1. Which of the following arrangements of general-purpose data structures is from slowest to fastest for the purpose of finding objects according to a key value:
a. sorted arrays, unsorted linked lists, hash tables, binary search trees
b. sorted arrays, binary search trees, linked lists, hash tables
c. hash tables, binary search trees, unsorted arrays, sorted linked lists
d. sorted linked lists, sorted arrays, binary search trees, hash tables
2. Which of the following arrangements of general-purpose data structures is from slowest to fastest for the purpose of storing objects by key value (not necessarily in order):
a. unsorted arrays, sorted linked lists, hash tables, binary search trees
b. sorted arrays, binary search trees, linked lists, hash tables
c. hash tables, binary search trees, sorted arrays, sorted linked lists
d. unsorted arrays, linked lists, binary search trees, hash tables
3. In an abstract data type, access is often limited to certain items. Which of the following is not such an abstract data type?
a. binary search tree
b. priority queue
c. queue
d. stack
4. Which of the following is not a basic data structure that could be used to implement an abstract data type?
a. array
b. linked list
c. hash table
d. heap
5. Which of the following statements is true?
a. An abstract data type can be conveniently searched for an item by key.
b. An abstract data type can be conveniently traversed.
c. An abstract data type is an interface within a program that simplifies problems.
d. An abstract data type is a database for direct user-accessible data.
6. Which of the following methods of implementing a priority queue is best when both insertion and deletion need to be reasonably fast?
a. ordered array
b. ordered linked list
c. heap
d. binary search tree
7. If the amount of data to be stored in a stack cannot be predicted, the best data structure to implement the stack is:
a. hash table
b. binary search tree
c. linked list
d. unordered array
8. Which of the following statements is true regarding a queue?
a. It may be implemented either by an array or a linked list.
b. It may be implemented by a heap because first in is first out.
c. It may be implemented by a linked list because insertions and deletions may be from the same end.
d. It may be implemented by an array without providing for wrap-around.
9. Which of the following sort algorithms is not an O(n2) sort?
a. shell sort
b. insertion sort
c. selection sort
d. bubble sort
10. Which of the following is true regarding the efficiency of the shell sort?
a. It is slower than O(n2).
b. It is faster than O(n*log2 n).
c. It is not as efficient as the insertion sort.
d. It has not been established theoretically, i.e. as a single function of n.
