=========================preview======================
(COMP171)171midtermSpring05.pdf
Back to COMP171 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
Department of Computer Science
COMP 171 Data Structures and Algorithms
Spring 2005
Midterm Examination
Date: Saturday, April 2, 2005 Time: 14:30C16:30
.
You must attempt all questions. Your answers will be graded according to correctness, ef.ciency, precision and clarity.
.
This is a closed book, closed notes examination. You should put aside your calculators, cellphones, PDAs, Palms, etc.
.
This document has 12 single-sided pages, please check it.
.
You may use the reverse side of the pages for your rough work.
.
You cannot write your answers using a pencil, although you may use a pencil for rough work. Rough work will not be marked.
Student name: Student ID: Email address: Lecture section:
Question Score Maximum score
1 8
2 10
3 11
4 6
5 15
TOTAL 50
1. (8 marks) Heaps and binary search tree.
(a)
(1 mark) Does the following array represent a min-heap (Yes/No)? 0123 4 5 6 7 8
(b)
(3 marks) Given the following max-heap of size 10: 0 1 2 3 4 5 6789
Delete the maximum from the max-heap and give the resulting max heap:
(c)
(4 marks)
7 9 8 20 16 14 10 17 18
29 11 17 10 11 16 15 9 7 10
The following two sequences of keys (separated by blanks) are the output of the inorder and postorder traversals of a binary search tree. Draw this tree.
Inorder: BCDEGH
Postorder: DECHGB
2. (10 marks) Sorting
Consider sorting an unordered array A[0 ...n . 1] of distinct integers using mergesort. The
following algorithm is the merging routine used in mergesort.
Algorithm merge(A, p, q, r)
Input: Subarrays A[p..l] and A[q..r] s.t. p l = q . 1 <r and both subarrays are sorted in
increasing order.
Output: A[p..r] is sorted in increasing order.
(. T is a temporary array. .)
1.
k = p; i =0; l = q . 1;
2.
while p l and q r
3.
do if A[p] A[q]
4.
then T [i]= A[p]; i = i +1; p = p +1;
5.
else T [i]= A[q]; i = i +1; q = q +1;
6.
while p l
7.
do T [i]= A[p]; i = i +1; p = p +1;
8.
while q r
9.
do T [i]= A[q]; i = i +1; q = q +1;
10.
for i = k to r
11.
do A[i]= T [i . k];
(a)
(3 marks) Analyze the worst-case running time of the algorithm merge in terms of the lengths of A[p..l] and A[q..r].
(b)
(1 mark) Explain why mergesort may run slower than quicksort when the input array size is large.
(c)
(6 marks) Write down the pseudocode for a non-recursive version of mergesort. You may assume that the input size is a power of 2. Analyze the worst-case running time of your non-recursive mergesort using big Oh. (Show all steps.)
(contd)
3. (11 marks) Recursion Consider the following recursive program:
// x is an integer and n is any non-negative integer
int foo( int x, int n ){
if (n== 0)return1;
if (n%2==1){
y = foo(x,(n-1)/2);
return x*y*y;
}
else{
y = foo(x,