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

Solutions (red)

Problem 1. (7 points) Quickies.

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

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

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

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

e. y²x + yz.

f. Use two hash tables; one for engines and one for manufacturers.

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++;
}