Question

JH: Student Name: 4) Given the following array, do the following (show all the work). A (56, 89, 23, 58, 22, 11, 45, 48, 90) (a - 5 pts) Construct a hash table for the given array using the hash function H(K)- K mod 5 (b- 4 pts) Determine the average number of comparisons for a successful search using the hash table of (c -3 pts) What is the worst case number of comparisons for an unsuccessful search in the hash table of (d-7 pts) Show the sequence of iterations run on the array to get it sorted using the Selection Sort algorithm. (e - 8 pts) Use the sorted array of (d) to construct a binary search tree (f- 5 pts) Determine the average number of comparisons for a successful search in the binary search tree of (e). (g-8 pts) Determine average number of comparisons for an unsuccessful search in the binary search tree of (f)

Answer 1

Only 4 parts can be solved at a time. Post remaining questions separately.

a. Assuming linked list at every index of the array

k mod 5	Keys
0	45->90
1	56->11
2	22
3	23->58->48
4	89

b. Average Comparisons= [(1+ 2) + (1+ 2) + 1+ (1+ 2 + 3) + 1]/9= 14/9

c. Worst Case comparison: 3 as maximum no. of keys are 3 in some index of the hash table (4 if NULL need to be visited)  

d. Assuming sorting in ascending order and the smallest key is selected and put in the beginning.

After the first iteration:

11, 89,23, 58,22,56,45,48,90

After second iteration

11,22,23,58,89,56,45,48,90

After third iteration

11,22,23,58,89,56,45,48,90

After 4th iteration

11,22,23,45,89,56,58,48,90

After 5th iteration

11,22,23,45,48,56,58,89,90

After 6th,7th and last iteration, it remains same

11,22,23,45,48,56,58,89,90