Multiple Choice 1. Which of the following represents "quadratic time? A. 3n+5n2+1 B. nlogn C. n'+n+1 D. 2"+n2+5 E. None of the above 2. Which of the following statements is TRUE about linked lists? A. All the elements in a linked list are always stored contiguously. B. Given a reference to the position, removing a node from a linked list is extremely inefficient. C. Linked lists support random access. D. You can traverse a singly linked list from head to tail and from tail to head. E. Each node in a singly linked list saves data as well as a link to its next node. 3. What is the big O notation for the following code snippet? for (int i = 0; i 0) { q.enqueue (s.pop()); } A. 10 B. 20 C. 30 D. 40 E. 50 11. Under which circumstances should a recursive solution be preferred to an iterative solution? (1) When the recursive version is more easily understood. (2) When the running time is critical. (3) When space (memory) is critical. A. None of them B. Only (1) C. (1) and (2) D. (1) and (3) E. All of them 12. For the array based unbounded Queue implementation, what happens if the underlying array is full and an enqueue operation is attempted? A. A QueueOverflowException is thrown. B. A QueueUnderflowException is thrown. C. A linked list is created to hold additional elements. D. A bigger array is created and all the elements in the current array are copied into the new array. E. Nothing happens. 13. Which statements about a binary search of an unordered array of size n are true? I. Each iteration eliminates half the search space that doesn't contain the target element II. It will not work because binary search requires an ordered array III. It works but always runs in the worst-case time, which is logn probes of the array A. I,II B. I, III C. II D. III E. None 14. While checking if ( 00100) ) is a balanced expression using the stack based method, what is the highest number of elements on the stack at any one time? A. 2 B. 3 C. 4 D. 5 E. None of the above Short Answers 15. For array based queues, what are the differences between the dequeue operations in the fixed front design and the floating front design? How do you determine the index of front in both cases (use formula if necessary)? 16. When choosing the underlying structure for an ADT implementation, in what circumstances would you use an array instead of a linked list? Explain your answer. OUTPUT: 17. What is the output of the following program? public class TraceRecursion { public static void main(String[] args) { myRec (25, 20, 30); } public static void myRec(int a, int b, int c) { if (a > 4) { myRec(b - 3,0 - 4, a / 2); System.out.println("bis " + b); } else System.out.println("a is " + a); Coding Questions 18. Recursion can be used to test if the sum of the elements in an array is an odd number. Assume that an array A has the following content: 5 6 A 87 31 1525 10 15 21 17 0 1 2 3 4 7 A boolean method oddsum(int[] a, int pos) is defined to check the oddness of the sum of the elements beginning at index pos. For example, oddSum (A, 0) returns true as the sum of the whole array is 221, which is odd, but oddSum (A, 3) returns false since A[3] + A[4] + A[5] + A[6] + A[7] = 88, which is not odd. The method does not change the content of the array. a) Assuming you are going to implement the oddSum method, what would be your base case? As far as the general case, how do you identify the oddness of the sum? Do not write code but use English to answer this question. (Hint: you may make the judgement based on the oddness of the element at pos and the oddness of the sum of elements beginning at pos + 1.) b) Write an implementation for the oddSum method according to your definition in part a). boolean oddSum (int[] a, int pos) { 19. Given the following definition of the LNode class, implement the methods "largestRec" (recursive) and "remove" (non-recursive) for the LinkedList class which represents singly linked lists. public class LNode private int m_info; private LNode m link; public LNode (int info) { m_info = info; m_link = null; } public void setLink (LNode link){ m_link = link; } public LNode getLink() { return m_link; } public void setInfo(int info) m_info = info; public int getInfo() { return m_info; public class LinkedList { private LNode head; // a reference to the first node in the list { public LinkedList() head = null; } // This is a wrapper method that calls largestRec. public int largest() { retuen largestRec (head); } // This recursive helper method finds the largest number in the list. // You can assume that the list has at least one element in it. public int largestRec (LNode node) { } // This non-recursive method removes a node from the list. It returns true // if the node is found and removed, otherwise, returns false. public boolean remove(int v) { }