《算法设计分析》由会员分享，可在线阅读，更多相关《算法设计分析（7页珍藏版）》请在金锄头文库上搜索。
1、第2次作业一、单项选择题（本大题共40分，共20小题，每小题2分）1. 在找零钱问题中，收银员算法中所应用的贪心规则的最恰当描述是（）。A. 总是选择面值最高的硬币B. 总是选择不超过剩余应找钱数的最大面值的硬币C. 总是选择面值是10，5的倍数的硬币D. 总是选择面值最小的硬币2. 由边界条件出发,通过递推式求f（n）的值，从边界到求解的全过程十分清楚 的是（）A. 贪心B. 递推C. 递归D. 概率3.考虑最长公共子序列问题的下述递归表达式，P_C53CE8FF336AA43839D03B6A499D5422如果全部子问题组织在一个ci,j的二维表格中，则ci,j不依赖于下述哪个 子问题：
2、（）。A. 同一行的上一列B. 同一列的上一行C. 上一行的上一列D. 同一行的下一列3. 找零钱问题中，定义Cj为兑换j所需要的硬币的最少数量，如果找出的第一个硬币为5分，则下述公式哪个是对的（）。A. Cj = 1 + Cj-5B. Cj = 5 + Cj-1C. Cj = 5 + Cj-5D. Cj = 1 + Cj-14. 大型程序设计一般用（）数据类型来描述算法。A. 逻辑B. 抽象C. 简明D. 复杂5. 在最优二叉搜索树问题中，我们的优化目标是（）。A. 只经过最少次数的比较就可以找到概率最大的元素B. 经过最多次数的比较就可以找到概率最小的元素C. 找到每个元素所需要的平均比较
3、次数为最小D. 元素搜索代价的数学期望为最小6. Edmonds-Karp算法中寻找增广路径的方法是（）。A. 深度优先算法B. 广度优先算法C. Prim算法D. Dijkstra 算法8.矩阵连乘问题里，对于矩阵链AAAAA,如果最外层加括号形式为(AA)一 .一、一 -_ , , 5 6 7 8 95 6(A7A8A9)，则子问题m5,9的子问题为()。A. m1,5,m6,9B. m5,6, m6,9C. m5,6, m7,10D. m5,6, m7,99. 当问题的规模n趋向无穷大时，()的数量级(阶)称为算法的渐进时间复 杂度。A. 时间复杂度B. 空间复杂度C. 冗余度D. 迭代
4、次数10. 下列算法中通常以自底向上的方式求解最优解的是()。A. 备忘录法B. 动态规划法C. 贪心法D. 回溯法11. 最优二叉搜索树的时间复杂度为()。A. O(n)B. O(n!)C. O(n2)D. O(ns)12. 递归函数f(n)=f(n-1)+n(n1)的递归出口是()。A. f(0)=0B. f(1)=1C. f(0)=1D. f(n)=n13. 下面是贪心算法的基本要素的是()。A. 重叠子问题B. 构造最优解C. 贪心选择性质D. 定义最优解14. 分治法所能解决的问题应具有的关键特征是()。A. 该问题的规模缩小到一定的程度就可以容易地解决B. 该问题可以分解为若十个规
5、模较小的相同问题C. 利用该问题分解出的子问题的解可以合并为该问题的解D. 该问题所分解出的各个子问题是相互独立的15. 在钢管切割问题里，如果用r表示长度为n英寸的钢管的最优切割方案所 获得的最大收益，且已知r所代表的最优解里，第一刀切下了 3英寸，则下述 公式哪一个是正确的？（）A. r = p + rB. n 3n-3r = r - 3C.r = r 3 + 3D.rn= r3 + p316. 程序可以不满足算法性质的（）A. 输入B. 输出C. 确定性D. 有限性17.考虑关于01背包问题的如下递归表达式，P_8BD35526A3C2328AA5A3718BBF7E29D3如果物品i的
6、重量小于背包的剩余容量，并且我们选择装入了物品i,则 OPT（i，w）的取值为（）。A. OPT（i-1,w）B. OPT（i-1,w-Wi）C. v + OPT（i-1,w-w）D. vi + OPT（i-1,wi） i17. 以下关于Huffmann树的描述，哪一项是错误的（）。A. Huffman树是满树B. 字符均在叶子结点上C. 最低频度的两个字符处于树的最底层，且互为兄弟D. 在树的同一层，字符的出现顺序会影响平均编码长度的数学期望18. 一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法 和备忘录算法相比：（）。A. 动态规划效果好B. 备忘录方法效果好C. 无法判
7、断D. 哪个效果好19. 关于解决最小代价生成树问题的Prim算法的下述说法，不正确的是（）。A. 优先队列Q中顶点的键值指这个顶点与A集合中点的最小权边的权重B. 从Q中取出一个顶点的实质是在应用MST性质选择连接A与V-A的最小权边C. 算法执行结束后，生成树有n-1个顶点D. 算法以优先队列为空为结束条件二、判断题（本大题共60分，共20小题，每小题3分）1.算法就是一组无穷的规则（）2.一个操作所需的时间和操作数的类型无关（）3.0-1背包问题，无论物件的顺序如何排列，动态规划总能获得最优解（）4.Huffmann编码树所对应的编码并不一定是前缀码。（）5.Prim算法是一种动态规划算
8、法。（）6.分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此, 分治法的计算效率通常可以用递归方程来进行分析（）7.贪心算法和动态规划算法都要求问题具有最优子结构性质（）。8.适宜于用贪心策略来解的问题都有两个特点:贪心选择性质和最优子结构。()9.f(n)=6X2n+m, f(n)的渐进性态 f(n)= (2n)()10.归并排序算法的基本思想是将待排序的元素分成大小大致相同的2个子集合()11.目前所知道的矩阵乘法的最好下界仍是它的平凡下界Q(n2)()12.程序必须满足算法具有数据输出的性质()13.选择排序、插入排序和归并排序算法中，插入算法是分治算法。()14.
9、递推是从内边界条件出发，通过递推式达到边界条件。()15.应用分治法的两个前提是问题的可分性和解的可归并性()16.有些数据结构如二叉树等，由于其本身的递归特性、特别适合用递归的形式来 描述。()17.如果全部元素的搜索概率是相等的，此时最优二叉搜索树应接近一棵完美二叉 树，其搜索代价与折半查找法相当。（）18.操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。（）19.证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的 最优子结构性质。（）20.对于01背包问题的动态规划算法，背包容量越大，算法执行所花费的时间越 多。（）答案：一、单项选择题（40分，共20题，每小题2分）1. B 2. B 3. D 4. A 5. B 6. D 7. B 8. D 9. A 10. B 11. D 12. B 13. C14. C 15. A 16. D 17. C 18. D 19. A 20. C 二、判断题（60分，共20题，每小题3分）1. X 2. X 3. V 4. X 5. X 6. V 7. V 8. V 9. V 10. X 11. V12. V 13. X 14. V 15. V 16. V 17. V 18. V 19. X 20. V
