Computer Science II - Juniata College



Spring ‘05

April 8, 2005

Name_____________________________

1. Linked lists.

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

[4 pts]

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

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

[12 pts]

public class LList

private class Node {

_________________________________

__________________________________

private Node(String s){

______________________________

______________________________

}//end constructor

}//end Node inner class

// define and initialize the head pointer

______________________________

public LList(){

__________________________________

}//end constructor

}

d) Write a complete toString() method that would traverse the list and concatenate the strings together and separate them with ‘\n’

[5 pts]

2. Assume the linked list class above was extended to implement a stack. Complete the push and pop routines below.

[10 pts]

public class LLStack extends LList

{

// the head of the list serves as top

public void push(String s){

}

public String pop(){

if(______________________)

throw new StackUnderflowException(“_________________”);

}

}

3. Fill in the blanks to implement a recursive linked list (sorted) search algorithm. In this case the value to be searched can be a leading substring of the stored string. The null value is return if there’s no match. The public helper function that calls the recursive function is given:

public Listable LLSearch(String substr){

return LLSearch(substr, head);

}

[11 pts]

private Listable LLSearch(String substr, Node cur){

if( __________ == null ||

_______.compareTo(_________.item) ____ 0 ) {

return null; //not found

} else {

if ( cur.______.startsWith( _________ ) ){

return ___________.________ ;

} else { // keep looking

return LLSearch(_________ , ________.________);

}

}

}

4. Write a recursive method to print the contents of the linked list (not the stack) in reverse order.

[8 pts]

public void printRev(){

printRevRec(head);

}

private void printRevRec(Node node){

}

5. Trees.

[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 smallest subtree that is not a binary tree? _____

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

d) If each node is limited to two children, how many nodes total could be stored in this (binary) tree without adding any more levels? ______

e) List the ancestors of node M ______________________

f) List the descendants of node B. _______________________

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)

6. 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;

BSTNode left;

BSTNode right;

Finish the recursive Java function to set the weight field to the number of descendents of each node in a binary tree. The algorithm works as follows. If the root (of tree or subtree) is null then return 0; otherwise get the number of the nodes in the left subtree and in the right subtree, add them, store the sum in the root of the subtree, and return that value.

[11 pts]

public int setWeight( _________ curNode)

{

if(curNode _____ ________ ) return ____ ;

int sum = setWeight ( _________________ )

+ __________ ( _________________ );

___________.__________ = sum;

return ______;

}

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

[4 pts]

O R G A N I Z E

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]

8. 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, i.e, the postfix equivalent of the expression.

[3 pts]

9. 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) dequeue()

_________ (LL) enqueue(item)

_________ (LL) pop()

_________ (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 E F

/|\ /|\

G H I I J K

/ \

L M

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

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

Google Online Preview   Download