COP
3530 Section 1 EXAM
2 April
3, 2001
Kraynek Name:_______________
10 points
1.
Show
the Binary Tree representation of the following tree.
10 points
2.
Given the algebraic expression 3 + a + 37*(4 – c) + x^2, draw the corresponding
expression tree.
15 points
3.
Given a binary tree of Integers write the method
int sum(BinaryTreeNode T);
that
returns the sum of the Integers in all the nodes of the tree T. Use
class
BinaryTreeNode {
Object data;
BinaryTreeNode left;
BinaryTreeNode right;
BinaryTreeNode(Object d) {
data = d;
}
BinaryTreeNode(Object d,
BinaryTreeNode l, BinaryTreeNode r) {
data = d;
left = l;
right = r;
}
boolean isLeaf() {
return left == null
&& right == null;
}
} //
end BinaryTreeNode
5 points
4.
If n is the number of nodes in the tree what is the running time of your method
from Problem 3 as a function of n?
15 points
5.
Write the method
String assemblyCode(BinaryTreeNode
T);
from
Assignment Three.
10 points
6.
Given the following graph, give a depth first search listing of the nodes.
15 points
7. Given
the classes, Edge and Vertex, and Vertex[] vertices as given in class examples
and assignments, write the method
String depthFirstSearch(int
startVertex);
that
produces a depth first listing of the nodes of the graph starting with
startVertex.
10 points
8.
Given the following weighted graph, show the previous and distance vales after
the weighted shortest paths algorithm is run on the graph.
10 points
9.
Given the array A = { 6,9,2,11,8,1,7,12,3,5}, show A after constructing a
Binary Heap from A using the pushDown(int i) method.