1、 第 1次作业 一、单项选择题（本大题共 60分，共 20 小题，每小题 3 分） 1. 衡量一个算法好坏的标准是 ( ）。 A. 运行速度快 B. 占用空间少 C. 时间复杂度低 D. 代码短 2. 设 mi, j 为计算矩阵链 Aij 所需的乘法运算次数的最小值，则矩阵链 A1n所需的乘法运算次数的最小值为（ ）。 A. m0,n B. m1,n-1 C. m1,n+1 D. m1,n 3. 当问题的最优解包含了其子问题的最优解时，称该问题具有（ ）。 A. 可解性质 B. 最优 解性质 C. 最优子结构性质 D. 独立分解性质 4. 二分搜索算法是基于（ ）设计的算法。 A. 分治法 B
2、. 动态规划法 C. 贪心法 D. 穷尽法 5. 直接或间接的调用自身的算法称为（ ）。 A. 贪心算法 B. 递归算法 C. 迭代算法 D. 动态规划算法 6. 当 n越来越大时，下列函数中，增长速度最快的应该是（ ） A. y=100n B. y=log100n C. y= D. y= 7. 算法的时间复杂度是指（） A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过 程中所需要的基本运算次数 D. 算法程序中的指令条数 8. 在活动安排问题中，下述哪项描述中的活动 A,B是相容的 （ ）？ A. 活动 A于活动 B 开始前开始 B. 活动 A于活动 B 结束前开始 C
3、. 活动 A于活动 B 开始前结束 D. 活动 A于活动 B 开始后开始 9. 应用分治法的两个前提是（ ）。 A. 问题的可分性和解的可归并性 B. 问题的可分性和解的存在性 C. 问题的复杂性和解的可归并性 D. 问题的可分性和解的复杂性 10. 衡量一个算法好坏的标准是（ ）。 A. 运行速度快 B. 占用空间少 C. 时间复杂度低 D. 代码短 11. 在最长公共子序列问题中，如果定义 ci, j 为 X1.i 和 Y1.j 的最长公共子序列的长度，则长度为 m的 X序列与长度为 n 的 Y序列的最长公共子序列的长度为（ ）。 A. c0,0 B. c1,1 C. c1,m D. cm
4、,n 12. 以下关于贪心算法，不正确的说法是 （ ）。 A. 用于解决优化问题 B. 总是选择在当前看来最好的选择 C. 期望通过局部最优达到全局最优 D. 所需求解的问题可以不满足最优子结构性质 13. 一个 p行 q列的矩形同一个 q行 r列的矩形相乘，总共要作多少次乘法运算？（ ） A. p x r B. q2 C. p x q x r D. q3 14. 合并排序法的基本思想是：将待排序元素分成大小大致相同的（ ）个子集合，分别对每个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 A. 4 B. 3 C. 2 D. 5 15. 在最优二叉搜索树问题中，考虑如下的
5、BST: 如果要搜索 k3 ，总共要经过多少次比较 （ ）。 A. 1次 B. 2次 C. 3次 D. 4次 16. 如图所示的 Huffmann 树， 字符 s的编码是（ ）。 A. 1010 B. 1110 C. 1111 D. 010 17. 适用动态规划解决的问题必须满足最优子结构和 ( )性质。 A. 无后效性 B. 无前效性 C. 重叠子问题 D. 递归 18. 对于 n个元素的排序问题。 n 2时 ,只要作（ ）次比较即可排好序 A. 3 B. 2 C. 1 D. 4 19. 备忘录方法的递归方式是 （ ） A. 自顶向下 B. 自右向左 C. 忽上忽下 D. 自底向上 20.
6、算法指的是（ ）。 A. 计算方法 B. 排序方法 C. 解决问题的方法和过程 D. 调度方法 二、判断题（本大题共 40 分，共 20 小题，每小题 2 分） 1. 最小代价生成树是贪心法的一个经典例子。 ( ) 2. 应用 Huffmann编码的目的是用更少的比特流表达更多的信息。（ ） 3. 算法的时间复杂度与问题的规模相关，是问题大小 n的函数 ( )。 4. 两个序列的最长公共子序列可以帮助评价两个序列的相似度。（ ） 5. 归并排序算法是渐近最优算法？ ( ) 6. 递归 定义必须是有确切含义是指必须一步比一步简单 ,最后是有终结的 ,决不能无限循环下去？ ( ) 7. 快速排序算
7、法是基于贪心策略的一个算法 ( )。 8. 二分搜索方法在最坏的情况下用 O(log n)时间完成搜索任务。（ ） 9. 基于三数取中划分的快速排序算法其最坏时间复杂度比基本的快速排序算法要好 ( ) 10. 算法就是一组有穷的规则？ ( ) 11. 钢管切割问题的顶层决策是要考虑第一刀应切下多长的钢管。（ ） 12. 计算机只能运行在有穷步内终止的算法。（） 13. 计算时间的数量级的 大小对算法的有效性有决定性的影响 ( ) 14. 由于矩阵乘法满足结合律，所以计算矩阵的连乘积不可以有许多不同的计算次序 ( )。 15. 能够用动态规划解决的问题有一个显著特征：子问题的重叠性。 ( ) 1
8、6. 在活动选择问题中，如果活动 A晚于活动 B 开始，则两个活动相容。（ ） 17. 贪心算法所做的选择都是目前最佳的 ( )。 18. 分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。 ( ) 19. 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。 ( ) 20. 对钢管切割问题反复应用 “ 总是切单位价值最高的允许长度 ” 的贪心规则可以获得最优解。（ ） 答案： 一、单项选择题（ 60 分，共 20 题，每小题 3 分） 1. C 2. D 3. C 4. A 5. B 6. C 7. C 8. C 9. A 10. C 11. D 12. D 13. C 14. C 15. C 16. B 17. C 18. C 19. A 20. C 二、判断题（ 40 分，共 20 题，每小题 2 分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
