1、 第 2次作业 一、单项选择题（本大题共 60分，共 20 小题，每小题 3 分） 1. 对于 01背包问题，定义： OPT(i, w) 背包容量为 w, 可选物品为 1.i时的最优解所对应的最大收益。则 n个物品，容量为 W的原问题的最优解的最优值为 （ ）。 A. OPT(0,W) B. OPT(1,W) C. OPT(n,W) D. OPT(n+1,W) 2. 实现快速排序算法如下： QuickSort (A, p, r) IF p 1)的递归出口是 ( )。 A. f(0)=0 B. f(1)=1 C. f(0)=1 D. f(n)=n 13. 下面是贪心算法的基本要素的是（ ）。 A
2、. 重叠子问题 B. 构造最优解 C. 贪心选择性质 D. 定义最优解 14. 分治法所能解决的问题应具有的关键特征是（ ）。 A. 该问题的规模缩小到一定的程度就可以容易地解决 B. 该问题可以分解为若干个规模较小的相同问题 C. 利用该问题分解出的子问题的解可以合并为该问题的解 D. 该问题所分解出的各个子问题是相互独立的 15. 在钢管切割问题里，如果用 rn表示长度为 n英寸的钢管的最优切割方案所获得的最大收益， 且已知 rn所代表的最优解里，第一刀切下了 3英寸，则下述公式哪一个是正确的？（ ） A. rn = p3 + rn-3 B. rn = rn 3 C. rn = rn-3
3、+ 3 D. rn = r3 + p3 16. （ ）是贪心算法与动态规划算法的共同点。 A. 重叠子问题 B. 构造最优解 C. 贪心选择性质 D. 最优子结构性质 17. 使用分治法求解不需要满足的条件是（ ）。 A. 子问题必须是一样的 B. 子问题不能够重复 C. 子问题的解可以合并 D. 原问题和子问题使用相同的方法解 18. 递归算法不能适用以下场合（ ） A. 数据的定义形式按递归定义 B. 数据之间的关系 (即数据结构 )按递归定义 C. 问题解法按递归算法实现 D. 概率问题 19. 在最优二叉搜索树问题中，定义 ei, j 为 ki,.,kj的最优二叉查找树的期望搜索成本，
4、而我们需要通过寻优来确定最优二叉查找树的根结点的下标 r, 问， r的取值范围为（ ）。 A. irj B. irj C. irj D. irj 20. 程序可以不满足算法性质的（ ） A. 输入 B. 输出 C. 确定性 D. 有限性 二、判断题（本大题共 40 分，共 20 小题，每小题 2 分） 1. Prim算法是一种动态规划算法。（ ） 2. 标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。 ( ) 3. 如果两个序列的最后一个字符相同，则其最长公共子序列必以那个相同的字符结尾。（ ） 4. 递归是从函数本身出发来达到边界条件。 ( ) 5.
5、 备忘录方法可以看作是动态规划算法的变形（ ） 6. Huffmann编码树一定是满树。（ ） 7. 算法分析的目的是分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法 ( ) 8. 归并排序算法的基本思想是将待排序的元素分成大小大致相同的 2个子集合 ( ) 9. 算法的渐进时间复杂性是指当问题的规模 n 趋向无穷大时，影响算法效率的重要因素是 T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用 T(n)的数量级 (阶 )评价算法。时间复杂度 T(n)的数量级 (阶 )称为渐进时间复杂性。（） 10. 快速排序是一个递归的算法 ( ) 11. 对于最优二叉
6、搜索树问题，搜索概率最高的元素一定在根结点上。（ ） 12. 找零钱问题应用 “ 找不超过当前剩余应找钱数的最大面值硬币 ” 可以保证获得最优解。（ ） 13. 一个算法产生一个或多个输出，它们是同输入有某种特定关系的量 ( ) 14. 程序性能评估主要包含两方面，性能分析与性能测量 ( ) 15. 最优子结构性质特征反映了递归思想的应用 ( ) 16. 有些数据结构如二叉树等，由于其本身的递归特性、特 别适合用递归的形式来描述。 ( ) 17. 对同一个问题，动态规划算法和分治算法计算复杂性可能是不同的 ( )。 18. 分治法中的各个子问题是独立的 ( ) 19. 贪心法的当前选择不依赖于
7、有待于做出的选择和子问题。 ( ) 20. 对于 01背包问题的动态规划算法，背包容量越大，算法执行所花费的时间越多。 （ ） 答案： 一、单项选择题（ 60 分，共 20 题，每小题 3 分） 1. C 2. A 3. B 4. A 5. C 6. B 7. D 8. A 9. B 10. A 11. D 12. B 13. C 14. C 15. A 16. D 17. A 18. D 19. A 20. D 二、判断题（ 40 分，共 20 题，每小题 2 分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
