a) Consider a hash table of size 11 with hash function () = (11 + 4) 11. Draw the

table that results after inserting, in the given order, the following values: 65, 13, 49,

27, 89, 32, 46, 73, 33 for each of the three scenarios below:

i.

When collisions are handled by separate chaining;

ii.

When collisions are handled by linear probing;

iii.

When collisions are handled by double hashing using a second hash function

() = ( 9) + 1. Hint, the overall (combined) hash function is () =

( () + () ) 11, where i = 0, 1, 2, 3,

iv.

When collisions are handled by quadratic probing with a quadratic probe

function (, ) = (() + 0.5 + 0.5 2 ) 11 where = 1, 2, 3, .

b) What would be the contents of queue Q1 after the following code is executed and

the following data are entered?

1 =

1 =

( )

( 0)

(1, )

(1, )

(1, )

( 1)

(1, )

(1, )

The data are 23, 47, 29, 0, 69, 32, 13, 47, 28, 12, 76, 0, 34, 69, 5, 69,

84, 0