算法分析与设计期末考试模拟试题一(3)

第 3 页 （共 4 页） 1. 最坏、最好、平均、最坏

2.

)(2n O 、)(log n O 3. 常数因子

4. 直接或间接地调用自身、用函数自身给出定义

5. 最好、局部最优选择

6. 贪心选择性质、最优子结构性质

7. 贪心算法、动态规划算法

8. 较小、互相独立、相同、合并

9. 最优子结构（性质）、子问题重叠（性质）

10.动态规划算法、贪心算法。

二、简答题答案（每小题10分，共计40分）

1. 如果只需要求解问题的最优值，动态规划算法步骤如下：

（1）找出最优解的性质，并刻画其结构特征；

（2）递归地定义最优值；

（3）以自底向上的方式计算出最优值；

如果需要构造最优解，则还需要加上如下步骤：

（4）根据计算最优值时得到的信息，构造最优解。

2. 所谓贪心选择性质是指，所求问题的全局最优解可以通过一系列局

部最优选择，即贪心选择来达到。

3. 如果G 的子图G ’是一棵包含G 的所有顶点的树，则称G ’为G 的生成树。生成树上各边权的总和称为该生成树的耗费。在G 的所有生成树中，耗费最小的生成树称为G 的最小生成树。

4. 动态规划算法需要知道所有子问题的解，而贪心算法不需要知道所有子问题的解，它只是在每一步迭代中选择看起来最好的解，并不从整体进行最优考虑，因此效率较高。

三、算法分析和设计题答案（每小题10分，共计20分）

1. 汉诺塔问题的递归算法如下:

public static void Hanoi(int n, int a, int b, int c)