Points off 1 2 3 4 Admin Total off Net ScoreCS 307 – Final Exam– Spring 2002Name____________________________________Last 4 digits of SSN / Student ID ______________Class Unique ID ___________________________Instructions: 1. There are 4 questions on this test. Question 1 is worth 60 points, all others are worth 20 points each.2. You will 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.7. Please make your answers legible. 1. Java mechanics and 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.307 310 108 408 313 336 105CS 307 – Final Exam – Spring 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 a 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 2002 237710140147 13175329root of tree______________________ F. Consider inserting 1 item into a binary search tree that contains N nodes. There are no special algorithms to ensure or maintain balance in the tree as items are inserted or deleted. What is the average case Big O for inserting 1 item into the tree?________________________G. Consider inserting 1 item into a binary search tree that contains N nodes. There are no special algorithms to ensure or maintain balance in the tree as items are inserted or deleted. What is the worst case Big O for inserting 1 item into the tree?________________________H. Consider inserting N items into a binary search tree that is initially empty. There are no special algorithms to ensure or maintain balance in the tree as items are inserted or deleted. What is the average case Big O for inserting N items into the (initially empty) tree?________________________________________________________I. Consider inserting N items into a binary search tree that is initially empty. There are no special algorithms to ensure or maintain balance in the tree as items are inserted or deleted. What is the worst case Big O for inserting N items into the (initially empty) tree?________________________________________________________ J. What is the Big O of this code? method1 always has a Big O of O(1).for (int i = 0; i < N; i++) for (int j = 0; j < i; j++) for(int k = 1; k < j; k++)method1();_____________________________________________CS 307 – Final Exam – Spring 2002 3K. What is the Big O of this code? method always has a Big O of O(N) where N is the magnitude of the parameter sent to method2.for (int i = 0; i < N; i++) for(int j = N; j > 0; j /= 2) method2(j)_____________________________________________L. What is the Big O of this code? method3 always has a Big O of O(N) where N is the magnitude of the argument sent to method3. method4 has a Big O of O(log N) where N is the magnitude of the parameter sent to method4for(int i = 0; i < N; i++)method3(i);for(int j = 0; j < 3 * N / 4; j++)method4(j);for( int k = 0; k < N; k++)method3(k);______________________________________M. What is the Big O of the following method?public static int method5(int N){ if( N < 0 )return 5; elsereturn 2 + method5( N – 1 );}_______________________________________N. What is the average case Big O of a preorder traversal on a binary search tree?_______________________________________CS 307 – Final Exam – Spring 2002 4O. A full binary tree is one where every level has the maximum number of nodes. How many nodes are in a full binary tree with 6 levels?_______________________________________P. Consider the following method:public int OS( int n ){ if ( n <= 1 )return n + 4;elsereturn n + OS( n / 3 ); }What is the output of the statement System.out.println( OS(41) ); ____________________________________________Q. 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 = N2;N2.prev = N1;ListNode N3 = new ListNode();____________________________________________R. A program with a Big O of O(N) takes 10 seconds to process a data set of size 200,000. What is the expected time for the same program to process a data set of 500,000 items?____________________________________________CS 307 – Final Exam – Spring 2002 5S. A program with a Big O of O(N ^ 2) takes 10 seconds to process a data set of size 50,000. What is the expected time for the same program to process a data set of 200,000 items?____________________________________________T. Consider the following code:int[] list; // line 1// code to create and fill list not shown// you may assume list is not nulllist[12] = 0; // line 2Can line 2 cause an exception? If so what must be done so that an exception cannot occur?__________________________________________CS 307 – Final Exam – Spring 2002 62. (Trees) This questions asks you to write a method that examines a binary tree. Recall that each node in a binary tree has a height. A node's height is equal to the path length from the node to its deepest leaf. The path length is equal to the number of links that must be navigated to get from one node to another. You are to write a method that determines how many nodes would have to be added to each level to make it full. A full level is one that has the maximum number of nodes possible. Consider the binarytree on page 2. Level 0 is short 0 nodes (this will always be the case for a
View Full Document
Unlocking...