1、 第 2次作业 一、单项选择题（本大题共 50分，共 20 小题，每小题 2.5 分） 1. 实现快速排序算法如下： 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. 重叠子问题 B. 构造最优解 C. 贪心选择性质 D. 定义最优解 14. 在钢管切割问题里，如果用 rn表示长度为 n英寸的钢管的最优切割方案所获得的最大收益，且已知 rn所代表的最优解里，第一刀切下了 3英寸，则下述公式哪一个是正确的？（ ） A. rn = p3 +
2、 rn-3 B. rn = rn 3 C. rn = rn-3 + 3 D. rn = r3 + p3 15. 使用分治法求解不需要满足的条件是（ ）。 A. 子问题必须是一样的 B. 子问题不能够重复 C. 子问题的解可以合并 D. 原问题和子问题使用相同的方法解 16. 程序可以不满足算法性质的（ ） A. 输入 B. 输出 C. 确定性 D. 有限性 17. 考虑关于 01背包问题的如下递归表达式，如果物品 i的重量小于背包的剩余容量，并且我们选择装入了物品 i,则OPT(i， w)的取值为（ ）。 A. OPT(i-1,w) B. OPT(i-1,w-wi) C. vi + OPT(i
3、-1,w-wi) D. vi + OPT(i-1,wi) 18. 以下关于 Huffmann 树的描述，哪一项是错误的 （ ）。 A. Huffman树是满树 B. 字符均在叶子结点上 C. 最低频度的两个字符处于树的最底层，且互为兄弟 D. 在树的同一层，字符的出现顺序会影响平均编码长度的数学期望 19. 一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法和备忘录算法相比： （ ）。 A. 动态规划效果好 B. 备忘录方法效果好 C. 无法判断 D. 哪个效果好 20. 关于解决最小代价生成树问题的 Prim算法的下述说法，不正确的是 （ ）。 A. 优先队列 Q中顶点的键值指
4、这个顶点与 A集合中点的最小权边的权重 B. 从 Q中取出一个顶点的实质是在应用 MST 性质选择连接 A与 V-A 的最小权边 C. 算法执行结束后，生成树有 n-1个顶点 D. 算法以优先队列为空为结束条件 二、判断题（本大题共 50 分，共 20 小题，每小题 2.5 分） 1. 在通往边界条件的递归调用过程中，系统用堆栈保存的每次调用的中间结果是局部变量和返回地址值。 ( ) 2. 0-1背包问题的计算时间与物件的排列顺序有关。 ( ) 3. 选择排序、插入排序和归并排序算法 中，插入算法是分治算法。 （ ） 4. 贪心算法是一种不追求最优解，只希望得到较为满意解的方法。 ( ) 5.
5、 静态方法的调用方式是：方法名（实际参数）。 ( ) 6. 动态规划的实质是分治思想和解决冗余 ( )。 7. 最坏情况下的时间复杂度决定算法的优劣，并且最坏情况下的时间复杂度较平均时间复杂度有可操作性。（ ） 8. 绝大多数情况下，快速排序算法的时间复杂度位 O(n log(n)。 （ ） 9. 找零钱问题应用 “ 找不超过当前剩余应找钱数的最大面值硬币 ” 可以保证获得最优解。（ ） 10. 程序性能评估主要包含两方面，性能分析与性能测量 ( ) 11. 有些数据结构如二叉树等，由于其本身的递归特性、特别适合用递归的形式来描述。 ( ) 12. 如果全部元素的搜索概率是相等的，此时最优二叉
6、搜索树应接近一棵完美二叉树，其搜索代价与折半查找法相当。（ ） 13. 对同一个问题，动态规划算法和分治算法计算复杂性可能是不同的 ( )。 14. 分治法的基本思想是将一个规模较大的问题分解成若干个规模较小的问题，这些子问题之间并不一定相互独立 ( ) 15. 贪心法的当前选择不依赖于 有待于做出的选择和子问题。 ( ) 16. 操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。 ( ) 17. 消除递归一般要用到栈这种数据结构（ ） 18. 对同一个问题，动态规划算法和分治算法计算复杂性是一样的。（ ） 19. 证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的
7、最优子结构性质。（ ） 20. 对于 01背包问题的动态规划算法，背包容量越大，算法执行所花费的时间越多。 （ ） 答案： 一、单项选择题（ 50 分，共 20 题，每小题 2.5 分） 1. A 2. A 3. C 4. B 5. A 6. A 7. D 8. A 9. B 10. A 11. D 12. B 13. C 14. A 15. A 16. D 17. C 18. D 19. A 20. C 二、判断题（ 50 分，共 20 题，每小题 2.5 分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
