CIS5100 Fall 2005 Exam #3, open book, open notes. Name ___________________ Each question is 10 points. Suppose that the linked list pictured below is built from 3 Nodes as defined below. class Node { Node start; // start -> 5 -> 7 -> 3 int data; Node next; } 1. What is the value of start.data ? ANSWER: 5 2. What is the value of start.next.next.data ? ANSWER: 3 3. Suppose that the linked list is used to implement a stack with the top at the front. Draw a picture of the list after the stack is popped once. ANSWER: start -> 7 -> 3 4. Write a statement in Java that removes the first node of the list. // ANSWER start = start.next; 5. Suppose that the array shown below has 7 sorted elements. Which values are tested during a binary search to determine that the value 8 is not present, and in what order are they tested? +----+----+----+----+----+----+----+ | 3 | 5 | 6 | 7 | 9 | 12 | 17 | +----+----+----+----+----+----+----+ ANSWER: any of the following: 3 17 7 12 9 3 17 7 9 17 3 7 12 9 17 3 7 9 7 12 9 6. Suppose that a sorted binary tree is built as pictured below. What nodes are tested to determine that 12 is not present? 8 / \ 3 14 / / \ 2 10 17 / 9 ANSWER: 8 14 10 7. Draw a picture of the tree after 6 and 4 are inserted in that order. ANSWER 8 / \ 3 14 / \ / \ 2 6 10 17 / / 4 9 8. Suppose that each Node in the tree is as defined below. Write a method int count(Node) that takes a Node pointing to the root of a tree and returns the number of nodes in that tree. For example, if root points to the 8 in the tree above, then count(root) returns 7 (or 9 after your two insertions). int count(Node n) { // your code here class Node { int data; Node left, right; } // ANSWER int count(Node n) { if (n == null) return 0; else return 1 + count(n.left) + count(n.right); } 9. A bubble sort of 10,000 elements takes about 1 second on a certain computer. About how long will it take on 50,000 elements? ANSWER: 25 seconds 10. List two sorting algorithms that will always be faster than bubble sort if the input array is large enough. ANSWER: any 2 of bubblesort, heapsort, mergesort, tree