Spring ‘10 CS 240 Computer Science II Exam 3 Page 1
April 12, 2010
Name______
1. . For each data structure in the table, list all the characteristics or properties that match that structure. Use the letters A through E.
[10 pts]
A=Linear structure B=LIFO C=Log time search
D=Sequential access only E=Log time insertion
Stack /
Sorted array /
Binary Search Tree /
2. True/False on queues.
[5 pts]
______The queue ADT restricts insertion at the front and deletion from the rear.
______A bounded queue limits the number of objects enqueued at any given time.
______An unbounded queue can be implemented as a doubly linked list.
______Queues are a more general form of stacks and can be used interchangably in most applications.
______In a bounded, but circular, queue the front index is always greater than the rear index.
3. Fill in the blanks below, including the comment, for the enqueue operation in a bounded queue implementation.
[10 pts]
public Object dequeue()
{
if (______()) {
______new QueueUnderflowException("Dequeue failed on empty queue");
}
Object temp = queue[______];
queue[______] = null; //because______
front = (______+ 1) ____ queue.length;
numElements ______;
return ______;
}
}
4. Fill in the blanks below to complete a binary search function on a “full” array of Comparable object which returns the position of the search object in the array. If not found, -1 is returned.
[15 pts]
public static Comparable binSearch(Comparable vec[],Comparable skey)
{
int lo = _____ ;
int hi = vec.______- 1;
while (lo ____ hi){
int mid = (______+ ______) / ___;
int cmp = skey . ______vec [ _____ ];
if (cmp ____ 0 ){
hi = mid ______;
} else if (cmp _____ 0){
lo = mid ______;
} else
return ______;
}
}
5. Fill in the blanks to implement a recursive algorithm to print (to System.out) a linked list in reverse order and return the length of the list. The list holds strings. The public helper function that calls the recursive function is given:
[9 pts]
public int LLPrintRev(){
return LLPrintRev(head);
}
private int LLPrintRev(LLNode cur){
if( ______== ______) {//base case: end of list or empty
return ______;
}
int count = LLPrintRev( ______.getLink()) + ____;
______( ______.getInfo() );
return ______;
}
}
}
6. Trees. Answer the questions based on the tree to the right.
[12 pts]
a) Assume the root is at level 0. What is the level of node H? ____
b) Which node is the root of a subtree that is not a binary tree? _____
c) If each node is limited to two children, how many nodes total could be stored in this (binary) tree without adding any more levels? ______
d) How many leaves are there in this tree? _____
e) List the ancestors of node M ______
f) List the descendants of node F. ______
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 search tree are defined in a class having the following instance variables. There are two fields of data: name and phone. The phone field does not affect node placement in the BST; only the name field controls node placement. A missing phone number is indicated by an empty string.
String name; //accessed by getName()
String phone; //accessed by getPhone()
BSTNode left; //accessed by getLeft()
BSTNode right;//accessed by getRight()
Finish the Java method to return the phone found in the node of a BST, given a name string.
[10 pts]
public String findPhone(String searchName)
{
BSTNode cur = root;
while(______null ){
int cmp = searchName.______( cur.______);
if(cmp == _____) {
return cur .______;
else if (cmp ___ 0){
_____ = cur. ______;
else
_____ = cur. ______;
}
return ______; //appropriate value to flag failure of search,
//but note not everyone has a phone number
}
8. Create a binary search tree from the following character data entered into the BST left to right.
[5 pts]
C O M P A T I B L E
a) List the nodes of your tree above from a postorder traversal.
[4 pts]
b) List the nodes of your tree above from an inorder traversal.
[4 pts]
9. Give the big-O complexities, linear, logarithmic or constant for each of the operations for these data structures: unordered linked list (LL), unordered array (Array), or BST.
[10 pts]
CS 240 Computer Science II Exam 3 Page 5
______(LL) insert()
______(LL) traverse() //visit all elements
______(BST) traverse()
______(Array) traverse()
______(LL) delete(item)
______(BST) insert(item)
______(Array) insert(item)
______(Array) isThere(item)
______(BST) insert(item)
______(BST) delete(item)
CS 240 Computer Science II Exam 3 Page 5
10. Show the order of pixels filled in the 6x10 pixel array according to Fill routine shown below. Use a,b,c,d,e, etc. for the order of pixels. ‘a’ designates the starting pixel. Note carefully the order of the recursive calls.
[6 pts]
* * * * * * * * * *
* * * *
* * * * * * *
* * * * a *
* * * * *
* * * * * * * * * *
public static void Fill( PixMatrix pixels, RowRange row, ColRange col, Color paintColor )
{
if (pixels[row][col] == paintColor) return;
if (pixels[row][col] == BOUNDARY_COLOR) return;//’*’ is BOUNDARY_COLOR
pixels[row][col] = paintColor;
if(col < RIGHT_COL) Fill(pixels, row, col+1, paintColor);
if(row < BOT_ROW) Fill(pixels, row+1, col, paintColor);
if(col > LEFT_COL) Fill(pixels, row, col-1, paintColor);
if(row > TOP_ROW) Fill(pixels, row-1, col, paintColor);
}