=========================preview======================
(comp152)[2010](s)wa~1907^sol_10148.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) 1010
(b)
114

(c)
It outputs the number n to the base m.


2.
Name the two stacks as E and D, for we will enqueue into E and dequeue from D. To implement enqueue(e), simplycall E.push(e). To implement dequeue(), simplycall D.pop(), provided thatD is not empty. If D is empty, iteratively pop every element from E and push it onto D, until E is empty, and then call D.pop().

3.
This can be done similar to an insertion sort. For each element in the array, keep popping the top element from S to Temp stack until the top one is larger or equal to the element. Push the element into the stack S. Keep popping the elements in Temp and pushing them back to S.

After all the elements in the array are scanned and pushed this way, the stack S has the elements sorted in increasing order from the top.

4.
We .rst sort the arrays A and B independently using afast sorting algorithm(say, mergesort orQuicksort).


(a) Thealgorithmfor .nding theintersectionisasfollows(similartothemerging steps in mergesort): Step 1. Put two pointers, pointer A and pointer B, at the head of array A and list B, respectively. Step 2. If either of the pointers points beyond the array, exit. Step3. Otherwise,ifthe numberstheypoint to are the same, report the number once. Advance both pointers. Repeat Step 2.
Step4. Ifthe numbers are not the same, report the smaller element and advance the corresponding pointer. Repeat step 2.
(b) Thealgorithmfor .nding theunionisasfollows(similartothemerging stepsin mergesort): Step 1. Put two pointers, pointer A and pointer B, at the head of the array A and array B, respectively. Step 2. If either of the pointer points beyond the array, report all the elements pointed to by the other pointer. Step 3. Otherwise, if the numbers they point to are the same, report once the number they point to. Advance both pointers. Repeat Step 2.
Step4. Ifthe numbers are not the same, report the smaller number andadvance the pointer. Repeat step 2.
5. (a) Preorder: 5, 4, 2, 1, 9, 6 Inorder: 4, 2, 5, 9, 1, 6 Postorder: 2, 4, 9, 6, 1, 5
(b)


Postorder: 3, 4, 6, 1, 2, 5, 8
(c)
Suppose T is the corresponding binary tree to be determined. Let P, I be the given preorder and inorder traverval sequences for T respectively. Observe that the .rst element v of P is the root of T . Locate the v in I by doing linear search from left to right. Suppose I1 ,I2 are all elements in I at the left and right of v respectively. Then we know that I1 ,I2 should be the inorder traversal sequences of the left subtree T1 and right subtree T2 of the root v respectively. Let l = |I1 | and r = |I2 |. Set P1 be the l subsequent elements following v in P , and set P2 be the remaining r elements following P1 in P . Then we know that P1 ,P2 shouldbe the preorder traversal sequences of T1 ,T2 respectiv