算法分析与设计考试样卷

《算法分析与设计考试样卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计复习题1.Basedonwhatwehavediscussedinclass,statethebestasymptoticrunningtimeforeachoftheproblemsbelow,usingthe”bigOh”notation.ItisassumedthatT(1)=dforsomeconstantdinalltherecurrences.IfyouthinktheproblemisNP-complete,stateso(norunningtimeshouldbegiveninthisca

2、se).Juststatetheanswers-youdonotneedtojustifythem.2.Describethemainideasofthefollowingstrategies,andbrieflydescribethedifferencesbetweenthem.(1)divide-and–conquer;(2)dynamicprogramming；(3)branchandbound3.Duringthecoursewehavestudiedsomeimportantclassesofalgorith

3、ms.ThreeoftheseareDivideandConquerAlgorithms,GreedyAlgorithmsandDynamicProgrammingAlgorithms.Givenon-trivialexamplesofeachofthesethreetypesofalgorithmsanddescribethemindetai.Foreachexample,explainwhatmakesitsuchanalgorithm.(Thatis,foryourexampleofagreedyalgorith

4、myoushouldexplainexactlywhatmakesitagreedyalgorithm,andsoon.)Solution:Therearelotofpossiblesolutions.Naturalexampleswouldbe:DivideandConquer:MergesortGreedy:Kruskal’salgorithm.DynamicProgramming:Dijkstra’salgorithmorBellman-Ford’salgorithm.4.(30points)ChooseTorF

5、foreachofthefollowingstatements.1)ThebestcaserunningtimeforquicksorttosortanelementarrayisO(nlogn).2)Bythemastertheorem,thesolutiontotherecurrenceT(n)=3T(n/3)+3nisT(n)=O(nlogn).3)EverybinarysearchtreeonnnodeshasheightO(logn).1)Byusingpathcompression(Union-Find)t

6、echniquetoanalyzeKruskalalgorithm,thealgorithm’srunningtimeisO(mlog*n+nlog*n).2)Depth-firstsearchofagraphisasymptoticallyfasterthanbreadth-firstsearch.3)Kruskal’salgorithmforfindingaminimumspanningtreeemploysdynamicprogramming.4)Thebacktracktechniqueusestheideao

7、fbreathfirstsearchtogettheoptimalvalue.5)n!=O(2n).6)Intheworstcase,mergesortrunsinO(n2）time.7)Incomputerscience,alltheproblemsareeitherinPorNP.8)Kruskal’salgorithmisfasterPrim’salgorithm.9)Divide-and-Conquerisabottom-upalgorithmandDynamicProgrammingisatop-downal

8、gorithm.10)ForanunweightedgraphG,Depth-firstsearchalgorithmcanbeusedtofindtheshortestpathsfromagivenvertextoothervertices.11)FortwodecisionproblemsQ1andQ2,ifQ1ispolyn