浙江大学2005–2006学年冬季学期《高级数据结构与算法》课程期末考试试卷

浙江大学2005–2006学年冬季学期《高级数据结构与算法》课程期末考试试卷开课学院：软件学院，考试形式：闭卷，允许带__入场考试时间：_2005_年_1_月_10_日,所需时间：120分钟考生姓名：___学号：专业：____教师：题序一二三四总分得分评卷人NOTE:Pleasewriteyouranswersontheanswersheet.注意：请将答案填写在答题纸上。Pleasefillintheblanks(Therecouldbemultipleanswersforoneblank).(30points)Note:Zeropointforablankselectionsincethereisatleastoneanswerforeachproblem.(1)ForanAVLtree,is(are)correct.(2points) a.Theheightofleftandrightsub-treesdiffersbyatmost1. b.TheinsertionoperationcanbeperformedinO(logN)time. c.AnAVLtreeisakindofbinarysearchtree. d.ThepurposeofusingAVLtreeistosavesomespace.(2)AnAVLtreeofheight6hastheminimumsizeofnodes.(2points) a.31 b.32 c.33 d.34(3)ForaB-tree,is(are)correct.(2points) a.AB-treeisnotasearchtree.b.Alltheleaveshavethesamedepth.c.Allnon-leafnodesofa2-3treehave1or3children.d.GenerallyaB-treeisnotabinarytree.(4)Foraleftistheap,is(are)NOTcorrect.(2points)a.Thetotalnumberofnodesintheleftsub-treeisalwaysnolessthanthatintherightsub-tree.b.AleftistheapofNnodeshasarightpathcontainingatmostlog(N+1)nodes.c.Comparingtobinaryheaps,leftistheapsaremoresuitabletodomerge.d.Abinaryheapisalsoaleftistheap.(5)Foraskewheap,is(are)NOTcorrect.(2points)a.Skewheapisakindofleftistheap.b.Therightpathofaskewheapcanbearbitrarilylong.c.Comparingtoleftistheaps,skewheapsarealwaysmoreefficientinrunningtimeforeverymerge.d.Comparingtoleftistheaps,skewheapsarealwaysmoreefficientinspace.(6)Amongthefollowingstatements,is(are)correct.(2points)a.TheamortizedtimeisanaveragetimeofNsuccessiveoperations.b.Theamortizedtimeistheworst-casetimeofNsuccessiveoperationsintotal.c.ThepotentialfunctionofNsuccessiveinsertionsofabinomialqueueisthenumberoftrees.d.Theamortizedtimecouldbemuchmorethantheactualtimeforoneoperation.(7)Forthefollowings,theO(logN)case(s)is(are),theO(N)case(s)is(are).(2points)a.Theworst-caserunningtimeofmergingtwoleftistheaps.b.Theworst-caserunningtimeofmergingtwoskewheaps.c.Theamortizedcostpermergeofaskewheap.d.BuildingaleftistheapfromNnumbers.(8)Forthefollowingproblems,is(are)undecidableproblem(s)andis(are)NP-completeproblem(s).(3points)a.Eulercircuitproblemb.Hamiltoniancycleproblemc.Satisfiabilityproblemd.Haltingprobleme.All-pairsshortestpathsproblemf.Binpackingproblem(9)Forthefollowingstatements,is(are)NOTcorrect.(2points)a.AllNPproblemsaredecidable.b.AllNP-completeproblemsareNPproblems.c.AlldecidableproblemsareNPproblems.d.AllNPproblemscanbesolvedinpolynomialtimeinanon-deterministicmachine.(10)Forabinomialqueuecontaining23nodes,pleasegivethenamesofnon-emptybinomialtreesinthisbinomialqueue(e.g.B0,B1,B3):.(5points)(11)Theturnpikereconstructionproblemistoreconstructapointsetfromdistancesbetweeneverypairofpoints.Givenasetofdistances{1,2,3,3,4,5,7,7,8,10},thecorrespondingpointsetcontainspointswithcoordinates.(6points)Giventhefunctiondescriptionsofthefollowingtwoprograms,pleasefillintheblanklinesofcode.(15points)(1)AsinglerotationbetweennodeK1anditsrightchildinanAVLtree.(9points)structAvlNode{ElementTypeElement;AvlTreeLeft;AvlTreeRight;intHeight;}TypedefstructAvlNode*Position;TypedefstructAvlNode*AvlTree;staticPositionSingleRotateWithRight(PositionK1){ PositionK2;;;;K1->Height=Max(Height(K1->Left),Height(K1->Right))+1;K2->Height=Max(Height(K2->Right),K1->Height)+1;returnK2;}(2)Findingtheoptimalorderingofmatrixmultiplications.(6points)voidOptMatrix(constlongr[],intN,TwoDimArrayM){inti,k,Left,Right;longThisM;for(Left=1;Left<=N;Left++)M[Left][Left]=0;for(k=1;k<N;k++)for(Left=1;Left<=N-k;Left++){Right=Left+k;M[Left][Right]=Infinity;for(L=Left;L<Right;L++){;if(ThisM<M[Left][Right]);}}}

Pleasewriteordrawyouranswersforthefollowingproblemsontheanswersheet.(40points)(1)Pleasedrawtheresultsofinserting{6，7，8，9，10，1，2，3，4，5}intoa.(6points)aninitiallyemptyAVLtree;andb.(7points)aninitiallyemptysplaytree.(Tip:Drawingthetreesstepbystepmighthelpyougettingpartialcredits.)33817182673718241233211410236(2)Pleasedrawtheresultofdeletingtheminimumnumberfromthegivenleftistheap.(5points)(3)Pleasedrawtheresultofmergingthegiventwobinomialqueues.(5points)132313235124651518211295512212465142616184H2:(4)Givenasegmentoftextthis_is_a_strange_string,howmanybitsarerequiredtostorethestringas1-bytecharacters?HowmanybitsareneededtostoreitsHuffmancode?PleasedrawtheHuffmantreewiththefollowingassumptions:a.Allthecharactersareinitiallystoredinanarrayinthealphabeticalorder;andb.Alltheleftbranchesarecodedwith0’sandalltherightbranchesarecodedwith1’s.(10points)(5)Pleaseshowtheoptimalbinarysearchtreeforthefollowingwords,wherethefrequencyofoccurrenceisinparentheses:an(0.10),be(0.20),can(0.30),if(0.25),or(0.15).(7points)GiventheadjacencymatrixGofaweightedgraph,withG[k][k]presumedtobe0.PleasewriteanalgorithmwithtimecomplexityO(N3)forprintingtheshortestpathsbetweenanytwoverticesI,andjforall0I<j<N.Thatis,youroutputmusthavetheformatasthefollowing:(15points)0->…->1……0->…->N–11->…->2……1->…->N–1……N–2->…->