=========================preview======================
(COMP171)cs171mdf03.pdf
Back to COMP171 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
Department of Computer Science
COMP171: Data Structures and Algorithms
Fall 2003
Midterm Examination
Date: October 16th, 2003 Time: 7:00 C 8:30pm
Place: Rm 2407
. Your answers will be graded according to correctness, efficiency, precision and clarity.
. This is a closed book examination. You should put aside your calculators, mobile phones, PDAs, etc.
. This booklet has 11 singled-sided pages. Please check it.
. You may use the reverse side of the pages for your rough work.
Student name: KEY Student ID:
Students email address:
Tutorial Session: T1 Wed (Skiller) T2 Fri (Calvin)
Question
Score
Maximum Score
1
5
2
10
3
10
4
10
5
15
6
10
TOTAL
60
1. (5 marks)
Consider the following functions and loops.
int algorithm1(int n)
{
int sum = 0;
for(int i=0; i < n*n; i++)
for(int j=1; j < 3; j++)
sum++;
return sum;
}
int algorithm2(int n)
{
int sum = 0;
for(int i=0; i < n/2; i++)
sum++;
return sum;
}
int algorithm3(int n)
{
int sum = 0;
for(int i=n; i >= 2; i = i/2)
sum += algorithm2(i);
return sum;
}
int algorithm4(int n)
{
int sum=0;
for(int i=n; i >= 2; i=i/2)
sum += algorithm1(n);
}
Algorithm1() -> O(n2)
Algorithm2() -> O(n)
Algorithm3() -> O(nlogn)
Algorithm4() -> O(n2logn)
Give running time in Big Oh(..)? (1 mark each)
(a) int sum = algorithm4(n);
O(n2logn)
(b) int sum =0; for(int i=0; i < n; i++) algorithm3(i);
O(n2logn)
(c) int sum =0;
for(int i=0; i < 30; i++) for(int j=0; j < i; j++) for(int s=0; s < j; s++) for(int t=0; t < n; t++) sum++;
O(n)
(d) int sum=0; for(int i=1; i < n; i = i*2)
algorithm1(2);
O(logn)
(e) int sum=0; for(int i=0; i < n; i++)
{
sum += algorithm1(i);
sum += algorithm2(i);
}
O(n3)
2. (10 marks) HEAPS
(a) (5 marks) Using the following numbers, construct a valid max-heap in tree-format (i.e. draw the tree with the data in the nodes. Note, there is not a unique solution, but your result must be a valid max-heap).
14, 15, 8, 5, 19, 20, 12, 23, 2
(b) (5 marks) Given the following min-heap of size 10 (in array form):
0
1
2
3
4
5
6
7
8
9
5
10
15
12
13
37
16
18
14
19
Delete the minimum node and give the resulting min-heap:
0
1
2
3
4
5
6
7
8
10
12
15
14
13
37
16
18
19
3. (10 marks) Recursion
Consider the following recursive program.
// n is any positive integer