=========================preview======================
(COMP171)cs171mt2003.pdf
Back to COMP171 Login to download
======================================================
THEHONGKONGUNIVERSITYOFSCIENCE&TECHNOLOGY DepartmentofComputerScience
COMP171,L4:DataStructuresandAlgorithms Spring2003
MidtermExamination
GaryChan
Date:Saturday,March22,2003 Time:15:30{17:30 Place:LTA
Youranswerswillbegradedaccordingtocorrectness,e.ciency,precisionandclarity. Thisisaclosedbookexamination.Pleaseputasideyourcalculators,cellphones,PDAs,etc. Thisbooklethas11pages,pleasecheckit.
Studentname: Englishname:
StudentID: Emailaddress:
Problem
Mark
Maximum
1
10
2
15
3
20
4
10
5
10
Total
65
1.Recursion(10marks) Considerthefollowingrecursiveprocedure:
//nisanypositiveinteger
//misbetween2and9
voidfoo(intn,intm){
if(n.m)
cout..n.
else{
foo(n/m,m).
cout..n%m.
}
}
(a)(2marks)Whatistheoutputforfoo(10,2).
(b)(2marks)Whatistheoutputforfoo(34,5).
2
(c)(3marks)Whatdoestheproceduredo.
(d)(3marks)Analyzetheworst-caserunningtimeoftheprocedureintermsofbigoh.Your boundhastobetight.
2.Stacks(15marks) Considerthestandardarithmeticexpressions(in.xexpressions)withthefollowingcharacter-istics:
.Itisalegalin.xexpressionwithatmost100characters
.IthasFOURoperators:exponentiation(^),multiplication(*),addition(+),subtraction (-),andpossiblyparentheses(and)
.Ithasvariablestakenfromthesetfa.b.:::.zg
.Itcontainsnoblanks
Describeanalgorithmtoconvertanin.xexpressionintopost.xexpressionsusingastack. Youcanassumethatastackoperationsareprovided,sofurtherexplanationanddescription oftheseoperationsisnotneeded.
Hint:Notethatthefouroperatorscanbecategorizedintothreegroupsaccordingtotheiras-sociativity.LetA,B,CandDbeexpressionsthatareeithersinglevariablesorparenthesized expressions.
.Group1consistsonlyofthesubtractionoperatorsinceitistheonlyoperatorthatis leftassociativeandnotrightassociative.Thatis,A;B;Ccanonlybeevaluatedas (A;B);C.EvaluatingitasA;(B;C)isincorrect.
.Group2consistsonlyoftheexponentiationoperatorsinceitistheonlyoperatorthatis rightassociativeandnotleftassociative.Thatis,A^B^C^Dcanonlybeevaluatedas
A(B(CD))
.
.Group3consistsofthemultiplicationandadditionoperatorssincetheyarebothleft andrightassociative.
2.continued
3.Sorting(20marks) SupposethatAisanarraycontainingndistinctrealnumbers.Furthermore,Aisaconcate-nationofksubarraysA1,A2,:::.Ak,wherethevalueofkisunknownandthenumbers containedineverysubarrayAiarealreadyinascendingordescendingsortedorder.However, wedonotknowthesizeofeachsubarrayAi,andwedonotknowwhethereachAiisinin-creasingorderorindecreasingorder(weonlyknowthateachAiisinoneofthesetwosorted orders).NotethatthesizeofonesubarrayAimaydi.erlargelyfromthesizeofanother subarrayAj.Also,notethatkcanbeanyintegersuchthat1.k.n.
Answerthefollowingquestions:
(a)(6marks)Describeanalgorithmto.ndthearrayindexespiandqisuchthatAi. A[pi:::qi].
(b)(6marks)GiventhearrayAandanintegerk,describeanO(nlogk)timealgorithmto sortA.
(c)(5marks)Analyzetherunningtimeofyouralgorithm.Thatis,arguewhyyouralgorithm runsinO(nlogk)time.
(d)(3marks)Supposethatkisafunctio