Exam Prep Chapter 21 Heaps And Priority Queues - Java Foundations 4th Edition | Test Bank with Answer Key by John Lewis by John Lewis, Peter DePasquale, Joe Chase. DOCX document preview.
Chapter 21: Heaps and Priority Queues
Multiple Choice Questions:
1) In a heap with_______ nodes, the next element to be added to the heap will start a new level in the heap.
a) 2
b) 3
c) 4
d) 5
e) 6
2) When the removeMin operation removes the minimum element from a minheap, that element is initially replaced by its
a) left child
b) right child
c) the smaller of the left or the right child
d) the element in the last node that was added
e) none of these is correct
3) Maintaining a heap as a complete binary tree means that
a) the tree is unbalanced
b) leaf nodes are created at the lowest level in left- to right order
c) the tree is degenerate
d) every leaf node is at the same level
e) none of the above
4) A(n)____________________ is a collection that is ordered using two ordering rules
a) priority queue
b) interface
c) exception
d) stack
e) none of the above
5) Adding an element to a heap is ______________
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
e) none of the above
6) A priority queue can be implemented using
a) a list of queues
b) a minheap
c) a stack
d) both a) and b) are correct
e) all of a), b), and c) are correct
7) Sorting an array using a heap sort means that an element removed from a minheap will be
a) the next array element in descending order
b) the next array element in ascending order
c) re-inserted into its proper position in the minheap
d) an array element, but its position in the sorted array is not known
e) None of these is true
8) Heap sort is an __________ sorting algorithm.
a) O(1)
b) O(n)
c) O(n log n)
d) O()
e) none of the above
9) Which of the following is not part of the operation of adding an element to a heap?
a) Add the node for the element at the appropriate location in the heap
b) Reorder the heap to maintain the proper order of the nodes.
c) Rebalance the heap.
d) Reset the pointer to the last node that was added to the heap.
e) All of these are part of the operation of adding an element to a heap.
10) In a minheap in which all elements are distinct, the largest element is at
a) the root of the tree
b) the next level below the root of the tree
c) a node that is not a leaf node
d) a leaf node of the tree
e) The largest element could be anywhere in the tree.
11) When discussing a heap, the phrase “the last leaf in the tree” refers to
a) the rightmost leaf at the last level of the tree
b) the leftmost leaf at the last level of the tree
c) the node that is farthest from the root of the tree
d) the node with the largest value
e) the node that will be the last one to be removed from the tree
12) Which of the following is not a heap operation when working with a maxheap?
a) addElement
b) findMax
c) removeMax
d) removeElement
e) All of these are heap operations that can be used when working with a maxheap.
13) A ____________________ is a complete binary tree in which each element is greater than or equal to both of its children.
a) binary search tree
b) stack
c) full tree
d) maxheap
e) none of the above
14) In a maxheap, the largest element in the structure is always ______________________ .
a) a leaf
b) an internal node
c) the root
d) the left child of the root
e) the right child of the root
15) Which of the following is always true when adding an element to a heap?
a) The new element will always be a leaf.
b) The new element will always be the root.
c) The new element will always be an internal node.
d) The new element will always have 2 children.
e) none of the above is always true
1) The difference between a minheap and a maxheap is the order of the nodes between parents and children.
2) As an Abstract Data Type, a Heap interface inherits from a BinaryTree interface
3) When adding an element to a heap, the element is initially added as a root node.
4) In a minheap, the findMin operation is O(1).
5) A school sets up the following schedule for students to register for classes for next term: students in the Senior class register on Monday, Juniors on Tuesday, Sophomores on Wednesday, and finally students in the Freshman class on Thursday. On each day, students of the appropriate class register in first come, first served order. This is an example of a set of priority queues.
6) One of the benefits of implementing a heap with links is that a node does not need a link to its parent.
7) In a maxheap, the largest element is always the root.
8) Whenever a new element is added to a maxheap, it always becomes the root.
9) A heap sort sorts elements by constructing a heap out of them, and then removing them one at a time from the root.
10) Implementing a heap using an array simplifies the management of the last added node in the heap.
1) In what ways is a heap different from a binary tree?
2) What properties does a heap share with a binary tree?
3) Where is the largest element in a minheap found?
4) What steps are involved in removing an element from a minheap?
5) When comparing an array-based implementation of a heap against a linked implementation, which is more efficient?
6) A heap is a complete binary tree. What is required for the tree to be complete?
7) A heap is a binary tree. What operations does a heap add to the BinaryTree interface?
8) What is a maxheap?
9) Explain how an element is added to a maxheap.
10) What is a priority queue?
11) How can a heap be used to implement a priority queue?
12) In an array implementation of a heap, which element is the root of the binary tree?
13) Explain how heap sort works.
14) What is the complexity of heap sort? How is it calculated?
15) An array is sorted into ascending order. The following sequence of steps will put the array into descending order:
- Copy the array into a maxheap
- Remove the elements from the maxheap and put them in order into the array.
Is this the best way to put the array into descending order?
Document Information
Connected Book
Java Foundations 4th Edition | Test Bank with Answer Key by John Lewis
By John Lewis, Peter DePasquale, Joe Chase