COP 3530 Final Exam April 24, 2001
Kraynek Name:__________________
10
points
1. True of False for Java Classes and/or Interfaces
10
points
2. What is the big-O running time in terms of n of the following code segment?
int d = 1;
int e = 1;
while( e <= n ) {
e= e * 2;
d = d + 1;
}
10
points
3. What is the running time of the following method?
public int problem3method(int[] A, int left, int right) {
if( left > right) return 0;
int middle = (left+right)/2;
int a = problem3method(A,left,middle-1);
int s = a + problem3method(A,middle+1,right);
for(int i = 0; i < n; i++ ) {
s = s + A[i];
} // end for
return s;
}
20
points
4. Let A be an ArrayList where each element is A is a String. Write a method with declaration
void printStrings(ArrayList A);
that prints all the unique Strings from the ArrayList A in alphabetic order.
20
points
5. Given a binary tree write the method
int numberOfNodes(BinaryTreeNode T);
that returns the number of nodes in the tree binary 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
20
points
6. Suppose that the binary tree T is the binary tree representation of a non-binary tree. Write a method with declaration
void printChildren(BinaryTreeNode T);
that prints all of the children of T.
20
points
7. Suppose that T is a binary SEARCH tree. Write the method with declaration
Object getMax(BinaryTreeNode T);
that return the maximum value in the tree.
10
points
8. Given the following graph, give a depth first search listing of the nodes starting at vertex 0.
15
points
9. Suppose we have a closed hash table implemented as an array of ints with size = 10 and quadratic resolution of collisions. Show the array after the following operations have been performed:
insert(11);
insert(22);
insert(55);
insert(91);
insert(51);
insert(75);
15
points
10. Implement the method
public int get(int x);
from the DisjointSets class. You need not implement path compression.
15
points
11. Explain why any sort algorithm that swaps adjacent elements must be have running time O(n^2).
15
points
12. Given the algebraic expression 5 + a – 100/(4 + c) + x^2 + 2, draw the corresponding expression tree.
20
points
13. Define the class GraphNode:
class GraphNode {
int name;
LinkedList adjacentNodes;
boolean marked;
GraphNode(int n) {
name = n;
adjacentNodes = new LinkedList();
marked = false;
} // end constructor
} // end GraphNode
void printNodes(GraphNode G);
that prints all the nodes in the graph G.