算法分析与设计考试样卷

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

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

2、udonotneedtojustifythem.2.Describethemainideasofthefollowingstrategies,andbrieflydescribethedifferencesbetweenthem.(1)divide-and–conquer;(2)dynamicprogramming；(3)branchandbound3.Duringthecoursewehavestudiedsomeimportantclassesofalgorithms.ThreeoftheseareDivideandConquerAlgorithms,GreedyA

3、lgorithmsandDynamicProgrammingAlgorithms.Givenon-trivialexamplesofeachofthesethreetypesofalgorithmsanddescribethemindetai.Foreachexample,explainwhatmakesitsuchanalgorithm.(Thatis,foryourexampleofagreedyalgorithmyoushouldexplainexactlywhatmakesitagreedyalgorithm,andsoon.)Solution:Thereare

4、lotofpossiblesolutions.Naturalexampleswouldbe:DivideandConquer:MergesortGreedy:Kruskal’salgorithm.DynamicProgramming:Dijkstra’salgorithmorBellman-Ford’salgorithm.4.(30points)ChooseTorFforeachofthefollowingstatements.1)ThebestcaserunningtimeforquicksorttosortanelementarrayisO(nlogn).2)Byt

5、hemastertheorem,thesolutiontotherecurrenceT(n)=3T(n/3)+3nisT(n)=O(nlogn).3)EverybinarysearchtreeonnnodeshasheightO(logn).1)Byusingpathcompression(Union-Find)techniquetoanalyzeKruskalalgorithm,thealgorithm’srunningtimeisO(mlog*n+nlog*n).2)Depth-firstsearchofagraphisasymptoticallyfastertha

6、nbreadth-firstsearch.3)Kruskal’salgorithmforfindingaminimumspanningtreeemploysdynamicprogramming.4)Thebacktracktechniqueusestheideaofbreathfirstsearchtogettheoptimalvalue.5)n!=O(2n).6)Intheworstcase,mergesortrunsinO(n2）time.7)Incomputerscience,alltheproblemsareeitherinPorNP.8)Kruskal’sal

7、gorithmisfasterPrim’salgorithm.9)Divide-and-Conquerisabottom-upalgorithmandDynamicProgrammingisatop-downalgorithm.10)ForanunweightedgraphG,Depth-firstsearchalgorithmcanbeusedtofindtheshortestpathsfromagivenvertextoothervertices.11)FortwodecisionproblemsQ1andQ2,ifQ1ispolyn