$(50$ points$)$ Consider a hash table of size $N=7$ where we are going to store integer values. The

hash function is $h(k)=k$ mod $7.$ Draw the table that results after inserting, in the given order, the

following values: $5,15,12,26,11.$

$($a$)(10$ points$)$ Assume that collisions are handled by separate chaining.

$($b$)(10$ points$)$ Assuming collisions are handled by linear probing.

$($c$)(10$ points$)$ Assuming collisions are handled by double hashing, using secondary hash function

$h^{\text{'}}(k)=5-(kmod5).$

$($d$)(20$ points$)$ What are the advantages and disadvantages of the various collision resolution

strategies: Separate chaining, Lincar probing, Double hashing?

Solution: $(30$ points$)$

$($a$)(10$ points$)$ What is the preorder traversal of the following binary tree?

$($b$)(10$ points$)$ What is the inorder traversal of the above binary tree?

$($c$)(10$ points$)$ What is the postorder traversal of the above binary tree?

Solution: $(20$ points$)$ Consider the following binary max heap $($i$.$e$.,$ the array$-$representation of a heap$-$ordered

complete binary tree$).$ Here assume $xA.$

$(a)$ Delete the maximum key. Give the resulting binary heap. Circle those values that changed.

$(b)$ Insert the key $x$ into the original binary heap. Give the resulting binary heap. Circle those

values that changed.

Solution: