哈工大深圳算法设计与分析08年试卷-何震宇

PageNo.1哈尔滨工业大学深圳研究生院2008年秋季学期期末考试试卷HITShenzhenGraduateSchoolExaminationPaperCourseName:Lecturer:QuestionOneTwoThreeFourFiveSixSevenEightNineTenTotalMarkGeneraldirections:Thisexamisclosedbook.Youmaynotusethetextbook,yournotes,computer,oranyothermaterialsduringtheexam.Nocreditwillbegivenforquestionsleftunanswered,soyoushouldbesuretoanswerallquestions,evenifyouareonlytakingyourbestguess.Writeyouranswertoeachquestionorprobleminthepaperprovided.Ifnecessary,extrasheetswillbeprovided.Makesureyournameiswrittenonallofthesepages.Pleasebesuretowriteneatlyandanswerallquestionsunambiguously.Thisexamhasatotalof_100_points,andyouhave120minutes.Time:09:00-11:00,Monday,Dec.8,2008错误!未找到引用源。Singlechoice[10points]1、Whichofthefollowingsortingalgorithmsisnotstable?(B)(A)Insertionsort(B)Quicksort(C)Mergesort(D)Bubblesort2、Wesaythat()fnisasymptoticallylargerthan()gnif(D).(A)()fnOgn(B)()fngn(C)()fnogn(D)()fngn3、Anorder-statistictreeisanaugmentedred-blacktree.Inadditiontoitsusualfields,eachnodexhasafieldsize[x],whichisthenumberofnodesinthesubtreerootedatx,Foranorder-statistictreewithnnodes,thetimeforinsertion,deletionandmaintenanceofthesizefieldare(A)(A)(lg)On(lg)On(lg)On(B)(lg)On(lg)On(lg)Onn(C)(lg)On(lg)On(1)O(D)(lg)On(lg)Onn()On4、There’saB-treewhoseminimumdegreeist,everynodeotherthantherootmusthaveatleast__keys,atmost__keys,everyinternalnodeotherthantheroothasatleast__children(D).(A)t-12tt(B)t-12t-1t(C)t2tt+1(D)t-12t+1t5、WhichofthefollowingstatementsaboutP,NP,NPCiscorrect?(C)(A)P=NP,NPCNP(B)PNP,NPCP(C)PNP,NPCNP(D)P=NPC,PNP错误!未找到引用源。shortanswer[30points]6、Considerinsertingthekeys10,22,31,4,15,28,17,88,59intoahashtableoflengthm=11usingopenaddressingwiththeprimaryhashfunctionh1(k)=kmodm.Illustratetheresultofinsertingthesekeysusinglinearprobing,usingquadraticprobingwithc1=1andc2=3.Thefinalresultsarerequiredtobeexpressedascharts.[6points]012345678910228841528175931107、Usethearithmeticexpression((a+b)+c*(d+e)+f)*(g+h)toconstructabinarytree.[6points]8、ExplainhowtoimplementtwostacksinonearrayA[1..n]insuchawaythatneitherstackoverflowsunlessthetotalnumberofelementsinbothstackstogetherisn.ThePUSHandPOPoperationsshouldruninO(1)time.[6points]StudentName:StudentID:Major:答题内容写在边线外视为无效PageNo.29、Tellthedifferencebetweendynamicprogrammingandgreedyprogramming.[6points]10、WearegivenadirectedgraphG=(V,E)onwhicheachedge(u,v)∈Ehasanassociatedvaluer(u,v),whichisarealnumberintherange0≤r(u,v)≤1thatrepresentsthefailurerateofacommunicationchannelfromvertexutovertexv.Weassumethattheseprobabilitiesareindependent.Giveanefficientalgorithmtofindthemostreliablepathbetweentwogivenvertices.[6points]错误!未找到引用源。[60points]11、Considerthesearchingproblem:Input:AsequenceofnnumbersA=〈a1,a2,...,an〉andavaluev.Output:Anindexisuchthatv=A[i]orthespecialvalueNILifvdoesnotappearinA.Writepseudocodeforlinearsearch,whichscansthroughthesequence,lookingforv.Usingaloopinvariant,provethatyouralgorithmiscorrect.Makesurethatyourloopinvariantfulfillsthethreenecessaryproperties.[10points]12、UsearecursiontreetogiveanasymptoticallytightsolutiontotherecurrenceT(n)=T(αn)+T((1-α)n)+cn,whereαisaconstantintherange0α1andc0isalsoaconstant.[12points]13、Ared-blacktreeisabinarysearchtreewithoneextrabitofstoragepernode:itscolor,whichcanbeeitherREDorBLACK,andthered-blackisanearlybalancedtree.[13points]1)Abinarysearchtreeisared-blacktreeifitsatisfiesthefollowingred-blackproperties:1.Everynodeiseitherredorblack.2.Therootisblack.3.Everyleaf(NIL)isblack.4.(1)5.(2)Pleasegivethemissingproperty4andproperty5.[2points]2)Whatisthelargestpossiblenumberofinternalnodesinared-blacktreewithblack-heightk?Whatisthesmallestpossiblenumber?[3points]3)ThereistheRBTinsertionpseudo-code,whichinsertagivennodezintoaRBTT.SupposeyoucanuseLEFT-ROTATE(T,z)andRIGHT-ROTATE(T,z)operationdirectly,Pleasefilltheblank![8points]RB-INSERT(T,z)1y←nil[T]2x←root[T]3whilex≠nil[T]4doy←x5ifkey[z]key[x]6thenx←left[x]PageNo.37else(1)8p[z]←y9ify=nil[T]10thenroot[T]←z11elseifkey[z]key[y]12then(2)13elseright[y]←z14left[z]←nil[T]15right[z]←nil[T]16(3)17RB-INSERT-FIXUP(T,z)RB-INSERT-FIXUP(T,z)1whilecolor[p[z]]=RED2doifp[z]=left[p[p[z]]]3theny←right[p[p[z]]]4ifcolor[y]=RED5then(4)▹Case16(5)▹Case17(6)▹Case18z←p[p[z]]▹Case19elseifz=right[p[z]]10thenz←p[z]▹Case211(7)▹Case212color[p[z]]←BLACK▹Case313(8)▹Case314RIGHT-ROTATE(T,p[p[z]])▹Case315else(sameasthenclausewithrightandleftexchanged)16color[root[T]]←BLACK14、Findanoptimalparenthesizationofamatrix-chainproductwhosesequenceofdimensionsis5,10,3,12,5,50,6.[10points]15、Afullk-treewiththedepthLhasthefollowingproperties:AllthenodesontheLthlayerareleaves;Everynodeonotherlayershasknon-emptysubtrees.IfwenumberallthenodesfromthefirstlayertotheLthlayerandfromlefttorightwith1,2,3...,pleaseanswerthefollowingquestions:[15points]1)Howmanynodesdoestheithlayerhave?[3points]2)Whatisthenumberoftheparentofnoden,ifitexists.[4points]3)Whatisthenumberoftheithchildfromleftofnoden,ifitexists.[4points]4)Inwhatconditiondoesnodenhavearightbrother?Ifithas,whatisthenumberofitsrightbrother?[4points]