Autumn 2000

1. Insert the following keys in the given order in an initially empty order-3 B-tree: 3, 1, 4, 5, 9, 2, 6, 8, 7, 0.
Draw each step, as well as the final tree.

2. Consider the hash function h(x) = x mod 10 and the ordered input sequence of elements 4371, 1323, 6173, 4199, 4344, 9679, 1989.
Show the result of inserting these elements in that order into a hash table of size 10 bins (indexed 0..9), and organized:

a. by separate chaining;

b. by open addressing with linear probing, where F(i) = i;

c. by open addressing with quadratic probing, where F(i) = i*i.