算法分析与设计考试样卷

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

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

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

3、oftheseareDivideandConquerAlgorithms,GreedyAlgorithmsandDynamicProgrammingAlgorithms.Givenon-trivialexamplesofeachofthesethreetypesofalgorithmsanddescribethemindetai.Foreachexample,explainwhatmakesitsuchanalgorithm.(Thatis,foryourexampleofagreedyalgorithmyoushouldex

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

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

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

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

8、aphG,Depth-firstsearchalgorithmcanbeusedtofindtheshortestpathsfromagivenvertextoothervertices.11)FortwodecisionproblemsQ1andQ2,ifQ1ispolyn