Data structures

PROBLEM 1 Hash Table: Consider a hash table with ten hash locations. Using the hash function h(x) = x mod 10, insert the keys (33, 54, 69, 74, 18, 19) (in the order given) into the hash table. Use the secondary hash function '(x) 1 (x mod9) for collision resolution. Draw the resulting hash table. What happens when you attempt to insert the key 94 into the final hash table obtained in hash table Explain. 0 1 2 3 4 5 6 7 8 9 PROBLEM 2 Trees: Consider the binary tree shown below. For each of the traversals listed, give the order in which the nodes are visited preorder inorder postorder breadth-first PROBLEM 3 Draw the sequence of AVL trees obtained when the following keys are inserted one-by-one, in the order given into an initially empty AVL search tree: (16, 27.9.11.36, 54, 81, 63, 72) Identified rotations, if there is any PROBLEM 4 T1, T2 and T3 are subtrees of the tree rooted with y (on the left side) or x (on the right side) fill the function to left rotate subtree rooted with X. X / Right Rotation / X T3 T1 T1 T2 Left Rotation T2 T3 Node Node right Rotate(Node y) { Node X - y.left: X.right: X Perform rotation x. right - y -T2 V Update heights y.height = max(heightfy.left height ....... +11 x.height - tax theight........., height (.right)) + 11 y Return new root return : 3 Node leftRotate(Node ) { Nodey Node 72 - /Perform rotation y.left - X.right Update heights max(height 1x. latt), height (.right) + 13 max(heightly.left), height lyright) + 1; // Return new root return .............. PROBLEM 5 Consider the following directed, weighted graph: A D 20 9 5 11 4 F G H 12 1 A) Use Dijkstra's algorithm to calculate the single-source shortest paths from vertex A to every other vertex B) Step through Prim's algorithm to calculate a minimum spanning tree starting from vertex A