Computer Science II - Juniata College



Spring ‘03

April 2, 2003

Name_____________________________

1. Linked lists.

a) Fill in the Java inner class below to support the implementation of a linked list in which each node holds one String and a next reference.

[5 pts]

private class Node {

private _______ info;

private _______ next;

private Node(String s){

info = _______;

_________ = ________;

}

}

b) Indicate how the head pointer instance variable of the linked list is declared and start as the empty list. The linked list starts with a dummy head node.

[4 pts]

___________ head = new _______________________;

c) Draw a box and pointer diagram to represent the ordered list (“cat”, “dog”, “fish”) as pointed to by head. The linked list starts with a dummy head node.

[5 pts]

d) Fill in the blanks so that Java code that would add the value “ant” as a new first node of this ordered list.

[5 pts]

Node temp = new Node (“ant”);

temp. _______ = _______ . ________;

head.______ = ______ ;

2. Fill in the code below to complete the enqueue operation using a singly linked list implementation (no dummy head node).

[5 pts]

public void enqueue(Object item){

if (item == null)

throw new IllegalArgumentException

("Trying to insert null onto the queue");

Node node = new Node (______);

if (size == 0){

head = _________;

} else {

tail._______ = _______;

}

tail = node;

size_____;

}

3. Give the time complexities, O(1) or O(n) for each of the operations of the implied data structure that are implemented as a linked list.

[8 pts]

_________ pop()

_________ dequeue()

_________ enqueue(item)

_________ push(item)

_________ insert(item) //into a sorted list

_________ insert(item) //unsorted list

_________ getNextItem()

_________ isThere(item)

4. Fill in the blanks to implement a recursive binary search algorithm. Assume there is a public helper function that calls the recursive function:

public int binarySearch(Comparable key){

return binarySearch(key, 0, vec.length – 1);

}

[10 pts]

private int binarySearch(Comparable key, int lo, int hi){

if( ____ > ____ ) {

return -1; //not found

} else {

int mid = ____________;

int comp = vec[mid].compareTo(key);

if(comp > 0){

return binarySearch(key, ________,________);

} else if(comp ____ 0){

return binarySearch(key, ________,________);

} else { // found it

return ________ ;

}

}

}

5. A recursive definition for determining the greatest common denominator is credited to Euclid. For example,

the GCD of 16 and 12 is 4.

If b==0 then the GCD(a,b) = a,

otherwise the GCD (a,b) = GCD (b, a%b) //% is modulus

[10 pts]

Write this recursive Java function to implement the calculation of the greatest common denomionator.

public static int GCD(int a, int b){

}

6. Trees.

[10 pts]

a) Assume the root is at level 0. What is the level of node F? ____

b) Circle the largest subtree that is a binary tree.

c) How many leaves are there in the whole tree? _____

d) If each node could have at most three children, how many nodes total could be stored in this tree without adding any more levels? ______

e) List the ancestors of node H ______________________

f) List the descendants of node C. _______________________

g) Draw the conversion of this general tree as a binary tree (left child as first child of the general tree and right child as a sibling in the general tree)

7. Assume nodes in a binary tree are defined in an inner class having the following instance variables.

Comparable info;

BSTNode left;

BSTNode right;

a) Finish the recursive Java function to count the number of nodes in a binary tree. The algorithm works as follows. If the root (of tree or subtree) is null then return 0; otherwise return the sum of the nodes on the left and the nodes on the right, plus one for the root.

[7 pts]

public int Counter( _________ curNode)

{

if(curNode _____________ ) return ____ ;

return Counter ( _________________ )

+ __________ ( _________________ )

+ ____ ;

}

b) Finish the recursive Java function to return if the item exists in the binary search tree.

[8 pts]

public boolean isThere( BSTNode root, Comparable item)

{

if (_______ == null) return false;

int comp = pareTo( _________ . ___________)

if(comp == 0) return ___________ ;

if(comp < 0) return isThere ( ______ . ______ , item )

else return isThere (_______ . _______, item);

}

8. Create a binary search tree from the following character data entered into the bst left to right.

[4 pts]

D T W A B Q M N

a) List the nodes of your tree above from an inorder traversal.

[3 pts]

b) List the nodes of your tree above from a preorder traversal.

[3 pts]

9. Draw the following infix arithmetic expression as an expression tree. Represent precedence properly.

[4 pts]

(a+b)-c*(d+e)

a) Show a postorder traversal of your expression tree.

[3 pts]

10. True/False

[6 pts]

______ A doubly linked list permits traversal in both forward and backward directions

______ A doubly linked list doubles the algorithm complexity of the operations over a singly linked list.

______ Most operations on a binary tree depends on the depth of the tree which is logarithmic to its capacity.

______ A binary search tree always generates the same inorder traversal regardless of the sequence the nodes were entered into the tree.

______ A postorder traversal is the same as a reversed preorder travsersal.

______ The maximum number of nodes in a binary tree at level N is 2N

-----------------------

A

/ \

B C

/ \ \

D E F

/ \ /|\

G H I J K

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download