=========================preview======================
(COMP152)[2010](f)quiz~2385^_10043.pdf
Back to COMP152 Login to download
======================================================
The Hong Kong University of Science & Technology Department of Computer Science
COMP 152: OOP and Data Structures
Written Assignment (Solutions)

1. (a) (2 points) The printouts are 0333. The returned value is false.
(b) (2 points) If the returned value is true, it means that x is found in the sorted array A; otherwise, it means that x is not in A.
2. (8 points) To implement the Stack ADT using two queues, Q1 and Q2, we can simply
enqueue elements into Q1 whenever a push call is made. For pop calls, we can dequeue all elements of Q1 and enqueue them into Q2 except for the last element which we set aside in a temp variable. We then return the elements to Q1 by dequeing from Q2 and enqueing into Q1. The last element that we set aside earlier is then returned as the result of the pop.
Note: The students may simply return the last element in Q1 and in the following operations, the roles of Q1 and Q2 would be swapped.
3. (a) (3 points) The path is 7 6 1 5 0.
(b) // output the nodes from the starting point to w
(6 points)
Path(w){

int v =w;
push( w ); // push the destination first
while( (v = Pred[ v ]) != -1)
push( v );

push( v ); // push the source/starting point
while( (v = pop()) != EMPTY )
output v;
}

4. (14 points)
Step 1. Initialize the stack. Read in the in.x expression.
Step 2. Get one character from the expression
Step 3. If it is a variable (operand), write it out. Repeat Step 2.
Step4. Ifitisa (, push it into the stack. Repeat Step 2.
Step5. Ifitisa ), pop from the stack all the way to ), writing out all the operators

in sequence (do not write out ( and )). Repeat Step 2. Step6. Ifitisa -or +, keep popping the stack if its operator is +, -, ^, or * and write them out in sequence. Push the new operator into the stack. Repeat Step 2.
Step7. Ifitisa *, keep popping the stack if its operator is ^ or *. Push the new * into the stack. Repeat Step 2. Step8. Ifitisa ^, push it into the stack. Repeat Step 2. Step 9. If it is a null character (end of line), pop and write out all the operators in the stack.
5. (a) (3 points) It is not possible for the postorder and preorder traversal of a tree with more than one node to visit the nodes in the same order. It is because a preorder traversal will always visit the root node .rst, while a postorder traversal node will always visit an external node .rst.
(b) (2 points) It is possible for a preorder and a postorder traversal to visit the nodes in the reverse order. Consider the case of a tree with only two nodes.
6. (a) (8 points)
fill_height(x)
{
if (x != NULL)

{
fill_height(left(x));
fill_height(right(x));
if (left(x) == NULL)

L= 0;
else
L = height(left(x));
if (right(x) == NULL)
R= 0;
else
R = height(right(x));
height(x) = max(L,R) + 1;
}
}

The above recursive procedure is basically a postorder traversal of the binary search tree.
(b) (6 points)
path(x)
{
if (x != NULL)

{
output the key stored at x;