=========================preview======================
(COMP171)2006springmidtermSol.pdf
Back to COMP171 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY Department of Computer Science
COMP171: Data Structures and Algorithms Spring 2006
Midterm Examination Solution
L1: Dr. QiangYANG L2: Dr. Albert CHUNG L3: Dr. Xin LI
1. Merge Sort and Insertion Sort (8 marks)
(a)
(4 marks)

(b)
D(4 marks)




2. Binary Tree (13 marks)

(a) (2 marks each).
(1)A B C D E;
(2)B D E C A;
(3)E D C B A.
(b) (7 marks).

3. Heap (10 marks)
(a) (1 mark for each insertion).
Table 1:












Index
1
2
3
4
5
6
7
8
9
10
Input array
5
8
11
16
3
46
75
23
12
89












Insert 5,8,11,16,3
16
11
8
5
3
X
X
X
X
X
Insert 46
46
11
16
5
3
8
X
X
X
X
Insert 75
75
11
46
5
3
8
16
X
X
X
Insert 23
75
23
46
11
3
8
16
5
X
X
Insert 12
75
23
46
12
3
8
16
5
11
X
Insert 89
89
75
46
12
23
8
16
5
11
3
(b) (1 mark for each deleteMax ).
Table 2:














Index
1
2
3
4
5
6
7
8
9
10
11
Array
100
89
23
6
5
11
7
4
2
3
1
deleteMax
89
8
23
6
5
11
7
4
2
3
1
deleteMax
23
8
11
6
5
1
7
4
2
3
89
deleteMax
11
8
7
6
5
1
3
4
2
23
89
deleteMax
8
6
7
4
5
1
3
2
11
23
89
deleteMax
7
6
3
4
5
1
2
8
11
23
89
4. Radix Sort (10 marks)
(a) (2.5 marks each).











pass1: 390
641
693
944
286
136
727
968
408
329











pass2: 408
727
329
136
641
944
968
286
390
693











pass3: 136
286
329
390
408
641
693
727
944
968
(b) (2.5 marks). Line 10: for p := 9 downto 0 OR Line 8: enqueue(A[i],Q[9.t]); OR Line 7: t := 9.(A[i]mod D)div (D/10);
(1.5 marks for answer, 1 mark for explanation).
5. Big-Oh (14 marks)

(a) (2 marks each) 1) D 2) B
3) D
4) C

(b) (6 marks)
T (n)=3T (n 3 )+1 n> 1(2 marks)
T (1)=1 (1 mark)
T (n) = 3T (n 3 )+1
n
=32 T (32 )+(1+3)
= ...
n
=3k T (3k )+(1+3+... +3k.1 ) n 3k .1
=3k T (3k )+2
= O(n)
(Becausen =3k .)
(1 mark for answer, 2 marks for steps).

6. Stack (10 marks)

(a) (4 marks) Z =(A + B)2 C + B =103.
(b) (1 mark for each blank)
Q1: i < cArraySize;
Q2: stack->push( ch );
Q3: stack->isEmpty();
Q4: ch2 = stack->pop();
Q5: !stack->isEmpty()
Q6: return true;

7. Linked List (12 marks)

(a) (2 marks for each blank)
Q1: head == NULL || head->next == NULL
Q2: p2->next = p1 ;
Q3: p2 = p3 ;
Q4: p2->next = p1 ;

(b) (2 marks for each blank)
Q5: head->next = MergeRecursive(head1->next,head2); Q6: head->next = MergeRecursive(head1,head2->next);
8. Recursion (11 marks)

(a) (4 marks)

Algorithm 1 SEARCH(Q8)

Main Routine: Call SEARCH(A, 1,n)

Function: SEARCH(A, p, r)
Return: true if there exists such an index,