1、 第 1次作业 一、单项选择题（本大题共 50分，共 20 小题，每小题 2.5 分） 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. 分治法
2、B. 动态规划法 C. 贪心法 D. 穷尽法 5. 直接或间接的调用自身的算法称为（ ）。 A. 贪心算法 B. 递归算法 C. 迭代算法 D. 动态规划算法 6. 算法分析的两个主要方面是（ ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 7. 下述关于最优子结构的说法，不正确的是（ ）。 A. 原问题的最优解包含子问题的最优解 B. 原问题的最优解建立在子问 题的最优解基础之上 C. 原问题的最优解依赖于子问题的最优解 D. 原问题的最优解通过子问题的非最优解合并而得 8. 阶乘函数用递归定义 Public static int factorial(int
3、n) if(n=0) return 1; return ( ) ; A. n*factorial(n) B. n*factorial(n-1) C. n*factorial(n-2) D. n*factorial(n+1) 9. 当 n越来越大时，下列函数中，增长速度最快的应该是（ ） A. y=100n B. y=log100n C. y=P_C9203B197463D285288CBC2B12D1D516 D. y=P_7C434CA91BB5C2CB760A50DB0E5A3E4E 10. 算法的时间复杂度是指（） A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程
4、中所需要的基本运算次数 D. 算法程序中的指令条数 11. 在活动安排问题中，下述哪项描述中的活动 A,B是相容的 （ ）？ A. 活动 A于活动 B 开始前开始 B. 活动 A于活动 B 结束 前开始 C. 活动 A于活动 B 开始前结束 D. 活动 A于活动 B 开始后开始 12. 衡量一个算法好坏的标准是（ ）。 A. 运行速度快 B. 占用空间少 C. 时间复杂度低 D. 代码短 13. 以下关于贪心算法，不正确的说法是 （ ）。 A. 用于解决优化问题 B. 总是选择在当前看来最好的选择 C. 期望通过局部最优达到全局最优 D. 所需求解的问题可以不满足最优子结构性质 14. 一个
5、p行 q列的矩形同一个 q行 r列的矩形相乘，总共要作多少次乘法运算？（ ） A. p x r B. q2 C. p x q x r D. q3 15. 在最优二叉搜索树问题中，考虑如下的 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
6、个元素分成个数大致相同的两半，取an/2与 x进行比较：如果（ ），则只要在数组 a的左半部继续搜索 x。 A. x an/2 B. x=an/2 C. xan/2 D. x=an/2 19. 备忘录方法的递归方式是 （ ） A. 自顶向下 B. 自右向左 C. 忽上忽下 D. 自底向上 20. 算法指的是（ ）。 A. 计算方法 B. 排序方法 C. 解决问题的方法和过程 D. 调度方法 二、判断题（本大题共 50 分，共 20 小题，每小题 2.5 分） 1. 最小代价生成树是贪心法的一个经典例子。 ( ) 2. 找零钱问题可以用动态规划算法求解。（ ） 3. 算法的时间复杂度与问题的规模
7、相关，是问题大小 n的函数 ( )。 4. 算法就是一组有穷的规则。 ( ) 5. 归并排序算法是渐近最优算法？ ( ) 6. 快速排序算法是基于贪心策略的一个算法 ( )。 7. 二分搜索方法在最坏的情况下用 O(log n)时间完成搜索任务 。（ ） 8. 钢管切割问题的顶层决策是要考虑第一刀应切下多长的钢管。（ ） 9. 在活动选择问题中，如果活动 A晚于活动 B 开始，则两个活动相容。（ ） 10. 对钢管切割问题反复应用 “ 总是切单位价值最高的允许长度 ” 的贪心规则可以获得最优解。（ ） 11. 要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度。 ( ) 12.
8、 0-1背包问题，无论物件的顺序如何排列，动态规划总能获得最优解 ( ) 13. 动态规划法其具体形式是多种多样的，但都具有相同的填表格式（ ）。 14. 如果两个序列的最后一个字符相同，则其最长公共子序列必以那个相同的字符结尾。（ ） 15. 算法是任何定义好了的计算程式，它取某些值或值的集合作为输入，并产生某些值或值的集合作为输出 ( )。 16. 归并排序算法是渐进最优算法？ ( ) 17. 活动选择问题的贪心算法所应用的贪心规则是 “ 总是选择持续时间最短的活动 ” 。（ ） 18. Ford-Fulkerson算法规定了增广路径的搜索算法 ( )。 19. f(n)=62 n+n2， f(n)的渐进性态 f(n)=(2n)（ ） 20. 快速排序是一个递归的算法 ( ) 答案： 一、单项选择题（ 50 分，共 20 题，每小题 2.5 分） 1. C 2. D 3. C 4. A 5. B 6. A 7. D 8. B 9. C 10. C 11. C 12. C 13. D 14. C 15. C 16. B 17. C 18. A 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.
