1. What makes one hash function better than another? What is a "perfect" hash function for a given set of keys? Is it possible to find a perfect hash function for a given set of keys? Explain.
2. Explain the difference between "chaining" and "open addressing" regarding hash tables.
3. Draw a binary search tree which stores the following numbers: 1, 3, 5, 7, 9, 11. Use 3 as the root.
a. How many comparisons must a binary search perform in order to find "11" in your tree?
b. Show the order of nodes visited by...
i. an in-order traversal of the tree.
ii. a pre-order traversal of the tree.
iii. a post-order traversal of the tree.
4. Draw a binary min-heap which stores the following numbers: 2, 3, 4, 5, 6, 7, 8, 9.
a. Show what happens when the root is removed (perform heapify-down).
b. Show what happens when the number 1 is added (perform heapify-up).