COP 3530 Section U03 Spring 2017 PRACTICE FINAL EXAM =================== INSTRUCTIONS ------------ 1. This test is closed book, closed notebook. You cannot use the practice exam, the practice exam answers, and your programs. 2. You cannot use computers, calculators, or cellphones. 3. If you need to use the bathroom, do it before the test. 4. There are 5 questions on the test, for a total of 128 points. 5. Write all answers on the exam book. 6. If you do not understand the meaning of a question ask me during the test. 7. You have 2 hours to work on the test. 8. The classes BinaryNode and PriorityQueue are listed in the Appendix. 9. Figure 1 is also shown in the Appendix. 10. Write your name and student number below. Name:___________________________________________________________________ Student Number:_________________________________________________________ QUESTIONS: ---------- Question 1: ( 35 points) Write the method buildTheSearchTree that takes as input an array of type T, sorted in increasing order and without duplications. The method must generate a complete binary search tree and returns the root of the tree. For example, if arr is the array of strings shown below, String[] names = { "Alex", "Bill", "Carol", "David", "Elaine", "John", "Luke", "Mark", "Pepito", "Rita", "Tom", "Ursula", "Wendy", "Zelda"}; and we make the call BinaryNode root = buildTheBinarySearchTree(names); the method must generate the tree Figure 1 of the Appendix. In a complete binary tree all levels are filled with the possible exception of the last one. And even on the last level the nodes are added from left to right. Do not use any of the add methods from the classes BinarySearch and AvlNode. Instead,find the position of the root in the input array arr, create the root node and then use two recursive calls to generate the left and the right child of the root. The fields and the constructors of the BinaryNode class are listed in the Appendix. Feel free to use helper methods. If the input array is null or has no elements, return null. Write your program below. Use good style and write comments. // build a complete binary search tree from an array // sorted in increasing order public static > BinaryNode buildTheSearchTree(T[] arr) { // you write it ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ } Question 2. (28 points) Fill in the blanks. 1. We sort an array of n items by making pairwise comparisons. Even the best algorithms require O( ______________) comparisons for the worst case. 2. We search a sorted array with n items using the binary search method. In the worst case we check O( ______________) locations. 3. We use comparisons to find out if an item occurs in an AVL tree with n items. In the worst case we need O( ______________) tries. 4. We insert an item into a binary search tree with n items. In the worst case we must check O(______________) locations. 5. We delete an item from an AVL tree with n elements. In the worst case we must make at most O( ______________) changes. 6. In the best case, bubble sort needs O( ______________) comparisons to sort an array of n items. 7. We sort an array of n items using the insertion sort. In the worst case we need O( ______________) comparisons. 8. We delete the minimum element of a binary heep with n items. In the worst case we must make O( ______________) comparisons. 9. We search an unsorted array with n elements. In the worst case we make O( _______________) comparisons. 10. We delete a node in a java.util.LinkedList that has n items. Assume that we know the address of the node that is to be removed. We need O( _______________) time to do the removal. 11. The method merge of merge sort takes as input 2 sorted arrays. The first one has 12 items and the second one 11. In the worst case the methods does ____________ comparisons. 12. We add an item to a binary heap that already has n items. In the worst case we must check O(______________) locations. 13. We search a linked list with n items for a query. In the worst case we need to check O(______________) nodes. 14. The number of comparisons made by Quicksort in the average case is O(_______________________). Question 3. (30 points) Write a short recursive method public BinaryNode postorderGet(int i) that returns the ith node of the tree with root this in the postorder traversal. If i is out of range, throw a NoSuchElementException. The method will be added to the BinaryNode class. Feel free to use a helper method, but it must be recursive. You must also write an efficient program. Write your answer below. // return the ith node in the postorder traversal public BinaryNode getPostOrder(int i) { // you write it ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ } Question 4. (20 points) What will be printed out by the program below? import java.util.ArrayList; public class Spring16cop3530finalQ4 { public static void main(String[] args) { // print the title System.out.println("TESTING PRIORITY QUEUES"); System.out.println("=======================\n\n\n"); // form a priority queue System.out.println("We form a priority queue of names."); ArrayList friends = new ArrayList<>(); System.out.println("We add the names Tomato, Papa Bill, Turtleman, " + "Tornado, Poco Pelo,\nBaby Trevor, The Pastor, Little Girl," + " Guru, Papa Smurf, Shrek."); boolean more = friends.add("Papa Bill"); more = friends.add("Tomato"); more = friends.add("Papa Bill"); more = friends.add("Turtleman"); more = friends.add("Tornado"); more = friends.add("Poco Pelo"); more = friends.add("Baby Trevor"); more = friends.add("The Pastor"); more = friends.add("Little Girl"); more = friends.add("Guru"); more = friends.add("Papa Smurf"); more = friends.add("Shrek"); System.out.println("The heap of friends:"); PriorityQueue people = new PriorityQueue(friends); } } The file PriorityQueue.java is in the Appendix. Write your answer below. ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ Question 5. ( 15 points) Given the input {54, 78, 64, 21, 34, 25 } and the hashing function % 10 show the resulting a. linear probing hash table b. quadratic probing hash table Assume that the table has 10 entries. Write your answer below. Index | Linear Probing | Quadratic Probing | ____________________________________________________ 0 | | | ____________________________________________________ 1 | | | ____________________________________________________ 2 | | | ____________________________________________________ 3 | | | ____________________________________________________ 4 | | | ____________________________________________________ 5 | | | ____________________________________________________ 6 | | | ____________________________________________________ 7 | | | ____________________________________________________ 8 | | | ____________________________________________________ 9 | | | ____________________________________________________