Points off 1 2 3 4 Admin Total off Net ScoreCS 307 – Final Exam– Spring 2003Name____________________________________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. You may native / built in arrays on any and all questions if you wish. 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.Recall that when asked for Big O your answer should be the most precise Big O function. For example Selection Sort has an average case Big O of O(N^2), but per the formal definition of Big Oit is technically correct to say Selection Sort also has a Big O of O(N^3). On this test I want the most precise Big O function. (Closest without going under.)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.101 -12 59 37 91 201CS 307 – Final Exam – Spring 2003 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.getData() + " " );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 – Spring 2003 219111131317 517 61root of tree 151______________________ For questions F and G consider the following Queue classpublic class Queue{ // create an empty queuepublic Queue()// add this element to the back of the queuepublic void enqueue(int x)// access the front element of the queuepublic int front()// remove front element of queuepublic void dequeue()// returns number of items in queuepublic int size()}F. What is the output of the following code:Queue q = new Queue();q.enqueue(12);q.enqueue(13);q.enqueue(q.front());q.enqueue(q.front());q.dequeue();q.enqueue(25);for(int i = 0; i < 3; i++){ System.out.print( q.front() + " " );q.dequeue();}________________________CS 307 – Final Exam – Spring 2003 3G. What is the output of the following code:Queue q = new Queue();q.enqueue(3);for(int i = 1; i < 17; i *= 2)q.enqueue(i);int limit = q.size();for(int i = 0; i < limit; i++){ System.out.print( q.front() + " " );q.dequeue();}________________________H. Consider a Doubly Linked List that stores data in sorted order. The Linked List only maintains links to the first and last node in the list. What is the average case Big O of determining ifa given value is present in the Linked List assuming the most efficient search method is used?________________________________________________________I. Consider an ArrayList that stores data in sorted order. What is the average case Big O of determining if a given value is present in the ArrayList assuming the most efficient search method isused?________________________________________________________J. Consider the graph Abstract Data Type. A graph is made up of nodes and links that connect nodes. One possible internal storage container for the graph ADT is an adjacency matrix. This is a 2D array with the number of rows equal to the number of nodes in the graph and the number of columns also equal to the number of nodes. How many elements are in the matrix given a graph with N nodes?_____________________________________________CS 307 – Final Exam – Spring 2003 4K. Consider the graph Abstract Data Type with an adjacency matrix, 2D array of booleans, as the internal storage container. If there are N nodes in the graph what is the Big O of adding a node to the graph ADT when using an adjacency matrix as the internal storage container. _____________________________________________L. What is the Big O of the following code:public int rogue(int n){ if(n <= 0)return 1;else return rogue(n/2) + rogue(n/2);}______________________________________CS 307 – Final Exam – Spring 2003 5For questions M and N consider the following Stack classpublic class Stack{ // create an empty stackpublic Stack()// add this element to the top of the stackpublic void push(int x)// access the top element of the stackpublic int top()// remove top element of stackpublic void pop()// returns number of items in stackpublic int size()}M. What is the output of the following code:public void colossus( int n ){ Stack s = new Stack();for(int i = n; i >= 0; i -= 3)s.push(i);for(int i = 0; i < 4; i++){ System.out.print( s.top() + " " );s.pop();}}// in some other methodcolossus(20);_______________________________________N. What is the Big O of method colossus in part M? All methods in the stack class are O(1)._______________________________________CS 307 – Final Exam – Spring 2003 6O. 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 arrows to show what is stored in pointers. Use a "/" to indicate any object references that are null. ListNode N1 = new ListNode();ListNode N2 = new ListNode();N1.prev = N2;N1.prev.prev = N1;ListNode N3 = N2;N2.prev.next = N2;_______________________________________P. What is the average case Big O for a postorder traversal of a binary tree? What does the N inthe Big O function represent?____________________________________________Q. What is the worst case Big O for inserting a single item into a Red Black Tree?____________________________________________CS 307 – Final Exam – Spring 2003 7R. Consider a Doubly Linked List class. The Linked List only maintains pointers to the first and last nodes in the
View Full Document
Unlocking...