1. The load factor is 0.4 2. (a) No, because the parent-child pairs 10-9 and 10-7 are out of order. (b) 1 / | \ / | \ / | \ / | \ / | \ / | \ 2 10 3 / | \ / \ 15 9 7 21 23 3. (a) O(n^3 log log n) (b) O(n^3) 4. There was some controversy over this question, concerning whether one should eliminate duplicate keys or not. With duplicates eliminated, one possible solution has 8,19,56,79 at the top level node, with three children: keys 8,10,17 in the first child, keys 19,33,41 in the second child, keys 56,75,78 in the third child, and keys 79,81,85 in the fourth child. There are many other valid solutions. 5. Linear probing. The problem didn't ask for an explanation, but the explanation is that linear probing will typically only use one external memory access per search (all of the cells it accesses are likely to be in the same cache line or the same page of virtual memory) while the other strategies will average more than one access per search. 6. Two double rotations.