2022数据结构英文试卷A及答案----NEW.docx
Finalexamination2022FallDataStructureandAlgorithmDesignClass:StudentNumber:Name:TeacherILMark6±ngiefehoice(2-point)(1) Considerthefollowingdefinitionofarecursivefunctionff.intff(intn)if(n=0)return1;return2*ff(n-1);)Ifn>0,whatisreturnedbyff(n)?(a)Iog2n(b)2(c)2(d)2*n(2) Aninputintoastackislike1,2,3,4,5,6.Whichoutputisimpossible?.a.2,4,3,5,1,6b.3,2,5,6,4Jc.1,5,4,6,2,3d.4,5,3,6,2,1(3) Whichofthefollowingdatastructuresusesa,'Last-in,First-out"policyforelementinsertionandremoval?(a)Stack(b)Tree(c)Hashtable(d)Queue(4) Ifdeletingtheithkeyfromacontiguouslistwithnkeys,keysneedtobeshiftedleftoneposition.a.n-ib.n-i+1c.id.n-i-1©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-treeoforder5i§atleasta.1b.2c.3d.4(7) WhensortingarecordsequencewithmultiplekeysusingLeastSignificantDigitmethod,thesortingalgorithmusedforeverydigitexcepttheleastsignificantdigit.a.mustbestableb.mustbeunstablec.canbeeitherstableorunstable(8) InthefollowingfourBinaryTrees,isnotacompleteBinaryTree.(9) Themaximumnumberofnodesonleveliofabinarytreeis.a.2-1b.2ic.2d.2-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,1in,bethenumberassignedtoanelementofacompletebinarytree.WhichofthefollowingstatementsisNOTtrue?(a) Ifi>1,thentheparentofthiselementhasbeenassignedthenumberLi2j.(b) If2i>n,thenthiselementhasnoleftchild.Otherwiseitsleftchildhasbeenassignedthenumber2i.(c) If2i+1>n,thenthiselementhasnorightchild.Otherwiseitsrightchildhasbeenassignedthenumber2i+1.(d) TheheightofthebinarytreeisLlog2(n+1)J(16) .CosiderthefollowingC+codefragment.x=191;y=200;while(y>0)if(x>200)x=x-10;y-;elsex+÷Whatisitsasymptotictimecomplexity?(a)O(1)(b)O(n)(c)O(n2)(d)O(n3)(17) InaBinaryTreewithnodes,therearenon-emptypointers.a.n-1b.n+1c.2n-1d.2+1(18) Inanundirectedgraphwithnvertices,themaximumnumberofedgesisa.n(n+1)2b.n(n-1)/2c.n(n-1)d.2(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,itsWPLiso(2) ThemostdepthofanAVLtreewith20nodesis.(3) Atreeofdegree3has100nodeswithdegree3and200nodeswithdegree2.Thenumberofleafnodesis(4) Ifa2-dimensiosmatrixAmnisstoredinan1-Darraywithrow-majormapping,thentheaddressofelementAijrelativetoA00is_(5) Whensortingarecordsequencewith20keysusingmergesorting,howmanypasses.willitexecute?Answer:12345716401i*n÷j53. (10points)Showtheresultofinserting51,25,36,88,42,52,15,96,87,30into(a)aninitiallyemptyAVLtree;5points(b)aninitiallyemptyB-treeoforder3answer:4. (10points)Showtheresultofinserting48,35,64,92,77,13,29,44intoaninitiallyemptycompleteBinaryTree,ifsortingthelistinascendingorder,thenpleasejustifythecompleteBinaryTreeintoaheap,anddrawtheheapafterfinishingheapsortprocess.answer443points3points5. (10points)Pleasedrawtheadjacencymatrixandadjacencylistofthefollowingdirectedgraph,andthenfromthestartingpointA,traversethegraphusingdepth-firstsearchandbreadth-firstsearchacrdigtoyouradjacencylistandgivethetwocorrespondingtraversalsequences.Answer:12345010 00 01010points0 10 100 11 00 10 10 0(2points)(2points)3pointsDFS:ABCEBFS:ABECD6. (10points)GivenHashfunctionH(k)=3Kmod11andthekeysequence32,13,49,24,38,21,4,12.Thesizeofhashtableis11.a. Constructthehashtablewithlinearprobingmethod.b. Calculatetheaveragesearchlengthforsuccessfulandunsuccessfulsearchundertheequalprobability.012345678910412493813243221(6points)ASLsucc=(5*1+3*2)8=118(2points)ASLmh=(1
