2003数据结构英文试卷

浙江工业大学2003年《数据结构》试卷第1页2003DataStructureTest(120minutes)Class:StudentNumber:Name:No.12345678TotalMark1.Single-Choice(20points)(1)TheLinkedListisdesignedforconvenientlybdataitem.a.gettingb.insertingc.findingd.locating(2)Assumeasequencelistas1,2,3,4,5,6passesastack,animpossibleoutputsequencelistIsc.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)Aqueueisastructurenotimplementingb.a.first-in/first-outb.first-in/last-outc.last-in/last-outd.first-come/first-serve(4)Removingthedataitematindexifromasequentiallistwithnitems,ditemsneedtobeshiftedleftoneposition.a.n-ib.n-i+1c.id.n-i-1(5)ThereisanalgorithmwithinsertinganitemtoaorderedSeqListandstillkeepingtheSeqListordered.Thecomputationalefficiencyofthisinsertingalgorithmisc.a.O(log2n)b.O(1)c.O(n)d.(n2)(6)TheaddresseswhichstoreLinkedListd.a.mustbesequentialb.mustbepartlysequentialc.mustbenosequentiald.canbesequentialordiscontiguous(7)AccordingthedefinitionofBinaryTree,therewillbebdifferentBinaryTreeswith5nodes.a.6b.5c.4d.3(8)Inthefollowing4BinaryTrees,cisnotthecompleteBinaryTree.abcd(9)ABinaryTreewillhaveanodesonitsleveliatmost.浙江工业大学2003年《数据结构》试卷第2页a.2ib.2ic.2i+1d.2i-1(10)IftheBinaryTreeT2istransformedfromtheTreeT1,thenthepostorderofT1isthebofT2.a.preorderb.inorderc.postorderd.levelorder(11)Inthefollowingsortingalgorithm,cisanunstablealgorithm.a.theinsertionsortb.thebubblesortc.quicksortd.mergesort(12)Assumethereisaorderedlistconsistingof100dataitems,usingbinarysearchtofindaspecialitem,themaximumcomparisonsisd.a.25b.1c.10d.7(13)TheresultfromscanningaBinarySearchTreeininordertraversalisincorder.a.descendingorascendingb.descendingc.ascendingd.outoforder(14)Thedcaseisworstforquicksort.a.thedatawhichwillbesortedistoolarger.b.therearemanysameiteminthedatawhichwillbesorted.c.thedatawillbesortedisoutoforderd.thedatawillbesortedisalreadyinasequentialorder.(15)InaBinaryTreewithnnodes,thereisanon-emptypointers.a.n-1b.n+1c.2n-1d.2n+1(16)Inaundirectedgraphwithnvertexs,themaximumedgesisb.a.n(n+1)/2b.n(n-1)/2c.n(n-1)d.n2(17)Thepriorityqueueisastructureimplementingc.a.insertingitemonlyattherearofthepriorityqueue.b.insertingitemonlyatthefrontofthepriorityqueue.c.deletingitemaccordingtothepriorityoftheitem.d.firstin/firstout(18)Theoutputfromscanningaminimumheapwithleveltraversalalgorithmc.a.mustbeanascendingsequence.b.mustbedescendingsequencec.musthaveaminimumitemattheheadposition.d.musthaveaminimumitemattherearposition.(19)AssumethepreorderofTisABEGFCDH,theinorderofTisEGBFADHC,thenthepostorderofTwillbea.a.GEFBHDCAb.EGFBDHCAc.GEFBDHCAd.GEBFDHCA(20)Whenarecursivealgorithmistransformedintoanorecursivealgorithm,astructurebisgenerallyused.a.SeqListb.Stackc.Queued.BinaryTree2.Pleaseconvertthefollowinginfixexpression(a*(b+c))+(b/d-e)*aintopostfixexpression,浙江工业大学2003年《数据结构》试卷第3页intheconvertingprocess,pleasedrawthechangeofoperatorstackandthechangeoftheoutput.(10points)3.Assumealistis{xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,xem,zom},pleaseinserttheseitemstoanemptyBinarySearchTreeandthenconstructtheAVLtree.Pleasedrawthewholeprocessesincludinginsertinganitem,orrotatenodestorestoreheightbalance.(10points)4.Assumealistis{48,35,64,92,77,13,29,44},firstlyinserttheseitemstoanemptycompleteBinaryTreeaccordingtothesequenceonebyone,thenpleaseheapifythecompleteBinaryTreeandimplementtheheapsort.Pleasedrawthewholeheapigyingprocessandsortingprocess.(10points)5.Forthefollowingdirectedgraph,givetheadjacencymatrixandadjacencylist.Thenaccordingyouradjacencylist,pleasescanthegraphusingthedepth-firstsearchandthebreadth-firstsearchandgivethecorrespondingresult.(10points)6.Assumealistis35,25,47,13,66,41,22,57,pleasesortingthelistwithquicksortalgorithm.Pleasewriteeverysortingpassresult(noprogramming).(10points)7.Assumekeys={32,13,49,55,22,39,20},Hashfunctionish(key)=key%7.Thelinearprobeopenaddressingisusedtoresolvecollisions.PleasetrytocalculatethevalueofHashforeachkeyandgivethefinalhashtable.(10points)8.Programming(Allmethodshavebeendeclaredintextbookcanbeuseddirectly,oryoucanrewritethemiftheyarenotsameinyouranswer)(20points)(1)AssumetherearetwoascendingorderedlistsL1andL2,pleasemergeL1andL2intoanewlistL3.TherewillbenoduplicateitemsinL3.ThenpleasereversetheL3intoadescendingorderedlist.(10points)(2)PleasegivethecompletedeclarationofQueueincirclemodel,thenwritetheinsertalgorithmanddeletealgorithm.(10points)AEDCB