If a heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value? (3 points) A. data[0] B. data[n-1]

 C. data[n] D. data[2*n + 1] E. data[2*n + 2] 

Tree algorithms typically run in time O(d) . What is d? (3 points) A. The depth of the tree. B. The number of divisions at each level. C. The number of entries in each node.

D. The number of nodes in the tree. E. The total number of entries in all the nodes of the tree.

What is the best definition of a collision in a hash table? (3 points) A. Two entries are identical except for their keys. B. Two entries with different data have the exact same key. C. Two entries with different keys have the same exact hash value. D. Two entries with the exact same key have different hash values.

In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which function has a better implementation because of this difference? (3 points) A. insert

B. is_present C. remove D. size E. Two or more of the above functions

A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table? (3 points) A. 256 B. 511

C. 512 D. 1024 E. There is no maximum.

What is the minimum number of nodes in a full binary tree with depth 3? ( 3 points) A. 3

B. 4 C. 8 D. 11 E. 15

What is the minimum number of nodes in a complete binary tree with depth 3? (3 points)

A. 3 B. 4 C. 8 D. 11 E. 15

Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T? (3 points)

A. 0 B. 3 C. 4 D. 5

Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored? (3 points)

 A. data[i+1] B. data[i+2] C. data[2*i + 1] D. data[2*i + 2] 

Here is a small binary tree.

14

/\ 2 11

/\ /\ 1 3 10 30

// 7 40

What is the order of nodes visited using a pre-order traversal? (3 points)

A. 1 2 3 7 10 11 14 30 40 B. 1 2 3 14 7 10 11 40 30 C. 1 3 2 7 10 40 30 11 14 D. 14 2 1 3 11 10 7 30 40