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

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

1、浙江大学am-zhs学年秋季学期《数据结构基础》课程期末考试试卷开课学院：软件院、计算机、竺可桢学院,考试形式：闭卷，允许帯.无入场考试时间:工化年血刀"日.所需时间:ne分钟考生姓名：学号：专业：教师：题序二四总分得分评卷人AnswerSheetPartI1.C2.a3.d4.d5.c6.b7.a&b9.b10.cPartII1]1.(c)Child!=H->Size&&H->EJ.Gments〔Child+1]>H-〉Elements[Child]H->ElGnients[i]=H->Elements[Child]2.3.j>=IncrementThisSum

2、+A[j]Tmp

3、rgest.O(NlogN)TakeapivotandpartitionthesetasinQuicksort・Ifk<=

4、S2

5、thentheelementmustbeinS2,recursivelyfinditfromS2.Ifk=

6、S2

7、+l,thenreturnthepivot.Ifk>

8、S2

9、,thenit'sinSIandit'sthe(

10、Sl

11、・N+k)・thlargestelement.RecursivelyfinditfromSl・Average=O(N).Worst=O(N2).4.(b)PartIVvoidDijkstra(TableT){/

12、*T[].Countisinitializedtobe0.T[start]-Count=T[start].balloon*/vertexv,w;for(;;){v=smallestunknowndistancevertex;if(v==NotAVertex)break;T[v].Known=True;for(eachwadjacenttov)if(!T[w].Known)if(T[v].Dist+Cvw

13、lloon;}elseif((T[v].Dist+Cvw==T[w].Dist)&&(T[v].Count+T[w].balloon>T[w].Count)){T[w].Count=T[v].Count+T[w].balloon;T[w].Path=v;/*DONOTforgetthis*/}}}NOTE:Pleasewriteyouranswersontheanswersheet.注意：请将答案填写在答题纸上。I.Pleaseselecttheanswerforthefollowingproblems・(20points)(1)Thetimecomplexity

14、ofthefollowingpieceofcodeis(2points)for(i=0;i0;j/=2)printf(''%dz/zj);a.0(n)b.0(n*n)c.0(nlogn)d.O(n*i)(2)SupposethatthetimecomplexitiesoftwoprogramsaregivenbyT1(N)=0(f(N))andT2(N)=0(f(N))•Whichofthefollowingequationsistrue?(2points)a.T1(N)+T2(N)=0(f(N))b.T1(N)-T2(N)=

15、o(f(N))c.T1(N)/T2(N)=0(l)d.T1(N)=0(T2(N))(3)GivenanemptystackSandmnemptyqueueQ・AlistofcharactersarepushedintoSintheorderofa.bfcrdferfandeverycharacterthatispoppedfromSwillbeinsertedintoQimmediately.IftheoutputofQisbrdfcffrera,theminimumcapacityofSmustbe•(2points)a.6b・5c・4d・3(4)Suppose

16、thatt