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

8. 分治法是将一个规模为n的问题分解为k个规模________的子问题，

这些子问题___________且与原问题__________。递归地求解这些子

问题，然后将各个子问题的解_________得到原问题的解。

9. 动态规划算法的两个基本要素是____________________和

____________________。

10.___ 算法可以有效地解凸多边形最优三角剖分问题，

而____________算法是求解最优装载问题的有效方法。

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

1. 如果只需要求解问题的最优值，动态规划算法步骤是什么？如果需要构造最优解，则还需要加上什么步骤？

2. 请简述什么是贪心选择性质

3. 请简述什么是最小生成树。

4. 请简述贪心算法比动态规划算法效率高的原因。

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

1. 请写出汉诺塔问题的简要递归算法。

2. 请设计一个在有序数组a[1..n]中二分搜索元素x的递归算法，要求若x在数组中则返回其下标否则返回0.

算法分析与设计模拟试题一答案

一、填空题答案（每小题4分，共计40分）

第 2 页（共 4 页）