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