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

### Solutions

Problem 1. (6 points) A Miscellany.

a. AException is a superclass of BException.

b. Θ(n2).

c. We divide the proof into two separate cases: either xy, or x < y.

In the first case, we have

log (x + y) ≤ log (2x) = log 2 + log x ≤ log x + log y
for all values y ≥ 2 and xy.

The second case, where x < y, is symmetric.

log (x + y) < log (2y) = log 2 + log y ≤ log x + log y
for all values x ≥ 2 and yx.

Therefore, log (x + y) ≤ log x + log y for all x ≥ 2 and y2, so log (x + y) ∈ O(log x + log y).

Problem 2. (10 points) Trees.

a. b. c. A binary heap of height h contains at least 2h keys. A binary search tree of height h contains at least h + 1 keys. A 2-3-4 tree of height h contains at least 2h + 1 – 1 keys.

d. e. Write a loop that iterates through k, keeps track of the minimum key so far, and counts the number of keys in k (except k) that are smaller than every previous key.

```int min = k;
int depth = 0;
for (int i = 1; i < k.length; i++) {
if (k[i] < min) {
min = k[i];
depth++;
}
}
```

Problem 3. (9 points) Graphs.

a. b. (6, 0)

c. d. Do you think that T must include the edge of G with the least weight? Yes. What about the edge with the second-least weight? Yes. What about the edge with the third-least weight? No.

Kruskal's algorithm must choose the first two edges, because it is impossible that the endpoints of those edges are already connected by a path. However, the third edge is rejected if the first three edges form a triangle.

e. Θ(n2 + e log e) = Θ(n2 + e log n); either expression is correct.

f. Asymptotic notation is meaningful only as the number of edges e approaches infinity. In a 100-vertex undirected graph, the number of edges cannot exceed 5,050.

Mail inquiries to cs61b@cory.eecs