Chapter 17 Questions
Multiple Choice Questions
1. A heap whose root contains the item with the largest search key is called a ______.
a. minheap
b. maxheap
c. complete heap
d. binary heap
2. A heap whose root contains the item with the smallest search key is called a ______.
a. minheap
b. maxheap
c. complete heap
d. binary heap
3. A heap is a ______.
a. general tree
b. table
c. full binary tree
d. complete binary tree
4. A semiheap is a ______.
a. table
b. complete binary tree
c. general tree
d. full binary tree
5. In an array-based implementation of a heap, the number of array items that must be swapped to transform a
semiheap of n nodes into a heap is ______.
a. n
b. n + 1
c. log2 n
d. log2 (n + 1)
6. In an array-based implementation of a heap, the remove operation is ______.
a. O(1)
b. O(n)
c. O(n 2)
d. O(log n)
7. In an array-based implementation of a heap, the parent of the node in items[i] is always stored in ______.
a. items[i/2]
b. items[(i-1)/2]
c. items[i-2]
d. items[(i-2)/2]
8. In an array-based implementation of a heap, the add operation is ______.
a. O(1)
b. O(n)
c. O(n 2)
d. O(log n)
Chapter 17 Questions
9. The heapsort is ______ in the worst case.
a. O(n)
b. O(log n)
c. O(n * log n)
d. O(n2)
10. The heapsort is ______ in the average case.
a. O(1)
b. O(n)
c. O(log n)
d. O(n * log n)
11. Which of the following is true about the heapsort?
a. the heapsort does not require a second array
b. the heapsort is more efficient than the mergesort in the worst case
c. the heapsort is more efficient than the mergesort in the average case
d. the heapsort is better than the quicksort in the average case
12. Since a heap is a complete binary tree, what would be an efficient basis for its implementation?
a. pointer based
b. array based
c. a bag
d. a set-based
Chapter 17 Questions
True/False Questions
1. In a maxheap, the root contains a search key greater than or equal to the search key in each of its children.
2. In a heap, the search keys of the children of a particular node have no relationship to each other.
3. The merge sort is more efficient than the heap sort in the worst case.
Chapter 17 Questions
Short Answer Questions
1. What are the two main differences between a heap and a binary search tree?
2. What is one strategy to transform a semiheap into a heap?
3. What does the priority value in a priority queue correspond to in a heap?
4. What is the major advantage that a heap implementation of a priority queue has over a binary search tree
implementation?
5. What must be done to remove the value in the root of a heap?