算法分析与设计期末试题答案2011-c

1、。装。订。线。2011 年2012 年第 一 学期算法分析与设计期末试卷C 卷时间共 120 分钟一、（10 分）算法？算法有哪些基本特征？请算法同程序的相同点与不同点。解: 算法是解决问题的方法或过程，是满足以下四个性质的指令序列1）输入：有0 个以上的输入2）输出：至少有 1 个输出3）确定性：指令清晰、无歧义4）有限性：指令执行次数有限，时间有限算法和程序的相同点：两者都具有输入、输出和确定性的特征不同点：程序是算法用某种程序语言的具体实现，程序不满足算法具有的有限性性质二、（10 分）设某个算法的运行时间 T(n)满足如下递归方程：n 1T (n) O(1)2T (n / 2) O(n

2、) n 1.则该算法的时间复杂性是什么？解：T(n)=O(nlogn).三、（10 分）已知 A (a(k ) )，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求kijri *ri1矩阵链积 A1A2A3A4A5A6 的最佳求积顺序。（要求：给出计算步骤）解：使用动态规划算法进行求解。第 1 页 共 4 页得分阅卷人得分阅卷人得分阅卷人题号12345678910总分得分阅卷人求解矩阵为：因此，最佳乘积序列为（A1A2）（A3A4）（A5A6），共执行乘法 2010 次。四、（10 分）请问二分搜索算法、快速排序算法、线性时间选择算法和

3、最近点对问题的时间复杂性各为多少？解:二分搜索算法：情况 O(logn)、快速排序算法:情况 O(n2)，最好情况和平均情况均为 O(nlogn)线性时间选择算法:情况 O(n)最近点对问题:时间复杂性 O(nlogn)五、（15 分）分治算法和动态规划算法都是通过对问题进行分解，通过对子问题的求解然后进行解重构，从而实现对原问题的求解。请这两种算法在对问题进行分解时各自所遵循的原则。解：分治算法对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互独立且与原问题相同的子问题（不包含公共的子问题）。动态规划对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互关联的

4、与原问题类似的子问题（包含公共的子问题），采用表的方法来保存所有已解决问题的，而在需要的时候再找出已求得的，避免大量的重复计算。第 2页 共 4 页得分阅卷人得分阅卷人1234561012242202222303444044505601234561015033040516552010六、（15 分）贪心算法的设计是什么，特点？如果一个问题用贪心算法可以获得全局最优解，那么该问题的求解应满足哪些条件？解：贪心算法的设计是在对问题求解时，总是做出在当前看来是最好的选择。它的特点是 1）不是从整体考虑得到的解可能不是全局最优 2）简单，直接，易理解，效率高。如使用贪心算法求解问题获得全局最优解，则问

5、题应满足1）贪心选择性质（与动态规划的主要区别）所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到2）最优子结构性质（动态规划算法和贪心算法的共同点）一个问题的最优解包含其子问题的最优解时。七、（15 分）请简要描述回溯法的实现过程。用回溯法求解 0/1 背包问题、TSP 问题、N 皇后问题时，其各自的解空间树各是什么形式？解：实现过程：确定解空间的组织结构，然后从开始结点（根结点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为扩展结点。否则如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）到最近的活结点处，并使该结点成为当前的扩展结点。回溯法按上述方式递归地在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。0/1 背包：n+1 层的子集树TSP 问题：(n-1)!个叶节点的排列树N 皇后问题：完全