- A Heap Implementation Carrano Ch.27 Exam Questions

Chapter 27 - A Heap Implementation

True/False (13)

1. A heap is a complete binary tree.
2. The most common implementation of a heap uses a linked list.
3. In a maxheap, the object in each node is greater than or equal to the objects in the node’s ancestors.
4. When a binary tree is complete, using an array instead of linked nodes is a better choice.
5. In the array-based heap, assuming heap entries start at index 1, when removing the heap’s largest object, you remove the root node.
6. In the class MaxHeap method removeMax, the heap’s root is replaced with its last leaf.
7. In the array-based heap, the add method uses O(n) operations.
8. It is more efficient to create a heap using the method reheap than the method add.
9. In the class MaxHeap method reheap, we begin at the first nonleaf closest to the end of the array.
10. We can use a heap to sort an array.
11. If we place array items into a maxheap and then remove them one at a time, we will get the items in ascending order.
12. Heap sort does not require a second array.
13. Heap sort is usually preferred over quick sort.

Short Answer (8)

1. Define a complete tree.
2. Given the following heap, assuming heap entries start at index 1, draw the corresponding heap array representation.
   

1. Given the following heap array, assuming heap entries start at index 1, draw the corresponding binary tree.
   

1. In the class MaxHeap, how do you tell if a heap is empty?
2. Explain how you add a new entry to a maxheap.
3. Given the following maxheap, assuming heap entries start at index 1, show the heap after adding the entry 14.
   

1. Given the following maxheap, assuming heap entries start at index 1, show the heap after adding the entry 87.
   

1. Given the following maxheap, assuming heap entries start at index 1, show the heap after adding the entry 87 using the array representation.
   

Multiple Choice (23) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. In a maxheap, the object in each node is greater than or equal to the objects in the node’s
   1. descendants
   2. ancestors
   3. siblings
   4. parents
2. A heap is a complete binary tree whose nodes contain _____ objects.
   1. Comparable
   2. equal
   3. generic
   4. similar
3. A complete tree is full to its next-to-last level, and its leaves on the last level are filled in from
   1. left to right
   2. right to left
   3. parent to child
   4. bottom to top
4. To represent a heap in an array, place the result of a(n) _____ traversal into consecutive array locations beginning at index 1.
   1. level order
   2. inorder
   3. preorder
   4. postorder
5. In an array-based heap, assuming heap entries start at index 1, the left child of node n is at index
   1. 2n
   2. 2n+1
   3. n
   4. n/2
6. In an array-based heap, assuming heap entries start at index 1, the right child of node n is at index
   1. 2n+1
   2. 2n
   3. n
   4. n/2
7. In an array-based heap, assuming heap entries start at index 1, the _____ child of node n is at index 2n.
   1. left
   2. right
   3. middle
   4. last
8. In an array-based heap, assuming heap entries start at index 1, the _____ child of node n is at index 2n+1.
   1. right
   2. left
   3. middle
   4. last
9. In an array-based heap, we can identify node n as the root by checking
   1. if n/2 is 0
   2. a sentinel value
   3. a boolean flag
   4. all of the above
10. Is the following binary tree a maxheap?
    
    1. no
    2. yes
    3. maybe
    4. it cannot be determined
11. Is the following binary tree a maxheap?
    
    1. yes
    2. no
    3. maybe
    4. it cannot be determined
12. When adding a new entry to a maxheap, the object in a node is _____ its descendant objects.
    1. greater than or equal to
    2. less than or equal to
    3. greater than
    4. less than
13. In an array-based heap, what array index do we put a new entry into in the first step of the add algorithm in the following tree?
    
    1. 7
    2. 6
    3. 0
    4. 1
14. In a binary tree where the objects are ordered as a heap except for the root, it is called a(n)
    1. semi-heap
    2. partial heap
    3. broken heap
    4. transformed heap
15. In the array-based heap, assuming heap entries start at index 1, when removing the heap’s largest object, you remove
    1. the root
    2. the entry at index 0
    3. the entry at the end of the last row
    4. the entry at the beginning of the last row
16. In the class MaxHeap method removeMax, the heap’s root is replaced with its
    1. last leaf
    2. smallest child node
    3. largest child node
    4. first leaf
17. In the array-based heap implementation, the method add has efficiency
    1. O(log n)
    2. O(n)
    3. O(1)
    4. O(n2)
18. In the array-based heap implementation, creating a heap using the add operation has efficiency
    1. O(n log n)
    2. O(log n)
    3. O(n)
    4. O(n2)
19. It is more efficient to create a heap using
    1. the reheap method
    2. the add method
    3. the sinkdown method
    4. none of the above
20. In the class MaxHeap method reheap, we begin at
    1. the first nonleaf closest to the end of the array
    2. the last leaf
    3. the root
    4. index 0
21. Given a heap with n nodes and height h, what is the efficiency of the reheap operation?
    1. O(h)
    2. O(n)
    3. O(log h)
    4. O(1)
22. If we place array items into a maxheap and then remove them one at a time, we will get the items in
    1. descending order
    2. ascending order
    3. inorder
    4. preorder
23. The average-case efficiency of heap sort is
    1. O(n log n)
    2. O(n²)
    3. O(log n)
    4. O(n)