Computer Science II - Juniata College



November 11, 2005

Name_____________________________

1. Linked lists.

a) Draw a box and pointer diagram to represent the circular, ordered list (“cat”, “dog”, “fish”) as pointed to by head. The list must include a dummy head node.

[4 pts]

b) Show how the links above are rearranged to insert the node “bear” into the list.

c) Supply the declarations and assignment statements in the Java LList class below to support the implementation of the circular linked list in which each node holds one String item and a next reference.

[12 pts]

public class CLList

protected class Node { //inner class

_________________________________

__________________________________

protected Node(String s){//constructor

______________________________

______________________________

}//end constructor

}//end Node inner class

// define and initialize the head pointer

_____________________________________

public CLList(){

__________________________________

__________________________________

}//end constructor

}

d) Write a complete lengthIs() method that would traverse the list and count the real data nodes.

[5 pts]

public int lengthIs(){

e) Write a complete delete method to walk the list and delete the item from the list. It returns true if it was able to delete, false if the item was not found.

[10 pts]

public boolean delete(String s){

Node last = ___________________;

Node temp = ___________________;

while (_________ != ___________) {

if ( s.equals (___________________)){

last . ____________ = ___________ . __________;

return ___________ ;

}

last = ___________;

temp = __________ . _________ ;

}

return _________;

}

2. Assume the linked list class above was extended to implement a queue. Complete the enqueue and dequeue routines below.

[12 pts]

public class CLLQueue extends CLList

{

// the head node of the list serves as front pointer

Private Node rear; // serves as rear pointer; starts at head node

public void enqueue(String s){

}

public String dequeue(){

if(__________________________)

throw new QueueUnderflowException(“_________________”);

//and handle dequeuing of the last element in queue

}

}

3. Fill in the blanks to implement a recursive linked list algorithm that returns a concatenated string of the items in reverse order. The public helper function that calls the recursive function is given:

public String Reverse(){

return Reverse(head.next);

}

[7 pts]

private Reverse(Node cur){

if( __________ == null){

return ___________ ;

}

return ______________________________________

+ “ “ + ________________________________________;

}

4. Trees. Answer a-g based on the tree on the right.

[12 pts]

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

b) Which node is the root of the largest subtree that is a binary tree? _____

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

d) If each node is limited to three children, how many nodes could be stored in this (ternary) tree at level 3? ______

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)

5. Assume nodes in a binary tree are defined in an inner class having the following instance variables. There are two fields of data: info and weight. The field weight can be used to hold various numeric information about the node’s descendants. The weight field does not affect node placement in the BST; only the info field controls node placement.

Comparable info;

int weight; //positive only

BSTNode left;

BSTNode right;

Finish the recursive Java function to find the largest value of the weight fields in the binary tree. The algorithm works as follows. If the root (of tree or subtree) is null then return 0; otherwise return the largest weight of the nodes in the left subtree or the largest in the right subtree.

[11 pts]

public int maxWeight( _________ curNode)

{

if(curNode _____ ________ ) return ____ ;

int left = maxWeight ( _________________ );

int right = __________ ( _________________ );

if ( ________ > ________ ) return __________;

else return ____________;

}

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

[4 pts]

T E C H N I C A L

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

[3 pts]

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

[3 pts]

7. Below is a simple expression grammar. Use repeated replacements starting with expr to arrive at the given input expression to verify that it is legal. That is, replace occurrences of left-hand non-terminals with the right hand rules. The derivation is started. Order of replacements is not important

[7 pts]

b *(d+e)

expr := term

expr := expr addOp term expr -> term -> term multOp factor ->

term := factor

term := term multOp factor term * factor -> factor * factor ->

factor := var

factor := "(" expr ")"

addOp := "+" | "-"

multOp := "*" | "/" | "%"

var := "a" | "b" | "c" | "d" | "e"

8. Give the complexities, linear, logarithmic or constant for each of the operations of the implied data structure that are implemented as a linked list (LL) or BST.

[10 pts]

_________ (LL) delete(item)

_________ (LL) push(item)

_________ (LL) dequeue()

_________ (LL) enqueue(item)

_________ (LL) insert(item) //unsorted list

_________ (LL) insert(item) //into a sorted list

_________ (LL) isThere(item)

_________ (LL) getNextItem()

_________ (BST) insert(item)

_________ (BST) isThere(item)

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

A

/ \

B C

/|\ \

D X E F

/|\ / \

G H I I J

/ \

K L

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

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

Google Online Preview   Download