94) A priority queue is

A) is a collection that allows elements to be added, but only allows the minimum element to be removed

B) a binary search tree in which the heights of the subtrees at each node differ by at most one

C) is a binary search tree that stores elements according to their natural order

D) is an AVL tree in which the root is the minimum element

95) A sorting algorithm based on a priority queue is

A) heap sort

B) insertion sort

C) quicksort

D) bubble sort

96) The order condition that characterizes a heap states that

A) at each node X, any element stored in a child of X must be greater than the element stored at X

B) an inorder traversal of the heap's binary tree must yield a sorted sequence

C) at each node X, any element stored in a left child of X must be less than the element stored at X, and any element stored in right child must be greater than the element stored at X

D) None of the above

97) The level of a node X in a binary tree

A) is the length of the path from the root to X

B) is the length of a longest path from X to a leaf

C) is the length of a shortest path from X to a leaf

D) is one more than the level of a child of X

98) The depth of a binary tree

A) is the depth of one of the subtrees plus one

B) is the length of the longest path from the root to a leaf

C) is the length of the shortest path from the root to a leaf

D) is the total number of leaves in the tree

99) A binary tree with depth d is complete if

A) every node that is not a leaf has 2 children and and all nodes at level d are as far to the left as possible

B) each level L < d has nodes

C) each level L < d has nodes and all nodes at level d are as far to the left as possible

D) every node that is not a leaf has 2 children

100) A complete binary tree with N nodes has depth approximately equal to

A) N

B) 2^N

C) log N

D) N^2

101) A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0], and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes. If nodes in the same level are stored in left to right order, then the left child of the node stored at A[k] will be stored at

A) A[2k+2]

B) A[2k]

C) A[2k+1]

D) A[k/2]

102) A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0], and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes. If nodes in the same level are stored in left to right order, then the right child of the node stored at A[k] will be stored at

A) A[2k+2]

B) A[2k+1]

C) A[k/2]

D) A[2k]

103) A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0], and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes. If nodes in the same level are stored in left to right order, then the parent of the node stored at A[k] will be stored at

A) A[k-1]

B) A[k/2]

C) A[(k-1)/2]

D) A[2k+1]

104) A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0], and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes. If nodes in the same level are stored in left to right order, then the node stored at A[k] will be a leaf if and only if

A) k/2 > N

B) 2k+1 > N

C) 2k+1 N

D) None of the above

105) To find the minimum element stored in a heap

A) you should look at the root of the binary tree

B) you should start at the root, and then keep passing from each node to its left child until you come to a node with no left child

C) you need to examine every node, and then pick the one with the least value

D) you should start at the root, and then keep passing from each node to its right child until you come to a node with no right child

106) To find the minimum node in a binary search tree

A) you should start at the root, and then keep passing from each node to its left child until you come to a node with no left child

B) you need to examine every node, and then pick the one with the least value

C) you should look at the root of the binary tree

D) you should start at the root, and then keep passing from each node to its right child until you come to a node with no right child 107) Traversing a binary search tree in inorder

A) yields a sequence in which the minimum element is at the approximate midpoint of the sequence

B) is more efficient than traversing the tree in preorder

C) yields the same sequence as a postorder traversal

D) will yield a sorted sequence

108) To add a new element X to a heap:

A) insert X using the same algorithm for insertion in a binary search tree. If the tree remains balanced, stop. Otherwise, execute a rebalancing operation.

B) Add X as a leaf, taking care to preserve the completeness of the heap. If X is now the root, or is greater than its parent, stop. Otherwise, repeatedly swap X with its parent until X becomes the root, or becomes greater than its parent.

C) First add X in the position of the root. If X is a leaf, or is less than its children, stop. Otherwise, repeatedly swap X with the smaller of its two children until X becomes a leaf, or becomes less than its children.

D) if the tree is empty, make X the root of a new tree; otherwise, compare X to the root, if X is less, put it in the left subtree, if it is greater, put in the right subtree

109) To add a new element X to a binary search tree:

A) insert X using the same algorithm for insertion in a binary search tree. If the tree remains balanced, stop. Otherwise, execute a rebalancing operation.

B) First add X in the position of the root. If X is a leaf, or is less than its children, stop. Otherwise, repeatedly swap X with the smaller of its two children until X becomes a leaf, or becomes less than its children.

C) if the tree is empty, make X the root of a new tree; otherwise, compare X to the root, if X is less, put it in the left subtree, if it is greater, put in the right subtree

D) Add X as a leaf, taking care to preserve the completeness of the heap. If X is now the root, or is greater than its parent, stop. Otherwise, repeatedly swap X with its parent until X becomes the root, or becomes greater than its parent.

110) Consider the operation of deleting the root of a binary search tree. If the root is a leaf, then

A) the reference to the root of the tree should be set to null

B) the element stored in the root node should be replaced with null, or with 0.

C) the root should be replaced with a dummy place-holder node

D) the method doing the deletion should throw an exception

111) Consider the operation of deleting the root of a binary search tree. If the root has one child, then

A) the element stored in the root node should be replaced with null

B) the operation should be recursively performed on the one subtree of the root

C) the reference to the root of the tree should be set to point to the one child

D) the root of the subtree should be recursively deleted

112) Consider the operation of deleting the root of a binary search tree. If the root has two children, then

A) the root node should be removed, then the least node in the right subtree should be deleted and used to replace the root

B) the rood node should be removed, and the deepest rightmost leaf should be used to replace the root

C) the operation should be recursively performed on the two subtrees of the root.

D) the rood node should be removed, the deepest rightmost leaf should be used to replace the root, and then a sift down should be performed to take the root replacement to its proper place