EE4371 Assignment4-Data Structures Solved

Description

• Topic: Data Structures

1. Show how to implement a stack using two queues. Analyze the running time of the stack operations.
2. Demonstrate what happens when we insert the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be h(k) = k mod
3. Consider a binary search tree T​ ​ whose keys are distinct. Show that if the right subtree of a node x​ ​ in T​ ​ is empty and x​ ​ has a successor y​ ​, then y is the lowest ancestor of x​ whose left child is also an ancestor of x​ ​.
4. Describe a non-recursive algorithm for enumerating all permutations of the numbers {1, 2, …,n} using an explicit stack.
5. Show that any n-node binary tree can be converted to any other n​ ​-node binary tree using O(n)