PART I: Short Response

Directions: Answer each of the following questions. Please ensure that your responses are at least 3 to 5 sentences in length.

1. What is a linear implementation?

2. What kind of implementation of the ADT table is appropriate for retrieval-dominated applications, if the maximum size of the table is known? Why?

3. What kind of implementation of the ADT table is appropriate for retrieval-dominated applications if the maximum size of the table is NOT known?

4. What are the advantages of a linear implementation of the ADT table over a binary search tree implementation?

5. In an array-based implementation of the priority queue, where is the item with the highest priority value located?

PART II

Improve the palindrome-recognition algorithm C++ source code, by adding the first length / 2 characters to the queue and then pushing the remaining characters onto the stack.