CS 61B: Data Structures (Spring 2004)
Midterm II

### Solutions

Problem 1. (6 points) Quickies.

a. There are several acceptable answers. Here are the best ones:

• Find the maximum key.
• Find the smallest key greater than or equal to k.
• Find the greatest key less than or equal to k.
• Any of the above, with ``find'' replaced by ``remove.''
Note: answers that involved a bad hash code or a high load factor were not accepted. Our hash table has a good hash code and a reasonable load factor.

b.

• g(x) in O(f(x)) could be either.
• g(x) in Omega(f(x)) must be true.
• g(x) in Theta(f(x)) could be either.
• f(x) in Omega(x g(x)) must be false.
• g(x) in Omega(x f(x)) could be either.
• f(x)2 in O(g(x)2) must be true.

c. No. The signatures are the same but the prototypes are different (because the return types are different), so the two signatures are forever incompatible.

d.

Problem 2. (8 points) Trees.

a.

b. 1 2 0 5 4 7 6 9 8 3

c.

d. The best-case time for finding the minimum key in a binary search tree is Theta(1), because the minimum key might be stored at the root (no matter how large the tree is). In this case, the root has no left child, and all the other keys are in its right subtree.

The best-case time for finding the minimum key in a 2-3-4 tree is Theta(log n), because the minimum key is stored in a leaf, and every leaf is at a depth of Theta(log n).

e. No. The heap order property says that a left child's key must be greater than or equal to its parent's key. The binary search tree invariant says that a left child's key must be less than or equal to its parent's key. If both invariants hold, a left child's key must be equal to its parent's key. But the tree has no duplicate keys, so no key can have a left child.

Problem 3. (6 points) The Match Game.

Problem 4. (5 points) Graphs.

a.

• 1 2 3 4 5
• 1 3 2 4 5
• 1 3 4 5 2
• 1 5 4 3 2

b. No. Breadth-first search visits all vertices at a distance of 4 from the start vertex before any vertex at a distance of 5 from the start vertex. Therefore, BFS always visits vertex 5 before vertex 10.

c. Theta(|V| |E|).

d. When you do breadth-first search on a graph G starting from a vertex v, BFS computes the shortest spanning tree of G rooted at v. It also tells you the depth of each vertex, so you can easily figure out the height of the rooted spanning tree--it's equal to the depth of the deepest vertex. So the algorithm runs BFS |V| times, starting once at each vertex, and chooses the shortest of the |V| spanning trees.

Mail inquiries to cs61b@cory.eecs