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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- igcse computer science workbooks pdf
- igcse computer science workbook
- igcse computer science workbook answer
- igcse computer science coursebook pdf
- computer science people
- what is computer science like
- computer science revision
- igcse computer science revision notes
- college computer science project ideas
- ideas for computer science project
- computer science projects for students
- computer science final project