=========================preview======================
(COMP171)comp171mds04_gary.pdf
Back to COMP171 Login to download
======================================================
THEHONGKONGUNIVERSITYOFSCIENCE&TECHNOLOGY DepartmentofComputerScience
COMP171,L1:DataStructuresandAlgorithms Spring2004
MidtermExamination
GaryChan
Date:Saturday,March27,2004 Time:14:00{16:00 Place:LTA
Youranswerswillbegradedaccordingtocorrectness,e.ciency,precisionandclarity. Thisisaclosedbookexamination.Pleaseputasideyourcalculators,cellphones,PDAs,etc. Thisbooklethas14pages,pleasecheckit.
Studentname: EnglishNickname(ifany): StudentID: Emailaddress:
Ididnotcheatinthisexamination:




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)(4marks)SupposeA.f56122481621g.Whatistheoutputoffun(A,0,7).
(b)(4marks)SupposeA.f11111111g.Whatistheoutputoffun(A,0,7).
2

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








14
28
9
22
19
24
36
Youneedtosorttheelementsinincreasingorderusingheapsortwithoutincurringanyextra storageproportionaltothesizeofthearray(i.e.,in-placeheapsort).Tracetheoperationof heapsortbyshowingthearraycontentaftereachstep.
(4points)Aftertheinitializationstep(i.e.,themaxheaprepresentationofthearraynumbers):
0123456

(4points)Afterthe1ststepandheaprebuilding(i.e.,1numbersorted): 0123456








(3points)Afterthe2ndstepandheaprebuilding(i.e.,2numbersorted): 0123456








(3points)Afterthe3rdstepandheaprebuilding(i.e.,3numberssorted): 012345
6








(2points)Afterthe4thstepandheaprebuilding(i.e.,4numberssorted): 0123456








(2points)Afterthe5thstepandheaprebuilding(i.e.,5numberssorted): 0123456








(2points)Afterthe6thstepandheaprebuilding(i.e.,6numberssorted): 012345
6








3.StacksandQueues(20marks) Thisquestionisrelatedtostacksandqueues.
(a)(12points)DescribehowtoimplementstackADTofpushandpopusingtwoqueues
labeledasQandQ.
12
(b)(8points)Analyzetheworst-caserunningtimeinbig-Ohofnpushesandnpops,exe-cutedinanyorder.
4.RankSearching(20marks)
Youaregivenanarrayaofndistinctnumbers.Notethatamaynotbesorted.
(a)(5points)Youaregivenanumberxwhichisoneoftheelementsinthearraya. i.(3points)Describeanalgorithmwhich.ndstherankofxina.Youralgorithm mustruninO(n)intheworstcase.
ii.(2points)ArguewhyyouralgorithmrunsinO(n)intheworstcase.
(b)(15points)Supposenowyouaregivenkdistinctnumbersoutofthearraya(kn). Thesenumbersarestoredinanotherarrayb.Notethatbmaynotbesorted.Foreach oftheelementsinb,youneedto.nditsrankinthearraya.
i.(9points)Describeane.cientalgorithmtoachievethat.Notethatyouwillbe gradedaccordingtothee.ciencyofthealgorithm.
ii.(6points)Analyzetheworst-caserunningtimeinbig-Ohofyouralg