ArrayList() create a new, empty ArrayListPoints off 1 2 3 4 Admin Total off Net ScoreCS 307 – Final Exam– Fall 2002Name____________________________________Last 4 digits of SSN / Student ID ______________Section Leaders Name ___________________________Instructions: 1. There are 4 questions on this test. Question 1 is worth 40 points; all others are worth 20 points each.2. You have 3 hours to complete the test.3. You may not use a calculator. 4. When code is required, write Java code. 5. You may not use any classes or methods from the Java Standard Library other than the ones specifically mentioned on each question.6. The style guide is not in effect except where noted7. Please make your answers legible. 1. Short answer questions. (2 points each) Write the answer to each question in the space provided. If code results in an error indicate if it is a compile error or runtime error.A. The following numbers are inserted in the order shown into a binary search tree with no checks to ensure or maintain balance. The tree is initially empty. Draw the resulting tree.195 156 20 68 162 150CS 307 – Final Exam – Fall 2002 1For parts B, C, and D consider the following binary tree. For each question assume when a node is processed the value in the node is printed out by the statement:System.out.print( currentNode.data + " " );B. What is the output of a preorder traversal of the tree?____________________________________________________C. What is the output of an inorder traversal of the tree?____________________________________________________D. What is the output of a postorder traversal of the tree?____________________________________________________E. Is the tree on page 2 a binary search tree?CS 307 – Final Exam – Fall 2002 2-42-5-2216181 13532138root of tree______________________ F. In a priority queue each element enqueued is placed in front of all elements already in the queue that have a lower priority, but behind all elements already in the queue that have a higher or equal priority? If the internal storage container for the priority queue is a doubly linked list with a head and tail reference what is the average case Big O for enqueueing an item to the priority queue?________________________G. What is the worst case Big O for inserting N items into an initially empty Binary search Treewith no checks or procedures to maintain balance?________________________H. What is the worst case Big O for inserting N items into an initially empty Red Black tree?________________________________________________________I. Consider the list data structure. A particular list uses an array as its internal storage container. When the container is full the array is always resized with space for 10 additional elements. What is the average case Big O for the default add operation, which always adds the new element to the end of the list? Give a brief explanation of your answer.________________________________________________________CS 307 – Final Exam – Fall 2002 3J. Consider the list data structure. A particular list uses an array as its internal storage container. When the container is full the array is always resized by creating a new array with a length equal to 3 times the length of the original array. What is the average case Big O for the default add operation which always adds the new element to the end of the list? Give a brief explanation of your answer_____________________________________________K. What is the Big O of this code? int N = 1000; int total = 0; for(int i = 0; i < N; i++) for(int k = 0; k < i; k++) for(int j = N; j > 0; j /= 2) total++;_____________________________________________L. What is the actual number of executed statements in the following code in terms of N. Assume N is declared and assigned a value prior to this codeint total = 0;for(int i = 0; i < N; i++)total++;for(int j = N; j > 0; j++)total++;for(int k = 0; k < N/2; k++)total++;______________________________________CS 307 – Final Exam – Fall 2002 4M. What is the Big O of the code from part L?_______________________________________N. Assume an algorithm takes 10 seconds to process a data set of size 1000. The algorithm has a Big O of O(N log2 N). How long do you expect the algorithm to process a data set of size 4000? log2 1000 approximately equals 10_______________________________________O. Assume an algorithm takes 20 seconds to process a data set of size 10,000. The algorithm has a Big O of O(N ^ 3). How long do you expect the algorithm to process a data set of size 40,000?_______________________________________P. Assume a native array of objects is used as the storage container for a stack. What is the bestcase Big O for popping all N elements in a stack? How must the stack me implemented to achieve this? ____________________________________________CS 307 – Final Exam – Fall 2002 5Q. Consider the following ListNode class:public class ListNode{ public Object data;public ListNode next;public ListNode prev;}Draw the object variables and objects that exists after the following code is executed. Use a "/" to indicate any object references that are null.ListNode N1 = new ListNode();ListNode N2 = new ListNode();N1.next = N1;N2.prev = N1;ListNode N3 = new ListNode();N3.data = N2;N1.prev = N3;____________________________________________CS 307 – Final Exam – Fall 2002 6R. Because all object variables in Java are really pointers and because all classes are descendants of the Object class there is an interesting possibility for implementation of a stack usingnative arrays of Objects. This implementation requires no recopying of elements at any time. Instead the initial storage container is a native array of objects of some fixed size, assume 10. After pushing 9 items with no pops the container only has one element left. When the 10th element is pushed instead of actually adding it to the container the last element is made to point to a native array of objects of length 20. When this container has 19 elements it is made to point at a native array of length 40. Visually the container would look like this:array elements 0 – 8 element 9 array elements 0 – 18 element 19 array elements 0 – 38 element 39 Briefly describe any difficulties, if any, involved with this implementation of a stack. ____________________________________________S. A set is a group of
View Full Document
Unlocking...