《2022数据结构英文试卷A及答案----NEW.docx》由会员分享，可在线阅读，更多相关《2022数据结构英文试卷A及答案----NEW.docx（8页珍藏版）》请在课桌文档上搜索。
1、Finalexamination2022FallDataStructureandAlgorithmDesignClass:StudentNumber:Name:TeacherILMark6ngiefehoice(2-point)(1) Considerthefollowingdefinitionofarecursivefunctionff.intff(intn)if(n=0)return1;return2*ff(n-1);)Ifn0,whatisreturnedbyff(n)?(a)Iog2n(b)2(c)2(d)2*n(2) Aninputintoastackislike1,2,3,4,5,
2、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-outpolicyforelementinsertionandremoval?(a)Stack(b)Tree(c)Hashtable(d)Queue(4) Ifdeletingtheithkeyfromacontiguouslistwithnkeys,keysneedtobeshiftedleftoneposition.a.n-
3、ib.n-i+1c.id.n-i-1Sortingakeysequence(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) Thenumberofkeywordineverynodeexcept
4、rootinaB-treeoforder5iatleasta.1b.2c.3d.4(7) WhensortingarecordsequencewithmultiplekeysusingLeastSignificantDigitmethod,thesortingalgorithmusedforeverydigitexcepttheleastsignificantdigit.a.mustbestableb.mustbeunstablec.canbeeitherstableorunstable(8) InthefollowingfourBinaryTrees,isnotacompleteBinary
5、Tree.(9) Themaximumnumberofnodesonleveliofabinarytreeis.a.2-1b.2ic.2d.2-1(10) IftheBinaryTreeT2istransformedfromtheTreeT1,thenthepostordertraversalsequenceofT1isthetraversalsequenceofT2.a.preorderb.inorderc.postorderd.levelorder(11) Inthefollowingsortingalgorithm,isanunstablealgorithm.a.theinsertion
6、sortb.thebubblesortc.quicksortd.mergesort(12) Inordertofindaspecifickeyinanorderedlistwith100keysusingbinarysearchalgorithm,themaximumtimesofcomparisonsis.a.25b.10c.1d.7(13) TheresultoftraversinginorderlyaBinarySearchTreeisa(an)order.a.descendingorascendingb.descendingc.ascendingd.disorder(14) Tosor
7、takeysequenceinascendingorderbyHeapsortingneedstoconstructaheap.(a)min(b)max(c)eitherminormax(d)completebinarytree(15) .Leti,1in,bethenumberassignedtoanelementofacompletebinarytree.WhichofthefollowingstatementsisNOTtrue?(a) Ifi1,thentheparentofthiselementhasbeenassignedthenumberLi2j.(b) If2in,thenth
8、iselementhasnoleftchild.Otherwiseitsleftchildhasbeenassignedthenumber2i.(c) If2i+1n,thenthiselementhasnorightchild.Otherwiseitsrightchildhasbeenassignedthenumber2i+1.(d) TheheightofthebinarytreeisLlog2(n+1)J(16) .CosiderthefollowingC+codefragment.x=191;y=200;while(y0)if(x200)x=x-10;y-;elsex+;Whatisi
9、tsasymptotictimecomplexity?(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,theinordert
10、raversalsequenceofTisEGBFADHC,thenthepostordertraversalsequenceofTwillbe.a.Gefbhdcab.egfbdhcac.gefbdhcad.gebfdhca(20) Thebinarysearchissuitablefora(an)list.a.orderedandcontiguousb.disorderedandcontiguousc.disorderedandlinkedd.orderedandlinkedanswer:12345678910Ccaadbacab11121314151617181920Cdcbdaabaa
11、2、Fillinblank(10points)(1) AHuffmantreeismadeofweight11,8,6,2,5respectively,itsWPLiso(2) ThemostdepthofanAVLtreewith20nodesis.(3) Atreeofdegree3has100nodeswithdegree3and200nodeswithdegree2.Thenumberofleafnodesis(4) Ifa2-dimensiosmatrixAmnisstoredinan1-Darraywithrow-majormapping,thentheaddressofeleme
12、ntAijrelativetoA00is_(5) Whensortingarecordsequencewith20keysusingmergesorting,howmanypasses.willitexecute?Answer:12345716401i*nj53. (10points)Showtheresultofinserting51,25,36,88,42,52,15,96,87,30into(a)aninitiallyemptyAVLtree;5points(b)aninitiallyemptyB-treeoforder3answer:4. (10points)Showtheresult
13、ofinserting48,35,64,92,77,13,29,44intoaninitiallyemptycompleteBinaryTree,ifsortingthelistinascendingorder,thenpleasejustifythecompleteBinaryTreeintoaheap,anddrawtheheapafterfinishingheapsortprocess.answer443points3points5. (10points)Pleasedrawtheadjacencymatrixandadjacencylistofthefollowingdirectedg
14、raph,andthenfromthestartingpointA,traversethegraphusingdepth-firstsearchandbreadth-firstsearchacrdigtoyouradjacencylistandgivethetwocorrespondingtraversalsequences.Answer:12345010 00 01010points0 10 100 11 00 10 10 0(2points)(2points)3pointsDFS:ABCEBFS:ABECD6. (10points)GivenHashfunctionH(k)=3Kmod11
15、andthekeysequence32,13,49,24,38,21,4,12.Thesizeofhashtableis11.a. Constructthehashtablewithlinearprobingmethod.b. Calculatetheaveragesearchlengthforsuccessfulandunsuccessfulsearchundertheequalprobability.012345678910412493813243221(6points)ASLsucc=(5*1+3*2)8=118(2points)ASLmh=(1+21+8+76+5+4+3+21)/11
16、=40/11(2points)UOUv*U7. (10points)PleasefillintheblanksintheprogramwhichsortsaKeysequenceinascendingorderwithbubblesorting.(2pointsblank)voidbubble_sort(int&a,intn)intb;Change=TRUE;for(i=n-1;i1&change;-i)Change=FALSE;for(j=0;ja+1)b=ai;aE=Hi+1l:aj+1=b;change=TRUE;)/bubble_sort8. (IOpoints)Pleasereadt
17、hefollowingprogram,andwriteitsfunctionandtheoutput.#includevoidunknown(intA,intB,intC,intAendJntBend,int*Num)intApos,Bpos,Cpos;Apos=O;Bpos=O;Cpos=O;while(AposAend&BposBend)if(AAposBBpos)CCpos+=BBpos+;(*Num)+;while(AposAend)CCpos+=AApos+;(*Num)+;while(BposBend)CCpos+=BBpos+;(*Num)+;main()(intA4=3,5,8,11);intB8=2,5,6,8,9,11,15,20);intC12;intIength=O;inti;unknown(A,B,C,4,8,Sgth);for(i=0;ilchild)&(!T-rchild)(2points)return1;/对叶子结点计数elsen1=CountLeaf(T-lchild);(1points)2=CountLeaf(T-rchild);(1points)return(n1+n2);(2points)if/CountLeaf
