and 1. Each recursive call to a method creates new a. global variables, methods b. parameters, classes c. local variables, classes d. local variables, parameters 2. In a linked list, you must have: a. Head and tail pointers b. Head and tail and current pointers c. Tail d. pointer e. Head pointer 3. Which of the following data structures is most appropriate for situations in which you need to access certain data at certain location in constant time? a. an array b. a linked list c. a queue d. a stack e. a priority queue f. none 4. Which of the following statements regarding singly linked lists is true? a. Insert at tail, remove at head and remove at tail can be performed in constant time. b. Insert at head, remove at head and remove at tail can be performed in constant time. C. Insert at head, insert at tail and remove at tail can be performed in constant time. d. Insert at head, insert at tail and remove at head can be performed in constant time. 5. In a simple linked list implementation of a queue, with no tail pointer, where should a new element be inserted to achieve O(1) efficiency? a. At the head b. A the head or at the last node c. At the last node d. It is impossible to achieve 6. In a simple linked list implementation of a queue, with tail pointer, elements are inserted at the head of the linked list, from which end an element should be removed to achieve O(1) efficiency? a. At the head b. A the head or at the last node C. At the last node d. It is impossible to achieve 5. In a simple linked list implementation of a queue, with no tail pointer, where should a new element be inserted to achieve O(1) efficiency? a. At the head b. A the head or at the last node C. At the last node d. It is impossible to achieve 6. In a simple linked list implementation of a queue, with tail pointer, elements are inserted at the head of the linked list, from which end an element should be removed to achieve O(1) efficiency? a. At the head b. A the head or at the last node c. At the last node d. It is impossible to achieve Page 1 of 4 Part 2- What is the right ADT that best matches the situation described FC is a company that delivers food to customers. The company strategy is to deliver food according to the time customers place their orders. However, the delivery boy does not follow that strategy; he delivers food based on distance. The closest customer is served first. The delivery boy reached a neighborhood in which each house has 2 neighbors, one on the left side and the other is on the right side. Some customers in the neighborhood did not like the delivery boy strategy and they called FC customer service. The customer service employee received the complaints from the customers who got their orders late. However, when she gets a complaint, she places it over the previous one. Part 3- For each of the following code fragments, give an analysis of the running time (Big-Oh will do). (Remember, things are not always what they seem) int mystery(int n) int max if (intArray.length > 0) int count = 0; for (int i = 0; i max) max - intArray[num]; System.out.printin (max); 1 else 1 System.out.println ("The array is empty.") 3 1 int m2 (int n) int ml (n) f if(n-1) return n return n + mi in 1, n-2); int count = 0; for (int i = n; i > 0; i--) for (int j = 0; j 0; 1) for (int j = 0; j someNumber, then A(item, someNumber) return someNumber Part 4-State whether the following statements true or false; briefly explain why . A lower bound of f(n) - 5m + 100nlog(n) is (n). If f(n) O(g(n)), then g(n) is a lower bound on f(n). Function n-log(n) grows faster than (log(n)) To make recursion feasible, the recursion step in a recursive solution must resemble the original problem, but be a slightly larger version of the problem. Queue items are removed from the same end used for insertion As recursion is implemented using a stack, an object of class Stack must be declared and initialized in the program to hold the class objects of every recursive call. Suppose that you have a singly linked list with five nodes and ith head reference. Then the statement head head, next: will remove the first node of the linked list, Part 5- Algorithm design and Coding m + 1 no (nm) = 3 ron - 1,1) n = 1, m = 0 on-1.m-1) n> 1, m 2 1 Write a recursive method mystery(int n, int m) to calculate the above function. Write an algorithm to move a stack into a queue and return the queue to the caller. Write a non-recursive algorithm to compute the size of a stack. Make sure the stack does not lose its elements Write a recursive algorithm to compute the size of a stack. Make sure the stack does not lose its elements . Given the object dilArray, which is an array object of 5 doubly linked lists of int-each contains at least 4 nodes-, using the usual linked list operations, write the proper code segments to do the following: Display the data field of the head node of each linked list in the array. Remove the first node of the linked list at index 2 Page 3 of 4 Insert a node with the value 5 after the tail node of the linked list at index 1 Delete the first linked list in dllArray Part6. The diagram below shows a linked list of characters, along with two variables that each stores a reference/pointer to one of the nodes in the list. head "B 'E' null The nodes in the linked list are implemented using the following class class Node char val; Node next; a. On the diagram, circle the node specified by the expression head. next next b. What is the value of val of the node in the expression from part a? e. Write one or more lines of code that remove the node containing the character 'S from the list. d. Modify the diagram above to reflect the results of executing the following lines on the original version of the list (before the 'S' was removed): 9 9.next q.next - head<><>