2009數(shù)據(jù)結(jié)構(gòu)英文試卷A及答案

Finalexamination2009FallDataStructureandAlgorithmDesignClass: StudentNumber: Name: Teacher No.123456789TotalMark1.Single-Choice(20points)Cff(intn){if(n==0)return1;return2*ff(n-1);}Ifn>0,whatisreturnedbyff(n)? log2n(b)n2(c)2n(d)2*nAninputintoastackislike1,2,3,4,5,6.Whichoutputisimpossible? .a.2,4,3,5,1,6 b.3,2,5,6,4,1 c.1,5,4,6,2,3 d.4,5,3,6,2,1Whichofthefollowingdatastructuresusesa"Last-in,First-out"policyforelementinsertionandremoval? (a)Stack(b)Tree (c)Hashtable (d)QueueIfdeletingtheihkeyfromacontiguouslistwithnkeys, keysneedtobeshiftedleftoneposition.a.n-i b.n-i+1 c.i d.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)．quicksortingThenumberofkeywordineverynodeexceptrootinaB-treeoforder5is atleasta.1 b.2 c.3 d.4

WhensortingarecordsequencewithmultiplekeysusingLeastSignificantDigitmethod,thesortingalgorithmusedforeverydigitexcepttheleastsignificantdigit .a.mustbestableb.mustbeunstable c.canbeeitherstableorunstableInthefollowingfourBinaryTrees, isnotacompleteBinaryTree.Themaximumnumberofnodesonleveliofabinarytreeis .a.2i-1 b.2i c.2i d.2i-1IftheBinaryTreeT2istransformedfromtheTreeT1,thenthepostordertraversalsequenceofT1isthe traversalsequenceofT2.a.preorder b.inorder c.postorder d.levelorderInthefollowingsortingalgorithm, isanunstablealgorithm.a.theinsertionsortb.thebubblesortc.quicksortd.mergesortInordertofindaspecifickeyinanorderedlistwith100keysusingbinarysearchalgorithm,themaximumtimesofcomparisonsis .a.25 b.10 c.1 d.7TheresultoftraversinginorderlyaBinarySearchTreeisa(an) order.a.descendingorascendingb.descendingc.ascendingd.disorderTosortakeysequenceinascendingorderbyHeapsortingneedstoconstructa heap.(a)min(b)max(c)eitherminormax(d)completebinarytree.Leti,1WiWn,bethenumberassignedtoanelementofacompletebinarytree.WhichofthefollowingstatementsisNOTtrue? Ifi>1,thentheparentofthiselementhasbeenassignedthenumber|_i/2」.If2i>n,thenthiselementhasnoleftchild.Otherwiseitsleftchildhasbeenassignedthenumber2i.If2i+1>n,thenthiselementhasnorightchild.Otherwiseitsrightchildhasbeenassignedthenumber2i+1.TheheightofthebinarytreeisLlog2(n+1)」.ConsiderthefollowingC++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)InaBinaryTreewithnnodes,thereare non-emptypointers.a.n-1 b.n+1 c.2n-1 d.2n+1Inanundirectedgraphwithnvertices,themaximumnumberofedgesis.TOC\o"1-5"\h\za.n(n+1)/2 b.n(n-1)/2 c.n(n-1) d.n2AssumethepreordertraversalsequenceofabinarytreeTisABEGFCDH,theinordertraversalsequenceofTisEGBFADHC,thenthepostordertraversalsequenceofTwillbe .a.GEFBHDCAb.EGFBDHCAc.GEFBDHCAd.GEBFDHCAThebinarysearchissuitablefora(an) list.a.orderedandcontiguous b.disorderedandcontiguousc.disorderedandlinked d.orderedandlinkedanswer:12345678910ccaadbacab11121314151617181920cdcbdaabaaTOC\o"1-5"\h\z2、Fillinblank(10points)(1)AHuffmantreeismadeofweight11,8,6,2,5respectively,itsWPLis 。(2)ThemostdepthofanAVLtreewith20nodesis .(3)Atreeofdegree3has100nodeswithdegree3and200nodeswithdegree2.Thenumberofleafnodesis .Ifa2-dimensionsmatrixA[m][n]isstoredinan1-Darraywithrow-majormapping,thentheaddressofelementA[i][j]relativetoA[0][0]is Whensortingarecordsequencewith20keysusingmergesorting,howmanypasses.willitexecute? Answer:12345716401i*n+j5

(10points)Showtheresultofinserting{51,25,36,88,42,52,15,96,87,30}into(a)aninitiallyemptyAVLtree;(b)aninitiallyemptyB-treeoforder35points5points5points(10points)Showtheresultofinserting{48,35,64,92,77,13,29,44}intoaninitiallyemptycompleteBinaryTree,ifsortingthelistinascendingorder,thenpleasejustifythecompleteBinaryTreeintoaheap,anddrawtheheapafterfinishingheapsortprocess.answer

(10points)Pleasedrawtheadjacencymatrixandadjacencylistofthefollowingdirectedgraph,andthenfromthestartingpointA,traversethegraphusingdepth-firstsearchandbreadth-firstsearchaccordingtoyouradjacencylistandgivethetwocorrespondingtraversalsequences.Answer:

(2points)BFS:ABECD22A(2points)BFS:ABECD22A(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)unsucc(10points)PleasefillintheblanksintheprogramwhichsortsaKeysequenceinascendingorderwithbubblesorting.(2points/blank)voidbubble_sort(int&a[],intn){intb;change=TRUE;for(i=n-1;i>1&&change;--i){change=FALSE:for(j=0;j<i;++j)if(a[j]>a[j+1]){b=a[j]; a[j]=a[i+1];a[j+1]=b: change=TRUE:}}}//bubble_sort(10points)Pleasereadthefollowingprogram,andwriteitsfunctionandtheoutput.#include<stdio.h>voidunknown(intA[],intB[],intC[],intAend,intBend,int*Num){intApos,Bpos,Cpos;Apos=0;Bpos=0;Cpos=0;while(Apos<Aend&&Bpos<Bend){if(A[Apos]<B[Bpos]){C[Cpos++]=A[Apos++];(*Num)++;}if(A[Apos]==B[Bpos]){C[Cpos++]=A[Apos++];Bpos++;(*Num)++;}if(A[Apos]>B[Bpos]){C[Cpos++]=B[Bpos++];(*Num)++;}}while(Apos<Aend){C[Cpos++]=A[Apos++];(*Num)++;}while(Bpos<Bend){C[Cpos++]=B[Bpos++];(*Num)++;}}main(){intA[4]={3,5,8,11};intB[8]={2,5,6,8,9,11,15,20};intC[12];intlength=0;inti;unknown(A,B,C,4,8,&length);for(i=0;i<length;i++)prin