资源描述：
《2012--数据结构英文试卷A及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、北京交通大学软件学院2012―2013学年第一学期期末考试试题DataStructureandAlgorithmDesign(A)Class:____StudentNumber:_____Name:________Teacher________No.IIIIIIIVVVITotalMarkI.Single-Choice(20points)1.Theheightofabinarytreethatcontains1023elementsisatmost(1)andatleast(2).A．1022B．1023C．1024D．9E．10F．112.Ifthesequen
2、ceofpushingelementsintoastackisa,b,c,whichoutputsequenceisimpossible?（）．A．abcB．bcaC．cbaD．cab3.Howmanyminimum-costspanningtreesarethereforanundirectedconnectedgraphwithnverticesandeedges?()A.mustbeonlyoneB.n-1C.n-eD.notsure4.WhenusingtheadjacencymatrixAtorepresentaundirectedgraphwithnn
3、odesandeedges,thedegreeofthenodevicanbecomputedbyformula().A.B./2C.e/2D.5.Intheworstcase,timecomplexityofquicksortwillbedegradedto().A．O(n)B．O(n2)C．O(nlogn)6.Inordertofindaspecifickeyinanorderedlistwith100keysusingbinarysearchalgorithm,themaximumtimesofcomparisonsis().A.25B.10C.1D.77.
4、Considerthefollowingpseudo-code,whichindicatespartofastandardbinarytreealgorithm.print(node){printdata;if(thereisaleftchild)print(leftchild);if(thereisarightchild)print(rightchild);}Whichofthefollowingisthestandardnameforthisalgorithm?()A.InordertraversalB.PreordertraversalC.Postorder
5、traversalD.Binarysearch8.WhichisnotthepropertyofaB-treeoforderm?()A.TherootnodehasmsubtreeatmostB.Allleafnodesareatthesamelevel.C.Thekeysineverynodeareordered.D.Allleafnodesareconnectedbylinks.9.Supposethatwehave1000distinctintegers,whichareintherangefrom0to50.IfusingRadixSortaccordin
6、gtotheLeastSignificantDigitfirst,()bucketsareneededtoconstructed.A.10B.50C.51D.1000AnswertableforQuestionI(writeyouranswersofQuestionIhere)1(1)1(2)23456789BEDDABDBDAII.Fillintheblank(2points*5)AnswertableforII(PleasewriteyouranswersofIIhere)12234preorder112，3，⑤，5i*n+j5,4,3,2,11.Thestr
7、ategyofdepth-firstsearchingalgorithmforagraphissimilartothatof____traversalalgorithmforanormaltree.2.Hereisahashtable,whosesizeis18,hashingfunctionisH1(key)=key%17(%hereisthemodulusoperator),andwhichusesLinearProbingstrategytocopewiththecollisionsandinserts26,25,72,38,8,18,59intotheha
8、shtab
