APoints off 1 2 3 4 5 Total off Net Score CS 307 – Final – Spring 2006Name__________________________________________UTEID login name _______________________________Circle your TA’s name: Chendi VinodInstructions: 1. Please turn off your cell phones.2. There are 5 questions on this test. The are 120 points on the test.3. You have 3 hours to complete the test.4. You may not use a calculator on the test. 5. When code is required, write Java code. 6. Ensure your answers are legible. 7. You may add helper methods if you wish when answering coding questions.8. When answering coding questions assume the preconditions of the methods are met.1. (2 points each, 40 points total) Short answer. Place you answers on the attached answer sheet. For questions that ask what is the output:- If the code contains a syntax error or other compile error, answer “Compiler error”.- If the code would result in a runtime error or exception answer “Runtime error”.- If the code results in an infinite loop answer “Infinite loop”.On questions that ask for the Big O of a method or algorithm, recall that when asked for Big O youranswer should be the most restrictive Big O function. For example Selection Sort has an expected case Big O of O(N^2), but per the formal definition of Big O it is correct to say Selection Sort also has a Big O of O(N^3). Give the most restrictive Big O function. (Closest without going under.)A. The following numbers are inserted, one at a time, in the order shown, into a binary search tree with no checks to ensure or maintain balance. (i.e. the traditional naïve insertion algorithm.) The tree is initially empty. Draw the resulting tree.2, 4, 8, 16, 7CS 307 – Final – Spring 2006 1For parts B - E 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.getData() + " " );B. What is the output of a preorder traversal of the above tree?C. What is the output of an inorder traversal of the above tree?D. What is the output of a postorder traversal of the above tree?E. Is the binary tree shown above a binary search tree?F. If 1000 elements are inserted one at a time into a binary search tree with no checks to ensureor maintain balance (i.e. the traditional naïve insertion algorithm.) what is the worst case height of the resulting tree? The actual number, not a Big O function. (The height of a tree isthe number of links from the root to the deepest leaf. The height of the tree on this page is 2.)CS 307 – Final – Spring 2006 2root of tree105 39 125 51G. N elements are inserted one at a time into a Red Black tree. What is the worst case Big O of inserting all N items?H. In class we discussed the two ways Java allows the creation of generic data structures. The first method involves storing variables of type Object and relying on the fact that all objects are descendants of the Object class. The second method relies on parameterized data types, declaring the data type a particular data structure will hold when it is declared. For example the declarationStack<Integer> s1 = new Stack<Integer>();declares a Stack that only holds Integer objects. Briefly describe the two major problems with the first technique, storing variables of type Object and relying on the fact that all objects are descendants of the Object class.I. What is the output of the following code?Stack<Integer> s1 = new Stack<Integer>();for(int i = 10; i >= 4; i -= 2)s1.push(i);Stack<Integer> s2 = new Stack<Integer>();int j = 1;while( !s1.isEmpty() ){if( j % 2 == 0 )s2.push( s1.top() );s2.push( s1.pop() );j++;}while( !s2.isEmpty() ){System.out.print( s2.pop() + “ “ );}CS 307 – Final – Spring 2006 3Assume a Queue is being implemented with an ArrayList as its internal storage container. public class Queue<AnyType>{private ArrayList<AnyType> myCon;public Queue(){myCon = new ArrayList<AnyType>();}public AnyType front(){return myCon.get(0);}public AnyType dequeue(){return myCon.remove(0);}public boolean isEmpty(){return myCon.size() == 0;}public void enqueue(){// implementation not shown}}J. For the Queue class shown above what is the Big O of the method front?K. Consider method emptyAndTotal, which uses the Queue class shown above. If a Queue contains N items what is the Big O of method emptyAndTotal?public int emptyAndTotal(Queue<Integer> q){int total = 0;while( !q.isEmpty() ){total += q.dequeue();}return total;}CS 307 – Final – Spring 2006 4Consider the following method total.public int total(List <Integer> data){int total = 0;for(int i = 0; i < data.size(); i++)total += data.get(i);return total;}L. If the List data is an ArrayList with N elements what is the expected Big O of method total?M. If the List data is a SinglyLinkedList with N elements what is the expected Big O of method total?N. If the List data is a SinglyLinkedList with N elements what changes could be made to method total to improve the Big O?O. On the last assignment you were required to implement a binary search tree. Assume the BinarySearchTree class uses the traditional add algorithm and is implemented using recursion. If a list of integers in ascending order are inserted into a BinarySearchTree object a StackOverflowException occurs after adding a few thousand items. Briefly explain why this occurs.P. In class I discussed a problem from the book Programming Pearls. The problem involved sorting integer values from a file. The integers were known to be in the range from 0 to 9,999,999 and no value could occur more than once. The solution presented required an array 10,000,000 bits in size. If the range of integers in the file was the same, but a given value could occur at most 8 times, how much space would the solution presented in class require?Q. What is the expected Big O for determining the height of a Binary Search Tree? (The height of a tree is the number of links from the root to the deepest leaf.)CS 307 – Final – Spring 2006 5R. 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. Recall that all object variables in Java are pointers.ListNode n1 = new ListNode();ListNode n2 = new ListNode();n1.next =
View Full Document
Unlocking...