Student Name: J#: 4) Given the following array, do the following (show all the w
ID: 3701786 • Letter: S
Question
Student Name: J#: 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 (c- 3 pts) What is the worst case number of comparisons for an unsuccessful search in the hash table of number of comparisons for a successful search using the hash table of (d - 7 pts) Show the sequence of iterations 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 (0) run on the array to get it sorted using the Selection SortExplanation / Answer
Hash Table H(56) = 56mod5 = 1 H(89) = 89mod5 = 4 H(23) = 23mod5 = 3 H(58) = 58mod5 = 3 H(22) = 22mod5 = 2 H(11) = 11mod5 = 1 H(45) = 45mod5 = 0 H(48) = 48mod5 = 3 H(90) = 90mod5 = 0 construct an array of linked list of size 5(since k=5) If more than one element maps to the array(hashtable) index then an extra list node is created to accomodate the new element Eg: hashtable[0] -> 45 -> 90, hashtable[1] -> 56 -> 11 since there are 9 elements and only 5 keys, in average case more than one element may map to a key, so number of comparisions can be 2 As per our implementation using chain probing in hash table, In worst case all elements in the input may map to same key and for an unsuccessful search in worst case number of comparision can be O(n) or 9 as per the problem As per selection sort in each pass over the array the minimum element and swapped with the index in consideration Pass one: working on index 0, element 11 and 56 are swapped. So current A = 11,89,23,58,22,56,45,48,90 Pass two: 11,22,23,58,89,56,45,48,90 Pass three: 11,22,23,58,89,56,45,48,90 Pass four: 11,22,23,45,89,56,58,48,90 Pass five: 11,22,23,45,48,56,58,89,90 Pass six: 11,22,23,45,48,56,58,89,90 pass seven: 11,22,23,45,48,56,58,89,90 pass eight: 11,22,23,45,48,56,58,89,90 pass nine: 11,22,23,45,48,56,58,89,90 BST: preorder traversal of BST:48,22,11,23,45,58,56,89,90 Average number of comparision: O(log N), where N is the height of the tree Average number of comparision for unsuccessful search is also O(log N)