COP 3530 FINAL EXAM April 22, 2003
10 points
1. True of False for Java Classes and/or Interfaces
The Comparator interface should always be implemented in a class by itself. T or F
The worst case running time of quicksort is O(n2). T or F
A BinaryHeap can be constructed in O(n) time. T or F
The boolean contains(Object x) method of HashSet is O(1). T or F
The boolean contains(Object x) method of LinkedList is O(n2). T or F
15 points
2. Consider
class DNode {
Object data;
DNode previous;
DNode next;
DNode(){}
DNode(Object d, DNode p, DNode n) {
data = d;
previous = p;
next = n;
}
} // end DNode
Suppose that DNode p references a node in a circular doubly linked list
with a list head. Write the method
void addAfter(DNode p, Object x);
that adds x to the list immediately after p.
15 points
3. Write an O(n) method
ArrayList removeDuplicatesKeepOrderArrayList a);
that returns an ArrayList of the (unique) elements of a in the same order as in a but without duplicates.
15 points
4. Write a recursive method
Object max(ArrayList a, int right);
that returns the largest object in a between index 0 and index right. Assume that the objects in a are Comparable.
15 points
5a. Consider the NCAA data file of Assignment Two. Recall the format is
year:winning team:score:losing team:score
Write a main method to output to the screen each year along with all the teams that won a game that year in alphabetic order. To read the data you can use
BufferedReader in = new BufferedReader(new FileReader(“ncaa2003.data”);
String aLine;
while( (aLine = in.readLine()) != null ) {
5 points
5b. Suppose that instead of alphabetic order we want the teams to be displayed in order according to the number of letters in their name. Show how to modify your solution to 5a to achieve this.
15 pts.
6. The Tree class public methods are:
public Tree(Object rootData);
public void addChild(Tree t);
public Object getData();
public List getChildren();
public boolean isLeaf();
public Iterator iterator();
public String toString();
Write a method void
removeLeaves(Tree t);
that removes all the leaves from the Tree t. Assume that t is not a leaf.
10 points
7. Given the Binary Search Tree show the tree after the operations add(12), add(10), remove(11), and remove(7) are performed.
7
/ \
/ \
15
/ \ / \
1 11 17
/ \ / \ / \
3 9 13 16
/ \ / \ / \ / \
10 points
8a. Let BinaryHeap array A = { 1,3,4,5,8,9,12,6,7,10,13,20}. Show A after the removeMin() operation has been performed.
5 points
8b. What is the running time of the Object removeMin() method of from the BinaryHeap class?
5 points
8c. What is the running time if all of the elements in the BinaryHeap had the same priority?
15 points
9. Let sets = { -3, 0, -2, 1, 2, 6, -3, 2, 5 } be the array representing the DisjointSets data structure. Show the array after the following operations are performed
union(getName(3), getName(4));
union(getName(7), getName(8));
10 points
10. Given the following algebraic expression, show the corresponding expression tree.
a * b + c*(d + e) + f + g
15 points
11. Given the following graph:
Show the previous and distance values at each node after applying the all shortest paths for weighted graphs algorithm starting from 0.