Secition 1 Answer All Questions Question 1 : a) State the complexity of the merge sort. Sort the following numbers using merge sort:10,7,2,3,5. (2 Marks) b) Given a stack s and a queue q, both empty, what will be the contents of the queue and the stack after running the following operations: (3 Marks) q.enqueue(2): q.enqueue(10); q.enqueue(7); s.push(q.dequeue()); s.push(q.dequeue s.popO; c) Write a method that inserts an item into the front of a linked list of strings. State the complexity of your method (5 Marks) Question 3 Consider the following sequence of numbers 12,13,5,2,30,7,15,10,3 a) Consruct a binary search tree. (2 Marks) b) Show the hash table with size 9 using chaining and hash(x)= x mod 9 (3 Marks). Show the contents of the tree using inOrder traversal algorithm. (2 Marks) d) Construct a priority queue (min-heap) for for the same sequence of numbers (3 Marks) e) Write a method that find the maximum element in a BST and state the complexity of the method (3 Marks) 4 Question 2 a) Let array A and a list L both be of length n. What is the complexity of the following operations: i. Inserting an element to the beginning of L ii. Inserting an element to the beginning of A iii. Finding minimum element in A (3 Marks) b) Consider a Linked List with mystery Method() inside the class LinkedList Assume the linked list looks like this: first->2->5->3->7->1->null What will be the output of this method. State the method complexity public void mystery Method() { if(first != null) { Node p = first; while(p.next !=null) { p=p.next; }// end while System.out.println(p.dData); }// end if }//end method (3 Marks) c) Write a method that deletes an element from an ordered array of integers. State the complexity of your method (4 marks) 3 Question 4 a) Write a method that prints the contents of stack in a reversed order i.e from bottom to top. You can only use pop, push and top stack methods, enQueue and deQueue queue method and recurion (3 Marks) b) Consider a rat in a maze. There is only one entry and one exit. There are blocks in its path and it can easily take a wrong route. Find a path from the entry to the exit. Determine the data structures needed to represent and solve this problem b- Write an algorithm to help the rat get out of this maze (4 Marks) 4- . . . : . . . S E