"C""D"compareToPoints off 1 2 3 4 Total off Net ScoreCS 307 – Final – Fall 2003Name__________________________________________UTEID login name _______________________________Section Leader's Name ___________________________Instructions: This exam has several parts so be sure you complete each part. Part 1: Short answer questions in this package (16 pts)Part 2: Free Response question in this package (30 pts)Part 3: Multiple choice questions in separate booklet (24 pts)Part 4: Free Response Question in separate booklet (30 pts)1. Make sure the serial number on the bubble sheet matches the serial number on your test booklet. 2. For the Multiple choice place you answers on the bubble sheet inside the package you were handed out. 3. For the separate free response question write your answers in that booklet.4. Write your name and "The University of Texas" on the multiple choice and free response booklet. You can write inside both booklet.5. Do not enter your name on the bubble sheet. 6. Enter 25 for the college code and grid in the ovals for 2 and 5.7. Print and grid in the ovals that correspond to the preprinted number in the corner of the answer sheet. This number should match the number printed on the test booklet.8. When finished turn in all of your materials including this booklet, the Multiple Choice booklet, the Free Response booklet, the bubble sheet, and the quick reference sheet.9. IMPORTANT. Clarifications to questions. a. Form 4ABP-V4, Serial numbers 5831 - 5900Multiple Choice, Question 5, page 7. In line 4 of the code place a "(" between for and intb. Form 4ABP-V4, Serial numbers 5831 - 5900Multiple Choice, Question 8, page 10. At the end of the statement "Assume that mat contains the following values." add the statement "Note that mat[0][4] is 2."1. (2 points each, 16 points total) Short answer. If an error would occur answer "syntax error" or "runtime error" depending on what type of error it would be. 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.)CS 307 – Final – Fall 2003 1A. 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.106 6 144 122 40 1_____________________________________________________________________________For 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() + " " );CS 307 – Final – Fall 2003 2root of tree"D""A""C" "E""G""M""Z""S""T"B. What is the output of a preorder traversal of the tree on page 2?____________________________________________________C. What is the output of an inorder traversal of the tree on page 2?____________________________________________________D. What is the output of a postorder traversal of the tree on page 2?____________________________________________________E. Given a Binary Search Tree with N nodes and no checks to ensure or maintain balance, whatis the worst case Big O for removing an item from the tree?_____________________________________________________________________________F. Given a Binary Search Tree with N nodes and no checks to ensure or maintain balance, whatis the average case Big O for removing an item from the tree?_____________________________________________________________________________CS 307 – Final – Fall 2003 3G. Given a Binary Search Tree with N nodes and no checks to ensure or maintain balance, whatis the worst case Big O for generating an ArrayList that contains all the elements of the tree and is in sorted order? (The ArrayList can be created with an initial capacity of N.)_____________________________________________________________________________H. Assume social security numbers are used as the keys for inserting Person Objects into a hashtable. The hash function adds the last 3 digits of the social security number to obtain the hash value. The array to hold objects has a length of 10. The table is not resized during the following insertions. The hash table uses open addressing (1 entry per element) and uses linear probing to resolve collisions. The hash table is initially empty. Show the hash table after inserting the following Person objects in the order shown.Frodo 000-00-0002Sam 123-45-6789Merry 987-65-4321Pippin 555-55-5557 0 1 2 3 4 5 6 7 8 9CS 307 – Final – Fall 2003 4No test materials on this pageCS 307 – Final – Fall 2003 52. (Trees, 30 points) Consider the following class for Binary Tree Nodespublic class TreeNode{private Comparable value;private TreeNode left;private TreeNode right;public TreeNode(Comparable initValue){ value = initValue;left = null;right = null;}public TreeNode(Comparable initValue, TreeNode initLeft, TreeNode initRight){ value = initValue;left = initLeft;right = initRight;}public Comparable getValue(){ return value; }public TreeNode getLeft(){ return left; }public TreeNode getRight(){ return right; }//other methods not shown}Recall that any and all classes that implement the Comparable interface must implement a compareTo method as described below:compareTopublic int compareTo(Object o)Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.returns a negative integer if the calling object is "less than" the parameter o, zero if the calling object and the parameter o are equal, and a positive integer if the calling object is "greater than" the parameter o.CS 307 – Final – Fall 2003 6Complete a method that determines if the node root, is the root of a binary search tree. Recall that the binary search tree property is that for every node in the tree, all elements in a node's left subtree are less than that node's data and all elements in the node's right subtree are greater than the node's data. Recall that if a node is null, it is the root of an empty binary search tree. The Big O of your method
View Full Document
Unlocking...