2009数据结构英文试卷A及答案----NEW

北京交通大学2009年《数据结构与算法设计》试卷第1页Finalexamination2009FallDataStructureandAlgorithmDesignClass:StudentNumber:Name:TeacherNo.123456789TotalMark1.Single-Choice(20points)(1)Considerthefollowingdefinitionofarecursivefunctionff.intff(intn){if(n==0)return1;return2*ff(n-1);}Ifn0,whatisreturnedbyff(n)?(a)log2n(b)n2(c)2n(d)2*n(2)Aninputintoastackislike1,2,3,4,5,6.Whichoutputisimpossible?.a.2,4,3,5,1,6b.3,2,5,6,4,1c.1,5,4,6,2,3d.4,5,3,6,2,1(3)WhichofthefollowingdatastructuresusesaLast-in,First-outpolicyforelementinsertionandremoval?(a)Stack(b)Tree(c)Hashtable(d)Queue(4)Ifdeletingtheithkeyfromacontiguouslistwithnkeys,keysneedtobeshiftedleftoneposition.a.n-ib.n-i+1c.id.n-i-1(5)Sortingakeysequence（28，84，24，47，18，30，71，35，23）,itsstatusischangedasfollows.23，18，24，28，47，30，71，35，8418，23，24，28，35，30，47，71，8418，23，24，28，30，35，47，71，84Thesortingmethodiscalled(a)．selectsorting(b)．Shellsorting(c)．mergesorting(d)．quicksorting(6)ThenumberofkeywordineverynodeexceptrootinaB-treeoforder5is__atleasta.1b.2c.3d.4北京交通大学2009年《数据结构与算法设计》试卷第2页(7)WhensortingarecordsequencewithmultiplekeysusingLeastSignificantDigitmethod,thesortingalgorithmusedforeverydigitexcepttheleastsignificantdigit.a.mustbestableb.mustbeunstablec.canbeeitherstableorunstable(8)InthefollowingfourBinaryTrees,isnotacompleteBinaryTree.abcd(9)Themaximumnumberofnodesonleveliofabinarytreeis.a.2i-1b.2ic.2id.2i-1(10)IftheBinaryTreeT2istransformedfromtheTreeT1,thenthepostordertraversalsequenceofT1isthetraversalsequenceofT2.a.preorderb.inorderc.postorderd.levelorder(11)Inthefollowingsortingalgorithm,isanunstablealgorithm.a.theinsertionsortb.thebubblesortc.quicksortd.mergesort(12)Inordertofindaspecifickeyinanorderedlistwith100keysusingbinarysearchalgorithm,themaximumtimesofcomparisonsis.a.25b.10c.1d.7(13)TheresultoftraversinginorderlyaBinarySearchTreeisa(an)order.a.descendingorascendingb.descendingc.ascendingd.disorder(14)TosortakeysequenceinascendingorderbyHeapsortingneedstoconstructaheap.(a)min(b)max(c)eitherminormax(d)completebinarytree(15).Leti,1≤i≤n,bethenumberassignedtoanelementofacompletebinarytree.WhichofthefollowingstatementsisNOTtrue?(a)Ifi＞1,thentheparentofthiselementhasbeenassignedthenumberi/2.(b)If2in,thenthiselementhasnoleftchild.Otherwiseitsleftchildhasbeenassignedthenumber2i.(c)If2i+1n,thenthiselementhasnorightchild.Otherwiseitsrightchildhasbeenassignedthenumber2i+1.(d)Theheightofthebinarytreeislog2(n+1)(16).ConsiderthefollowingC++codefragment.x=191;y=200;while(y0)if(x200){x=x-10;y--;}elsex++;Whatisitsasymptotictimecomplexity?(a)O(1)(b)O(n)(c)O(n2)(d)O(n3)北京交通大学2009年《数据结构与算法设计》试卷第3页(17)InaBinaryTreewithnnodes,therearenon-emptypointers.a.n-1b.n+1c.2n-1d.2n+1(18)Inanundirectedgraphwithnvertices,themaximumnumberofedgesis.a.n(n+1)/2b.n(n-1)/2c.n(n-1)d.n2(19)AssumethepreordertraversalsequenceofabinarytreeTisABEGFCDH,theinordertraversalsequenceofTisEGBFADHC,thenthepostordertraversalsequenceofTwillbe.a.GEFBHDCAb.EGFBDHCAc.GEFBDHCAd.GEBFDHCA(20)Thebinarysearchissuitablefora(an)list.a.orderedandcontiguousb.disorderedandcontiguousc.disorderedandlinkedd.orderedandlinkedanswer:12345678910ccaadbacab11121314151617181920cdcbdaabaa2、Fillinblank(10points)（1）AHuffmantreeismadeofweight11，8，6，2，5respectively,itsWPLis_____。（2）ThemostdepthofanAVLtreewith20nodesis.（3）Atreeofdegree3has100nodeswithdegree3and200nodeswithdegree2.Thenumberofleafnodesis.(4)Ifa2-dimensionsmatrixA[m][n]isstoredinan1-Darraywithrow-majormapping,thentheaddressofelementA[i][j]relativetoA[0][0]is__(5)Whensortingarecordsequencewith20keysusingmergesorting,howmanypasses.willitexecute?Answer:12345716401i*n+j5北京交通大学2009年《数据结构与算法设计》试卷第4页3.(10points)Showtheresultofinserting{51,25,36,88,42,52,15,96,87,30}into(a)aninitiallyemptyAVLtree;(b)aninitiallyemptyB-treeoforder3answer:5points:5points4.(10points)Showtheresultofinserting{48,35,64,92,77,13,29,44}intoaninitiallyemptycompleteBinaryTree,ifsortingthelistinascendingorder,thenpleasejustifythecompleteBinaryTreeintoaheap,anddrawtheheapafterfinishingheapsortprocess.answer3points51a36a42a25a30a88a15a52a879635a77a92a64Fa29a13a4448a51a253642a30a88a15a528796北京交通大学2009年《数据结构与算法设计》试卷第5页4points3points5.(10points)Pleasedrawtheadjacencymatrixandadjacencylistofthefollowingdirectedgraph,andthenfromthestartingpointA,traversethegraphusingdepth-firstsearchandbreadth-firstsearchaccordingtoyouradjacencylistandgivethetwocorrespondingtraversalsequences.Answer:AEDCB77a48a44a64Fa29a13a3592a29a48a44a35Fa77a64a9213a北京交通大学2009年《数据结构与算法设计》试卷第6页123451010012001103000014101015100003points012343pointsDFS:ABCED(2points)BFS:ABECD(2points)6.(10points)GivenHashfunctionH(k)=3Kmod11andthekeysequence{32，13，49，24，38，21，4，12}.Thesizeofhashtableis11.a.Constructthehashtablewithlinearprobingmethod.b.Calculatetheaveragesearchlengthforsuccessfulandunsuccessfulsearchundertheequalprobability.012345678910412493813243221(6points)ASLsucc=(5*1+3*2)/8=11/8(2points)ASLunsucc=(1+2+1+8+7+6+5+4+3+2+1)/11=40/11(2points)14∧0ABCDE3∧222∧0∧24∧北京交通大学2009年《数据结构与算法设计》试卷第7页7.(10points)PleasefillintheblanksintheprogramwhichsortsaKeysequencein