数据结构英文例题

《数据结构英文例题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ISingleChoice(10points)1.()Forthefollowingprogramfragmenttherunningtime(Big-Oh)is.i=0;s=0;while(s<(5*n*n+2)){i++;s=s+i;}a.O(n)b.O(n2)c.O(n1/2)d.O(n3)2.()Whichisnon-lineardatastructure_____.a.queueb.stackc.treed.sequencelist3.()Theworst-timeforremovinganelementfro

2、masequencelist(Big-Oh)is.a.O(1)b.O(n)c.O(n2)d.O(n3)4.()Inacircularqueuewecandistinguish(区分)emptyqueuesfromfullqueuesby.a.usingagapinthearrayb.incrementingqueuepositionsby2insteadof1c.keepingacountofthenumberofelementsd.aandc5.()Arecursivefunctioncancauseaninfinit

3、esequenceoffunctioncallsif.a.theproblemsizeishalvedateachstepb.theterminationconditionismissingc.nousefulincrementalcomputationisdoneineachstepd.theproblemsizeispositive6．()Thefullbinarytreewithheight4hasnodes.a.15b.16c.31d.327.()Searchinginanunsortedlistcanbemad

4、efasterbyusing.a.binarysearchb.asentinel（哨兵）attheendofthelistc.linkedlisttostoretheelementsd.aandc8.（）Supposethereare3edgesinanundirectedgraphG,IfwerepresentgraphGwithaadjacencymatrix,Howmany“1”sarethereinthematrix?a.3b.6c.1d.99.()ConstructaHuffmantreebyfourleafw

5、hoseweightsare9,2,5,7respectively.Theweightedpathlengthis___________.a.29b.37c.46d.4410.Considerthefollowingweightedgraph.ConsiderDijkstra’salgorithmonthisgraphtofindtheshortestpathswithsasastartingvertex.Whicharethefirstfourverticesextractedfromthepriorityqueueb

6、ythealgorithm(listedintheordertheyareextracted)?a.s,y,t,xb.s,y,x,zc.s,t,y,xd.s,y,x,tFig.111.Hereisanarrayoftenintegers:5389170264Supposewepartitionthisarrayusingquicksort'spartitionfunctionandusing5forthepivot.Whichshowsthearrayafterpartitionfinishes:a.5342107968

7、b.0342157968c.3102458967d.3102458976e.NoneoftheaboveIIFillinBlank(10points)1.Forthefollowingprogramfragmenttherunningtime(Big-Oh)is.for(inti=0;i

8、only.theindexofelementa[2][3]inBis.3．Wecanuse3vectortypetostorevalueandofnon-zeroelementsinasparsematrix.4.A______________isalistwhereremovalandadditionoccurat