=========================preview======================
(COMP171)comp171mds04_cloud.pdf
Back to COMP171 Login to download
======================================================
THEHONGKONGUNIVERSITYOFSCIENCE&TECHNOLOGY DepartmentofComputerScience
COMP171,L2:DataStructuresandAlgorithms Spring2004
MidtermExamination
Ka-WoLau
Date:Saturday,March27,2004 Time:14:00{16:00 Place:Room2304,2306,2407
Youranswerswillbegradedaccordingtocorrectness,e.ciency,precisionandclarity. Thisisaclosedbookexamination.Pleaseputasideyourcalculators,cellphones,PDAs,etc. Thisbooklethas13pages,pleasecheckit.
Studentname: StudentID: Emailaddress:
Ididnotcheatinthisexamination(yoursignature):




Problem
Mark
Maximum
1
15
2
20
3
20
4
20
5
25




Total
100
1.Recursion(15marks)
Considerthefollowingrecursiveprogram:
intfun(intA[],intp,intr){
if(p..r)
returnr.

else{
intm.(p+r)/2.
inti.fun(A,p,m).
intj.fun(A,m+1,r).

if(A[i]..A[j]) returni. elsereturnj. } }
(a)(4points)SupposeA.f56122481621g.Whatistheoutputoffun(A,0,7).
(b)(4points)SupposeA.f11111111g.Whatistheoutputoffun(A,0,7).
2

(c)(3points)Whatdoestheprogramdo.
(d)(4points)LetnbethearraysizeofAwhenfunis.rstcalled.Analyzetheworst-case runningtimeoftheprograminbig-Oh.
2.Heap-Sort(20marks) Youaregivenanarrayof7integers 0123456








14
28
9
22
19
24
36
Youneedtosorttheelementsusingheapsort.Tracetheoperationofheapsortbyshowing thearraycontentaftereachstep. (4points)Afterconvertingtheinputarraytoaninitialmin-heap:
0123456








(4points)Afterthe1stdeleteMinstepandtheheappropertyisrestored: 0123456








(3points)Afterthe2nddeleteMinstepandtheheappropertyisrestored: 0123456








(3points)Afterthe3rddeleteMinstepandtheheappropertyisrestored: 012345
6








(2points)Afterthe4thdeleteMinstepandtheheappropertyisrestored: 0123456








(2points)Afterthe5thdeleteMinstepandtheheappropertyisrestored: 0123456








(2points)Afterthe6thdeleteMinstepandtheheappropertyisrestored: 012345
6








3.StacksandQueues(20marks) Thisquestionisrelatedtostacksandqueues.
(a)(12points)DescribehowtoimplementstackADTofpushandpopusingtwoqueues
labelledasQandQ.
12
(b)(8points)Analyzetheworst-caserunningtimeinbig-Ohofnpushesandnpops,exe-cutedinanyorder.
4.Ranking(20marks)
Youaregivenanarrayaofndistinctnumbers.Notethatamaynotbesorted.
(a)(5points)Youaregivenanumberxwhichisoneoftheelementsinthearraya. i.(3points)Describeanalgorithmwhich.ndstherankofxina.Youralgorithm mustruninO(n)intheworstcase.
ii.(2points)ArguewhyyouralgorithmrunsinO(n)intheworstcase.
(b)(15points)(Ifyouralgorithmisnote.cient,youwillNOTgetfullcredit.) Supposenowyouaregivenkdistinctnumbersoutofthearraya(kn)(i.e.,allk numbersareina).Thesenumbersarestoredinanotherarrayb.Notethatbmaynot besorted.Foreachoftheelementsinb,youneedto.nditsrankinthearraya.
i.(9points)Describeane.cientalgorithmtoachievethat.
ii.(6points)Analyzetheworst-caserunningtimeinbig-Ohofyouralgorithminterms ofnandk.
5.BinaryTree(25marks)
Thisquestionisabouttherelationsofpreorder,inorder,andpostor