## 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.