资源描述：
《浙江大学2006–2007学年秋季学期数据结构基础课程期末考试试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、浙江大学2006-2007学年秋季学期《数据结构基础》课程期末考试试卷开课学院：软件学院,考试形式：闭卷，允许带_无入场考试吋间：2006年11月11日,所需吋间：120分钟考生姓名：学号：专业：教师：题序二三四总分得分评卷人NOTE:Pleasewriteyouranswersontheanswersheet.注意：请将答案填写在答题纸上。I.Pleaseselecttheanswerforthefollowingproblems・(20points)(i)Supposethatnnumbersarepushedontoastac
2、kintheorder1,isthefirstnumberthatispoppedoutofmustbe(2points)b.n-i+1c.n-id・anyonethestack,thentheispossible2,n-1,n.Ifni-thnumberpopped(2points)(2)Theproperty(s)thatalistdoesNOThaveis(are)a.noneedtopre-estimatethetotaispaceb.noneedtomoveitemsforinsertionanddeletionc.qui
3、ckrandomaccessd.thespacetakenisproportionaltothelengthofthelist(3)Inthefollowingintegersequences,is(are)NOTaheap.(2points)A・(100,85,98,77,80,60,82,40,20,10,66)b・(100,98,85,82,80,77,66,60,40,20,10)c.(10,20,40,60,66,77,80,82,85,98,100)d.(100,85,40,77,80,60,66,98,82z10,20
4、)(4)Ifdepth-firstsearchcanvisiteveryvertexwithanystartingvertex,thenthatgraphmustbea•(2points)a.treeb.graphcontainscyclesc.completegraphd・connectedgraph(5)Givenanintegersequence{15,9,7,8,20,-1,4,}•IfafterthefirstrunofShellsort,thesequencebecomes{15,-丄，4,8,20,9,7}rthent
5、heincrementmustbe(2points)a.1b.2c.3d・4(2)Placemitemsinahashtablewithanarraysizeofs,theloadingfactoris•(2points)a.s+mb.m/sc.m*sd.m-s(3)Breath-firstsearchwiththeadjacencylistrepresentationofagraphissimilartothetraversalofabinarytree(2points)a.preorderb.inorderc.postorder
6、d.leverl-order(4)Amongthefollowingsortingalgorithms,hastheaverageruntime0(NlogN)withsmallextraspace.(2points)a.Quicksortb.Heapsortc.Mergesortd・Radixsort(5)Inarkeysalongeachofthepathsfromanynodetotherootareordered.(2points)a.heapb.binarysearchtreec.completetreed・noneoft
7、heabove(6)Ifacompletebinarytreeofheighth(>=0)isrepresentedbyanarrayAthentheindexoftheleftmostleafis•(2points)a.2h-1+1b.2hc.2*1-1d.2*1I.Giventhefunctiondescriptionsofthefollowingtwo(pseudo-code)programs,pleasefillintheblanklines.(24points)(1)Thefunctionistodeterminethem
8、inimumpathsfromastartvertextoeveryothervertexinaweighted(alltheweightsarepositive)graph,andtoproduceacountofthenumber
