《算法设计与分析》复习题

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

1、填空1．直接或间接地调用自身的算法称为递归。2．算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。3．以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为o(h(n))。5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题结论的，叫做算法方案方案；另一类是不能通过若干个步骤直截了当地得出结论，而是需要

2、反复验证才能解决的，叫做启发式方案方案。6．算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是随机存取机、随机存取存储程序机、图灵机。8．快速排序算法的性能取决于划分的对称性。9．计算机的资源最重要的是内存和运算资源。因而，算法的复杂性有时间和空间之分。10．贪心算法总是做出在当前看来最优的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优解。11．许多可以用贪心算法求解的问题一般具有2个重要的性

3、质：最优子结构的性质和贪心选择的性质。12．常见的两种分支限界法为队列式和优先队列式。13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是回溯法，不需要排序的是动态规划和分支限界法。14．f(n)=6×2n+n2，f(n)的渐进性态f(n)=O( 2^n  )。15．对于含有n个元素的排列树问题，最好情况下计算时间复杂性为，最坏情况下计算时间复杂性为n!。16．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。17．回溯法的求解过程，即在问题的解空间树中，按深度优先策略从根结点出发搜索解

4、空间树。18．分支限界法的求解过程，即在问题的解空间树中，按广度优先策略从根结点出发搜索解空间树。19．多项式的上界为2^n。20．用分支限界法解布线问题时，对空间树搜索结束的标志是活结点表为空。21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0-1背包，只使用约束条件进行裁剪的是N皇后。简答1.算法分析的目的是什么？分析算的的效率以求改进2.算法的渐进时间复杂性的含义？当问题的规模n趋向无穷大时，影响算法效率

5、的重要因素是T（n）的数量级，而其他因素仅是实用时间复杂度相差的常熟倍，因此可以用T（n）的数量级（阶）评价算法。时间复杂度T（n）的数量级（阶）称为渐进时间复杂性3.最坏情况下的时间复杂性和平均时间复杂性有什么不同？最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } ,   I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I)  I∈Dn4.简述分治法

6、的基本思想。分治法的是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原题相同5.简述动态规划方法所运用的最优化原理。“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。6.简述最优子结构性质。一道动态规划问题其实就是一个递推问题，假设当前决策结果是f[n]，则最优子结构

7、就是要让f[n-k]最优，最优子结构性质就是能让转移到n的状态是最优的，并且与后面的决策没有关系，即让后面的决策安心地使用前面的局部最优解的一种性质7.简述回溯法基本思想。回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。1.用回溯法求解的问题，其解如何表示？有什么规定？问题的解可以表示为n元组：（x1,x2,„„xn），xi∈

8、Si, Si为有穷集合，xi∈Si, （x1,x2,„„xn）具备完备性，即（x1,x2,„„xn）是合理的，则（x1,x2,„„xi）(i