武汉科技大学2012级算法设计与分析重点

《武汉科技大学2012级算法设计与分析重点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析一、本次考试重点客观题1．算法是用计算机解决问题时的________和________。2.算法的5个基本特征是________、________、________、________________、________________。3.算法的质量指标有________、________、_________、________________。4.自然语言的缺点是：容易有歧义性可能导致算法的_________；语句太长导致算法太长；自然语言有串行性因此当算法中______和______较多时就很难清

2、晰表示出来；自然语言使用的算法不便于用程序设计语言翻译成计算机程序。5.算法的3条评价标准是_______________、______________、___________________。6.存在多项式时间的算法的一类问题，称之为_________；不存在多项式时间的算法的一类问题，称之为_________。7.迭代的两种方法是________和________。8.分治法的3个基本步骤是________、________、________。9.贪婪算法的基本理论是_____________________

3、___________________。10.多阶段最优化决策解决问题的过程称为________。11.使用枚举法时应该注意________________________。12.图分为________和________。13.典型的隐式图有________和________。前者的时间复杂度为________，后者为________。14.显式图常用的搜索方法有________和________；隐式图常用的搜索方法有________和________。15．使用枚举法求解问题时为了提高算法效率应该______

4、________________。16.循环深度为depth，则该循环时间复杂度为____________________。简答题1.请画出流程图中顺序结构、双分支选择结构、多分支选择结构、当型循环结构、直到型循环结构的图示。2.计算下列3种情况下的T(n)（提示：画出递归树）。（1）T(n)=T(n/2)+1（2）T(n)=2T(n/2)+1（3）T(n)=3T(n/2)+13.排列下列时间复杂度的数量级规模。O(logn)、）O（1）、O(n)、O(n!)、O(c^n)、O(n^c)4.设计循环结构和递归结构

5、的关键是什么（应该注意什么）？5.试比较循环结构和递归结构的优缺点。A.循环不论是时间复杂度还是空间复杂度都比递归高，所以可读性相差不大是尽量选择循环。B.递归包括递归和回溯两步，所以“后进先出”问题，递归算法更有效C.递归是一种比循环更强、好用的实现“重复操作”的机制，可读性好，代码量少，适用范围广，设计难度易，而循环空间，时间更节约递归的步骤：A.分析问题、寻找递归关系，是问题的规模逐渐变小B.设置边界、控制递归，找出算法可解的最小规模问题C.设计函数、确定参数6.使用动态规划方法的条件（性质）A.最优化原理

6、：问题包含的子问题的解也是最优的B.无后向性：某阶段状态一旦确定，就不受这个状态以后的决策的影响C.子问题重叠：子问题之间是不独立的，一个子问题在下一阶段的决策中可能被多次使用到动态规划的思想：把求解的问题分成多阶段或多个子问题，然后按照顺序求解各个子问题。前一子问题的解为后一子问题提供有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些可能达到最优的局部解，丢弃其他局部解。依次解各子问题，最后一个子问题就是初始问题的解。动态规划的步骤：A.划分阶段：按照空间和时间特征，划分为若干个阶段B.选择

7、阶段：将各种客观问题用不同状态表示出来C.确定决策并写出状态转移方程7.自然语言的缺点A.歧义性，导致算法的不确定性B.语句太长，导致算法太长C.串行性特点，很难表示循环和分支结构D..不便用程序设计语言翻译成计算机程序二、简答题重点不同算法策略特点小结1、贪心策略   贪心策略一方面是求解过程比较简单的算法，另一方面它又是对能适用问题的条件要求最严格（即适用范围很小）的算法。   贪心策略解决问题是按一定顺序，在只考虑当前局部信息的情况下，就做出一定的决策，最终得出问题的解。   即：通过局部最优决策能得到全局

8、最优决策2、递推策略  递推也是由当前问题的逐步解决从而得到整个问题的解，依赖于信息间本身的递推关系，每一步不需要决策参与到算法中，更多用于计算3、递归策略  递归常常用于分治算法、动态规划算法中。  递归是利用大问题与其子问题间的递推关系来解决问题的。  能采用递归策略的算法一般有以下特征：  （1）为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的