Deck 11: Binary Search Trees

Question 1

A minheap is a complete binary tree in which each node is less than or equal to both the left child and the right child.

A) Minheap
B) Maxheap
C) Heap
D) Binary search tree

Answer 1

Minheap

Question 2

A minheap stores its smallest element at the ________ of the binary tree.

A) leaf
B) internal node
C) root
D) sibling

Answer 2

root

Question 3

Both children of the root of a minheap are _________.

A) Minheaps
B) Maxheaps
C) Heaps
D) Binary search trees

Answer 3

Minheaps

Question 4

The __________ method adds a given Comparable element to the appropriate location in the heap, maintaining both the completeness property and the ordering property of the heap.

A) add
B) addNext
C) addElement
D) none of the above

Question 5

Since a heap is a complete tree, there is only one correct location for the insertion of a new node, and that is either the next open position from the left at level h or the first position on the left at level h+1 if level h is full.

A) Minheap
B) Maxheap
C) Balanced tree
D) Complete tree

Question 6

Typically, in heap implementations, we keep track of the position of the last node or, more precisely, the last leaf in the tree.

A) root
B) internal node
C) leaf
D) tree

Question 7

To maintain the completeness of the tree, there is only one valid element to replace the ________, and that is the element stored in the last leaf in the tree.

A) root
B) internal node
C) leaf
D) tree

Question 8

Though not a queue at all, a minheap provides an efficient implementation of a _____________.

A) Priority queue
B) Circular queue
C) Deque
D) None of the above

Question 9

Because of the requirement that we be able to traverse up the tree after an insertion, it is necessary for the nodes in a heap to store a pointer to their ________.

A) children
B) parent
C) siblings
D) none of the above

Question 10

In an array implementation of a binary tree, the root of the tree is in position 0, and for each node n, n's left child is in position ________ and n's right child is in position ________.

A) 2n + 1
B) 2n + 2
C) 2(n + 1)
D) A and B
E) A and C
F) B and C

Question 11

The addElement operation for both the linked and array implementations is O(__________).

A) n
B) log n
C) n log n
D) None of the above

Question 12

The removeMin operation for both the linked and array implementations is O(log n).

A) n
B) log n
C) n log n
D) None of the above

Question 13

The __________ method consists of adding each of the elements of the list to a heap and then removing them one at a time.

A) heapSort
B) heapify
C) toString
D) None of the above

Question 14

Heap sort is O(________).

A) n
B) log n
C) n log n
D) None of the above

Question 15

A minheap is a complete ______ tree in which each node is less than or equal to both the left child and the right child.

Question 16

A ______ stores its smallest element at the root of the binary tree.

Question 17

The addElement method adds a given ______ element to the appropriate location in the heap, maintaining both the completeness property and the ordering property of the heap.

Question 18

Since a heap is a ______ tree, there is only one correct location for the insertion of a new node, and that is either the next open position from the left at level h or the first position on the left at level h+1 if level h is full.

Question 19

Typically, in ______ implementations, we keep track of the position of the last node or, more precisely, the last leaf in the tree.

Question 20

To maintain the ______ of the tree, there is only one valid element to replace the root, and that is the element stored in the last leaf in the tree.

Question 21

Though not a queue at all, a ______ provides an efficient implementation of a priority queue.

Question 22

Because of the requirement that we be able to traverse up the tree after an insertion, it is necessary for the nodes in a heap to store a pointer to their ______.

Question 23

In an array implementation of a binary tree, the root of the tree is in position 0, and for each node n, n's left child is in position ______ and n's right child is in position ______.

Question 24

The addElement operation for both the linked and array implementations is O(______).

Question 25

The removeMin operation for both the linked and array implementations is O(______)

Question 26

The heapSort method consists of adding each of the elements of the list to a ______ and then removing them one at a time. If the heap is a minheap, this results in ______ order. However, if the heap is a maxheap, this results in ______ order.

Question 27

Heap sort is O(______).

Question 28

A minheap is a complete binary tree in which each node is less than or equal to both the left child and the right child.

Question 29

A minheap stores its largest element at the root of the binary tree, and both children of the root of a minheap are also minheaps.

Question 30

The addElement method adds a given Comparable element to the appropriate location in the heap, maintaining both the completeness property and the ordering property of the heap.

Question 31

Since a heap is a binary search tree, there is only one correct location for the insertion of a new node, and that is either the next open position from the left at level h or the first position on the left at level h+1 if level h is full.

Question 32

Typically, in heap implementations, we keep track of the position of the last node or, more precisely, the last leaf in the tree.

Question 33

To maintain the completeness of the tree, there is only one valid element to replace the root, and that is the element stored in the first leaf in the tree.

Question 34

Though not a queue at all, a minheap provides an efficient implementation of a priority queue.

Question 35

Because of the requirement that we be able to traverse up the tree after an insertion, it is necessary for the nodes in a heap to store a pointer to their parent.

Question 36

In an array implementation of a binary tree, the root of the tree is in position 0, and for each node n, n's left child is in position 2(n+1) and n's right child is in position 2(n+2).

Question 37

The addElement operation for both the linked and array implementations is O(n log n).

Question 38

The removeMin operation for both the linked and array implementations is O(log n).

Question 39

The heapSort method consists of adding each of the elements of the list to a heap and then removing them one at a time.

Question 40

Heap sort is O(n log n).

Question 41

What is the difference between a heap (a minheap) and a binary search tree?

Question 42

What is the difference between a minheap and a maxheap?

Question 43

What does it mean for a heap to be complete?

Question 44

Does a heap ever have to be rebalanced?

Question 45

The addElement operation for the linked implementation must determine the parent of the next node to be inserted. Why?

Question 46

Why does the addElement operation for the array implementation not have to determine the parent of the next node to be inserted?

Question 47

The removeMin operation for both implementations replaces the element at the root with the element in the last leaf of the heap. Why is this the proper replacement?

Question 48

What is the time complexity of the addElement operation?

Question 49

What is the time complexity of the removeMin operation?

Question 50

What is the time complexity of heap sort?