Exam 2

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).
Comments