COP 3530 Section 1 EXAM 1 February 22, 2001

Kraynek Name:_______________

10 points

1. True of False for Java Classes and/or Interfaces

1. AbstractList is a subclass of List T or F
2. AbstractSequentialList is a subclass of ArrayList T or F
3. TreeMap is a subclass of TreeSet T or F
4. The boolean contains(Object x) method of TreeSet is O(1) T or F
5. The boolean contains(Object x) method of LinkedList is O(n) T or F

10 points

2. What is the big-O running time in terms of n of the following code segment?

int d = 1;

while( n >=1 ) {

n = n \ 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 b = a + problem3method(A,middle+1,right);

return b + A[middle];

}

20 points

4. Recall the class TreeNode:

class TreeNode {

Object data;

LinkedList children;

TreeNode(Object x) {

data = x;

children = new LinkedList();

} // end constructor

void addChild(Object x) {

children.add(new TreeNode(x));

} // end addChild

boolean isLeaf() {

return children.size() == 0;

} // end isLeaf

} // end TreeNode

Write a method with declaration

int numberOfNodes(TreeNode T);

that returns the number of nodes in the tree T.

15 points

5. Recall the node class for a doubly linked list

class Node {

Object data;

Node next;

Node previous;

Node() {}

Node(Object data, Node previous, Node next) {

this.data = data;

this.previous = previous;

this.next = next;

}

}

Let ListNode header point to the list head of a circular doubly linked list with a list head and ListNode current point to a node in the list. Write the method void add(Object x) that inserts a new node into the list immediately following current with x as data.

35 points

6. Write a Java class (program) that reads the NCAA data as in Assignment Two and outputs to a file each team that ever won a game in the tournament along with the total number of wins from all years that they won. Make sure each team appears only once. Use

BufferedReader in = new BufferedReader(new FileReader("ncaa2000.data"));

PrintWriter out = new PrintWriter(new FileWriter("problemrOut.txt"),true);

to open the input and output files.