浙江大学2006–2007学年冬季学期new

《浙江大学2006–2007学年冬季学期new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浙江大学2006–2007学年冬季学期《高级数据结构与算法分析》课程期末考试试卷开课学院：软件学院、计算机学院、竺可桢学院，考试形式：闭卷，允许带_无入场考试时间：_2007_年_1_月_16_日,所需时间：120分钟考生姓名：___学号：专业：____教师：题序一二三四总分得分评卷人NOTE:Pleasewriteyouranswersontheanswersheet.注意：请将答案填写在答题纸上。I.Pleasefillintheblanks(Therecouldbemultipleanswersforoneblank).(24points)Note:Zeropointforab

2、lankselectionsincethereisatleastoneanswerforeachproblem.(1)ThetimecomplexityforfindinganelementinasplaytreewithNnodesis.(2points)a.O(1)b.O(logN)c.O(N)d.O(NlogN)(2)ThedepthofanAVLtreewith32nodesisatleast(2points)andatmost.(2points)a.5b.6c.7d.8(3)Whensolvingthebinpackingproblemwiththebest-fitmeth

3、od,arrangingtheremainingcapacitiesofthebinsin(2points)canreducethetimecomplexity.a.alinearsequentialstorageb.anAVLtreec.amin-heapd.anorderedlinearstorage(4)Abinomialqueueofsize53canberepresentedbythefollowingbinomialqueues.(2points)a.B0B1B2B3B4B5b.BB0B1B3B5c.B1B3B5B6d.BB0B2B4B5(5)Aleftisttreewi

4、thrnodesontherightpathmusthavenodes.(2points)rrr-1r-1a.atleast2-1b.atmost2-1c.atleast2d.atmost2(6)Forabinomialqueue,take(s)aconstanttimeonaverage.(2points)a.mergingb.find-minc.delete-mind.insertion(7)Whichofthefollowingproblemsarenotknowntoberuninpolynomialtime:.(2points)a.Eulercircuitproblemb.

5、Hamiltoncycleproblemc.Single-sourceunweightedshortest-pathproblemd.Single-sourceunweightedlongest-pathproblem(8)Anamortizedtimeboundis.(2points)a.>=worst-casetimeboundb.>=average-casetimeboundc.<=best-casetimeboundd.<=worst-casetimebound(9)TosolveaproblemwithinputsizeNbydivideandconqueralgorith

6、ms,iftheconquersteptakesO(N)extraworktoformthesolutionfromthesub-solutions,thenamongthefollowingfourdividingmethods,(2points)isthebestonewhile(2points)istheworstone.a.divideinto4sub-problemsofequalcomplexityN/3b.divideinto3sub-problemsofequalcomplexityN/4c.divideinto4sub-problemsofequalcomplexi

7、tyN/4d.divideinto3sub-problemsofequalcomplexityN/3(10)Thefastestalgorithmforconstructinganoptimalbinarysearchtreeisthe.algorithm.(2points)a.greedyb.divideandconquerc.dynamicprogrammingd.backtrackingII.Giventhefunctiondescriptionso