COP 3530 Section 1 EXAM 1 November 15, 2001

Kraynek Name:_______________

10 pts.

1. Let class Node be defined as:

 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;
 }
}

Suppose we are implementing a PriorityQueue (NOT a DoublePriorityQueue) using a sorted circular doubly linked list with a list head of Nodes pointed to by header, a Node variable. Write the method

Object deleteMin();

that deletes the minimum element (the Node containing the minimum element) from the list.

12 pts.

2. Consider the following tree:

A

/ | \

B C D

| / | \

E F G H

/ | \

I J K

List the nodes of the tree in

i. preorder

ii. inorder

iii. postorder

iv. level order.

15 pts.

3. Let T be a tree and class TreeNode be defined as:

class TreeNode {
 Object data;
 LinkedList children;
 
 public TreeNode(Object x) {
 data = x;
 children = new LinkedList();
 } // end constructor
 
 void addChild(Tree t) {
 children.add(t);
 } // end addChild
 
 boolean isLeaf() {
 return children.size() == 0;
 } // end isLeaf
}

Suppose the data are of type Integer. Write a recursive method to count the number of 37’s that are in the tree.

15 pts.

4. Write a method to return a String listing the nodes of a tree in preorder without using recursion.

8 pts.

5. Given the expression a + b * (c – d) + e / f ^2, draw the corresponding expression tree.

8 pts.

6. Draw the binary tree representation of the tree from problem 2.

A

/ | \

B C D

| / | \

E F G H

/ | \

I J K

10 pts.

7. Write the method

 BinaryTreeNode insert(Object x, BinaryTreeNode T);
 

from the BinarySearchTree class that inserts x into the binary search tree with root T.

10 pts.

8. Let A = { 4, 7, 9, 5, 8, 11, 15, 2, 6, 3, 12 }. Show the array after constructing a BinaryHeap from the array using the pushUp method.

12 points

9. Write a method to return a String listing the nodes of a binary tree along with depth of the node. For example, given the tree

A

/ \

B C

/ \ / \

D E F

/ \ / \ / \

G

/ \

The output could be A,0 B,1 D,2 C,1 E,2 G,3 F,2 . The nodes can appear in any order.