浙江大学2007–2008学年秋季学期 数据结构基础 课程期末考试试卷

《浙江大学2007–2008学年秋季学期 数据结构基础 课程期末考试试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浙江大学2007–2008学年秋季学期《数据结构基础》课程期末考试试卷开课学院：软件院、计算机、竺可桢学院，考试形式：闭卷，允许带_无入场考试时间：_2007_年_11_月_17日,所需时间：120分钟考生姓名：___学号：专业：____教师：题序一二三四总分得分评卷人AnswerSheetPartI1.c2.a3.d4.d5.c6.b7.a8.b9.b10.cPartII1.H->Elements[1]Child!=H->Size&&H->Elements[Child+1]>H->Elements[Child]H->Elements[i]=H->Eleme

2、nts[Child]2.j>=IncrementTmp

3、Compareanewelementwiththerootand,DeletMinandInsertthenewelementifthenewoneislarger.O(Nlogk)Sortandtakethekthlargest.O(NlogN)TakeapivotandpartitionthesetasinQuicksort.Ifk<=

4、S2

5、thentheelementmustbeinS2,recursivelyfinditfromS2.Ifk=

6、S2

7、+1,thenreturnthepivot.Ifk>

8、S2

9、,thenit’sinS1andit’s

10、the(

11、S1

12、-N+k)-thlargestelement.RecursivelyfinditfromS1.Average=O(N).Worst=O(N2).4.(b)PartIVvoidDijkstra(TableT){/*T[].Countisinitializedtobe0.T[start].Count=T[start].balloon*/vertexv,w;for(;;){v=smallestunknowndistancevertex;if(v==NotAVertex)break;T[v].Known=True;for(eachwadjacentt

13、ov)if(!T[w].Known)if(T[v].Dist+CvwT[w].Count)){T[w].Count=T[v].Count+T[w].balloon;T[w].Path=v;/*DONOTforgetthis*/}}}NOTE:Pleasewritey

14、ouranswersontheanswersheet.注意：请将答案填写在答题纸上。I.Pleaseselecttheanswerforthefollowingproblems.(20points)(1)Thetimecomplexityofthefollowingpieceofcodeis(2points)for(i=0;i0;j/=2)printf(“%d”,j);a.O(n)b.O(n*n)c.O(nlogn)d.O(n*i)(2)Supposethatthetimecomplexitiesoftwoprogram

15、saregivenbyT1(N)=O(f(N))andT2(N)=O(f(N)).Whichofthefollowingequationsistrue?(2points)a.T1(N)+T2(N)=O(f(N))b.T1(N)-T2(N)=o(f(N))c.T1(N)/T2(N)=O(1)d.T1(N)=O(T2(N))(3)GivenanemptystackSandanemptyqueueQ.AlistofcharactersarepushedintoSintheorderofa,b,c,d,e,fandeverycharacterthatispopped

16、fromSwillbeinsertedintoQim