Question

(g - 6 pts) Construct a hash table of the given array using a hash function H(K) = K mod 5. (h - 6 pts) For the hash table of (g), determine the average number of comparisons for a successful search and the worst case number of comparisons for an unsuccessful search. (i - 9 pts) Consider the elements of the array assigned to you are known only one at a time. Construct a sequence of priority queues (as max heaps) with the insertion (enqueue) of one element at a time, as shown in the slides. (j - 7 pts) Transform the binary search tree of (c) to a min heap.

[12, 21, 12, 26, 11, 13, 26, 30, 12, 2, 3, 13]

Answer 1

binary search to min heap

12

21 12

     26 11     13 26   replace 21 with 12

30 12 2 3 13

21

12 12

     26 11     13 26 replace 12 with 26

30 12 2 3 13

21

26 12

12 11     13 26 replace 26 with 21

30 12 2 3 13

26

21 12

12 11     13 26 replace 12 with 26

30 12 2 3 13

26

21 12

30 11     13 26

12 12 2 3 13

26

30 12

21 11     13 26

12 12 2 3 13

30

26 12

21 11     13 26

12 12 2 3 13

30

   26    26

     21        11     13 12

12     12 2 3 13