Algorithm

Questions about the exam questions will not be answered during the test.
For the binary tree related questions on this exam you may assume that this generic class has been
defined for your use and is included. When the term Btnode is used on the exam it is referring to
this generic class.
class Btnode
{ /* this generic class models a node of a binary tree */
/* here are the private data members of the binary tree node */
private T element;
private Btnode left;
private Btnode right;
/* the constructor given an Object,left child,and right child. */
Btnode(T theElement, Btnode lt, Btnode rt )
{ element = theElement;
left = lt;
right = rt;
}
/* here are the public get/set methods for the data members */
public T getElement( ){ return element;}
public Btnode getLeft( ) {return left;}
public Btnode getRight( ){return right;}
public void setElement( T x ){element = x;}
public void setLeft( Btnode t ) {left = t;}
public void setRight( Btnode t ){right = t;}
}



Question 1 - Multiple Choice. [2 pts. each - 18 pts total] For each of the following
subparts, circle the best or all correct answers as indicated.
A. The linear probe method for hash tables suffers from the phenomenon known as
i. fatal collisions
ii. sparse distribution
iii. clustering
iv. broken chains
v. none of the above
B. Which of the following sorting algorithms have a worst case performance that is better than O(n*n)?
i) selection
ii) bubble
iii) insertion
iv) shell
v) merge
vi) heapsort
vii) quicksort
C. Which tree below corresponds to the vector v created by the code below?
int arr[ 8 ] = {3, 15, 12, 4, 67, 6, 55, 9};
Vector v = new Vector (8);
for (int i=0; i< 8; i++) { v.addElement(arr[i]); }





D. Which of the following are true of sets?
i. A set with no elements in it is called an empty set
ii. Each element (ie, value) in a set is distinct
iii. The universal set is that which contains all the values of the base type
iv. The cardinality of a set denotes the number of elements in a set
v. New sets can be created by the union, intersection and difference operations
vi. The elements of a set are not ordered
E. Which of the following are true of heaps ?
i. It is a binary tree
ii. In terms of its shape, it must be complete
iii. It can be either a maximal or a minimal heap
iv. The value of the root has no relationship to the value of any other nodes
v. Is useful for implementing a stack
vi. Is the most efficient representation for a priority queue
F. Hashing is an ______ search algorithm.
(i) O(log2n) (ii) O(n2) (iii) O(n) (iv) O(1)
G. What is the value of the postfix expression 6 3 4 5 + * +
i) 10
ii) 0
iii) 25
iv) 33
v) none of the above
H. Given three arrays with L, M and N elements respectively, estimate the running time for the
following algorithm in terms of the number of times that the pairwise comparison step is executed:
repeat the following for i from 1 to L for array1
repeat the following for j from 1 to M for array2
repeat the following for k from 1 to N for array3
pairwise compare array1[i], array2 [j] and array3 [k] and based on the result do one the following
case 1: if array1[i] and array2 [j] are equal then { do something 1}
case 2: if array1[i] and array3 [k] are equal then { do something 2}
case 3: if array3[k] and array2 [j] are equal then { do something 3}
end repeat
end repeat
end repeat
i. O ( log 2 (L+M+N) )
ii. O ( N 3 )
iii. O ( L * M * N )
iv. None of the above


I. If the characters ‘A’, ‘D’, ‘C’, ‘B’ are put into a queue (in that order), and then retrieved one by one,
what will be the order in which they are removed?
i) ABCD
ii) DCBA
iii) BCDA
iv) ADCB
Question 2. Evaluation. (2 points each = 6 pts. total) For each of the following code segments,
write in the value of the variable x after the Java statements are executed. You may assume that the
proper import statements have already appeared.
A. ______________ Vector alist = new Vector ( );
alist.add (40);
alist.add (10);
alist.add (20);
alist.add (8);
int x = alist.get(0 ) * alist.get( 3) ;
B. ______________ Stack intStack = new Stack ( );
intStack.push (6);
intStack.push (5);
intStack.push (11 + intStack.peek ( ));
int y = intStack.peek ( ) ;
intStack.pop ( ) ;
int x = y + intStack.peek ( ) ;
C. ______________ int array [ ] = {0,1,2,3,4,5,6,7,8,9};
Queue s = new LinkedList ( );
for (int i = 0; i < 10; i++) s.add (array [ i ]);
s.remove ( );
int x = s.peek ( ) + array [7];
// hint: from the ADT for queue: add is enqueue, remove is dequeue, peek is front


3. Tree questions (20 pts)
A.(7 pts) For each subpart (a) – (g), use the following tree.



(a) What is the parent of node 5? ___________________
(b) What is the depth of this tree? ____________________
(c) List the nodes in subtree 12. ___________________________
(d) List all of the non leaf nodes. ______________________________
(e) Give the order that the nodes are visited in a preorder traversal of the tree.
____________________________________________________________
(f) Give the order that the nodes are visited in an inorder traversal of the tree.
____________________________________________________________
(g) List all of the nodes at level 2 in the tree. _______________________________
B. (2 pts) Draw the tree created by the following statements. Btnode is defined on page 1.
Btnode root, a, b, c, d;
d = new Btnode (6, NULL, NULL);
c = new Btnode (9, d, NULL);
b = new Btnode (4, NULL, c);
a = new Btnode (12, NULL, NULL);
root = new Btnode (10, a, b);
C. (3 pts) Trace the method count() below and describe what it does
public static int count (Btnode t)
{ int ctLeft, ctRight, ct;
if (t == NULL)
ct = 0;
else
{ ctLeft = count(t.getLeft());
ctRight= count(t.getRight());
boolean flag = (t.getLeft()!= NULL && t.getRight()!= NULL);
ct = ctLeft + ctRight + (int)flag;
}
return ct;
}


D. (3 pts) Use the following tree traversal function. Assuming m is initially 0, what is the resultant value of m when
calling this method as f ( Btnode root, m) where root is the base of the tree in Question 3A?
_____________________________
public static void f(Btnode t, int n)
{ if (t != NULL)
{ n++;
f(t.getLeft(), n);
f(t.getRight(), n);
}
return;
}
E. (5 pts) Consider the following binary search tree. Use the original tree below when answering each subpart (a)
through (e).




(a) If the value 46 is inserted into this tree, which node becomes its parent? __________________
(b) If the value 64 is inserted into this tree, which node becomes its parent? ___________________
(c) If we delete node 65, which node should be its replacement node? ___________________
(d) If we delete node 90, which node should be its replacement node? __________________
(e) If we delete the root node 50, which node should be selected as its replacement node so that the fewest number
of changes are made to the tree? ______________________


4. Heaps and Graphs (19 pts)
A. (3 pts) A heap can be represented by a vector. Start with the following heap and list the elements after each operation.
Execute the operations sequentially, using the result of the previous operation. The initial vector values for the heap
are {50, 35, 15, 12, 3, 5}.