Description
1. Let the table have 9 slots, and let the hash function be h(k) = k mod 9. Demonstrate what happens
when we insert the keys 10, 22, 35, 12, 1, 21, 6, 15, 36, 33 into a hash table with collisions resolved by
chaining.
2. Suppose we use a hash function h to hash n distinct keys into an array T of length m. Assuming simple
uniform hashing, what is the expected number of collisions?
3. (a) Suppose you have two sequences, {24, 19, 12, 6, 24, 36, 40, 39} and {6, 12, 24, 19, 39, 40, 36, 24}. You
know the first one is generated from some BST A by pre-order tree walk, and the second one is
generated from some BST B by post-order tree work. Please draw all the possible BST A that can
generate the sequence. Repeat that for BST B.
(b) If all the keys in a BST are distinct, can you draw a unique BST when only given its pre-order tree
walk? If yes, please describe why; if no, find a counter-case.
4. For the binary search tree (BST) in pre-order as {8, 4, 16, 9, 19, 17, 22}. Please first draw the BST,
then show the result of following operations (each operation is carried out on the result of the previous
operation):
(a) Insert key 20;
(b) Then, delete key 8;
(c) Then, delete key 19;
(d) Finally, delete key 16.
