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

1、A、4、A、4、WhenusingtheadjacencymatrixAtorepresentaundirectedgraphwithnnodesandeedges,thedegreeofthenodevicanbecomputedbyformula()、A、亠一、20122013學(xué)年第一學(xué)期期末考試試題DataStructureandAlgorithmDesign(A)Class:_StudentNumber:_Name:TeacherNo、IIIIIIIVVVITotalMark1、Single-Choice(20points)1、Theheightofabinarytreethatcon

2、tains1023elementsisatmost(1)andatleast(2)、1022B.1023C.1024D.9E.10F.112、Ifthesequenceofpushingelementsintoastackisa,b,c,whichoutputsequenceisimpossible?().A.abcB.bcaC.cbaD.cab3、Howmanyminimum-costspanningtreesarethereforanundirectedconnectedgraphwithnverticesandeedges?()A、mustbeonlyoneB、n-1C、n-eD、not

3、sure5、Intheworstcase,timecomplexityofquicksortwillbedegradedto()、A.O(n)B.O(n2)C.O(nlogn)6、Inordertofindaspecifickeyinanorderedlistwith100keysusingbinarysearchalgorithm,themaximumtimesofcomparisonsis()、A、25B、10C、1D、77、Considerthefollowingpseudo-code,whichindicatespartofastandardbinarytreealgorithm、pr

4、int(node)printdata;if(thereisaleftchild)print(leftchild);if(thereisarightchild)print(rightchild);Whichofthefollowingisthestandardnameforthisalgorithm?()A、InordertraversalB、PreordertraversalC、PostordertraversalD、Binarysearch8、WhichisnotthepropertyofaB-treeoforderm?()A、TherootnodehasmsubtreeatmostB、Al

5、lleafnodesareatthesamelevel、C、Thekeysineverynodeareordered、D、Allleafnodesareconnectedbylinks、9、Supposethatwehave1000distinctintegers,whichareintherangefrom0to50、IfusingRadixSortaccordingtotheLeastSignificantDigitfirst,()bucketsareneededtoconstructed、A、10B、50C、51D、1000AnswertableforQuestionI(writeyou

6、ranswersofQuestionIhere)1(1)1(2)23456789BEDDABDBDAII、Fillintheblank(2points*5)AnswertableforII(PleasewriteyouranswersofIIhere)12234preorder112,3,5i*n+j5,4,3,2,11、Thestrategyofdepth-firstsearchingalgorithmforagraphissimilartothatoftraversalalgorithmforanormaltree、2、Hereisahashtable,whosesizeis18,hash

7、ingfunctionisH1(key)=key%17(%hereisthemodulusoperator),andwhichusesLinearProbingstrategytocopewiththecollisionsandinserts26,25,72,38,8,18,59intothehashtableinturn、Theaddressof59is_、3、Givenakeysequence2,5,3,pleasewriteitsascendingorderedsequenceafterbeingsortedusingheapsort、(Note5=，just5isbeforeinori

8、ginalsequence)、Pleasedistinguish5and、4、Ifa2-dimensionsmatrixAmnisstoredinan1-Darraywithrow-majormapping,thentheaddressofelementAijrelativetoA00is5、Ifthein-orderandpre-orderseriesofthenodesinabinarytreeare“1,2,3,4,5”and“1,2,3,4,5”respectively,thepostordersequenceshouldbe、III、(40points)1、(8points)Supp

9、osethereisastringabcadececdcdeeededthatcomprisesthecharactersa,b,c,dande、Wemayencodethesymbolsusingvariable-lengthcodesinordertomakethelengthofstringtheshortest、PleasedrawtheHuffmantreeusedtoencodethecharacters,calculatetheweightedpathlengthfortheHuffmantreeandwritethecodeforeachcharacter、DrawtheHuf

10、fmantree(3points)CalculatetheweightedpathlengthfortheHuffmantree(2points)WPL(T)=6x2+5x2+2x3+1x3+4x2=39writethecodeforeachcharacter、(3points)錯一個扣一分,扣光為止abcde12、(8points)Pleaserespectivelygivetwounsortedlistswhoselengthare4toillustratethatquicksortandselectionsortareunstable、Anexamplelistforquicksorta

11、ndthesortingprocedureusingquicksort、(4points)(4,2,3)(2points)sortingprocedureThefirstpass:3,2,4(1point)Thesecondpass:,2,3,4(1point)Anexamplelistforselectionsortandthesortingprocedureusingselectionsort、(4points)(2,3,1)(1points)sortingprocedureThefirstpass:1,3,2(1point)Thesecondpass:1,3,2(1point)Theth

12、irdpass:1,2,3(1point)3、(8points)Giventhekeysequence(331,166,367,236,268,137,337,138),Pleasegivetheprocedure(distributingandcollecting)ofsortingusingradixsortmethod、notnecessarytowritequeuefrontandrearpointerifqueueisnull、Thefirstpass(3points)p331-166-367-236268-137337138lupasoFdi$tTibutingaQrilingto

13、theLeastdi0tlll331-l1叮1E6-236lif6冊一3137337137-337268138Thesecondpass(3points)p331-166236367373372681382adofdistributingacccrdiugtotliemiddledigit3_3it236137t337t138丫國166-367-268吐切2ndpassofcolkctingp-331h236-卜13?33713B-166-h36?268Thethirdpass(2points)p-*331-236-*137*337*138166-367-2683rdpassufdistrib

14、utiagaccoidingtothemostsignifirantdigifl137138166rlf2-236265r2tp13T7367匸3rdpitw寫ofcollectingp13713816J236268一33337一367Itisinascendingorder.4、(6points)Therearen1nodesofdegree1,n2nodesofdegree2,nmnodesofdegreeminatreeofdegreem,howmanyleafnodesthereareinthetree?Pleasegiveformulaandproveyourconclusion、A

15、nswer:becauseeverynodeexceptroothasonebranchlinked,sototalnodesareequaltototalbranchesplusone,therearenbranchesinnodeof(2points)degreen(2points)formulasuchas(2points)TclIlfl斗II斗亠11一詳軌+1如(2points)5、(10points)Showtheresultofinserting63,37,48,100,54,64,27,108,99,42intoanemptybinarysearchtree(2points)an

16、initiallyemptyAVLtree(4points)aninitiallyemptyB-treeoforder3(4points)Answer:binarysearchtree(2points)AVL(4points)f：064993748f：064993748于）（蒼;（HB-tree(4points)IV、(10points)Pleasefillintheblanksintheprogramwhichreversesasinglylinkedlist、Forexample,1,2,3,4,5,6,7,8,9,10willbecome10,9,8,7,6,5,4,3,2,1after

17、beingreversed、#definelist_init_size100#definen10#definelensizeof(structnode)typedefstructnodeintnum;structnode*next;lnode,*link;linkllist;staticinta=1,2,3,4,5,6,7,8,9,10;voidcreat(link*list)/createasinglylinkedlistforkeysequencestoredinarrayainti=0;lnode*p,*q;q=(structnode*)malloc(len);q-num=ai;*lis

18、t=q;while(inext=0;voidreverseList(link*h)/reversethesinglylinkedlistlnode*p,*q,*r;p=*h;r=0;while(p)q=p；(3)；(4)；r=q；(5)；main()lnode*l；creat(&l)；reverseList(&l)；Answer:p_num=ai;q-next=p;.p=p-next;q-next=r;*h=q;V、(10points)Pleasereadthefollowingcode,writethefunctionsofprogramsandwriteoutputoftheprogram

19、、#include#includemalloc、h#definen6staticcharchn=a,b,c,d,e,f;staticintann=0,1,1,0,0,0,1,0,0,1,1,0,1,0,0,1,0,1,0,1,1,0,0,1,0,1,0,0,0,1,0,0,1,1,1,0;typedefstructnode/*鄰接表中的邊結(jié)點*/intadjvex;structnode*next;EdgeNode;typedefstructvnode/*鄰接表中的頂點結(jié)點*/charvertex;EdgeNode*firstedge;VertexNoden;typedefstructintfr

20、ont,rear;intdatan;CirQueue;CirQueue*Q;intpathn,sum=0;intvisitedn;VertexNodeG;voidcreateALGraph()/*根據(jù)鄰接矩陣,建無向網(wǎng)的鄰接表表示*/inti,j;EdgeNode*s;for(i=0;in;i+)Gi、vertex=chi;Gi、firstedge=0;for(i=0;in;i+)for(j=0;jadjvex=j;s-next=Gi、firstedge;Gi、firstedge=s;voidprint()inti;EdgeNode*s;for(i=0;iadjvex、vertex);s=s-next;printf(n);intShortestPath(in