Midterm II is available as PostScript: yellow, blue, red.

Solutions (blue)

Problem 1. (7 points) Quickies.

a. Use two hash tables; one for artists and one for record companies.

b. The maximum height of an n-node binary search tree is n - 1.

c. The minimax algorithm could be said to be using either a preorder or a postorder tree traversal. (Either answer was accepted as correct.)

d. Pruning does not affect the answer produced by minimax.

e. None. Because of the finally clause, the only exception that can be thrown is a NullPointerException, which is unchecked.

f. yz² + yx.

Problem 2. (6 points) Data Structures.

a.

b.

c.

Problem 3. (4 points) Merging Trees.

Set T's root to be the root of R. Find the node in R with maximum key. Set that node's right child to be the root of S.

Problem 4. (8 points) Inserting a Key into a Binary Heap.

public void insertItem(int key) {
  int i = size + 1;
  while ((i > 1) && (key < heapArray[i / 2])) {
    heapArray[i] = heapArray[i / 2];
    i = i / 2;
  }
  heapArray[i] = key;
  size++;
}