1、第 1次作业一、单项选择题（本大题共 60分，共 20 小题，每小题 3 分）1. 设 mi, j 为计算矩阵链 Aij 所需的乘法运算次数的最小值，则矩阵链 A1n所需的乘法运算次数的最小值为（ ）。A. m0,nB. m1,n-1C. m1,n+1D. m1,n2. 二分搜索算法是基于（ ）设计的算法。A. 分治法B. 动态规划法C. 贪心法D. 穷尽法3. 直接或间接的调用自身的算法称为（ ）。A. 贪心算法B. 递归算法C. 迭代算法D. 动态规划算法4. 算法分析的两个主要方面是（ ）。A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性5. 下述关于最优子结构的说法
2、，不正确的是（ ）。A. 原问题的最优解包含子问题的最优解B. 原问题的最优解建立在子问题的最优解基础之上C. 原问题的最优解依赖于子问题的最优解D. 原问题的最优解通过子问题的非最优解合并而得6. 当 n越来越大时，下列函数中，增长速度最快的应该是（ ）A. y=100nB. y=log100nC. y=D. y=7. 实现归并排序利用的算法是（）。A. 分治策略 B. 动态规划法 C. 贪心法D. 回溯法8. 算法的时间复杂度是指（）A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数9. 在活动安排问题中，下述哪项描述中的活
3、动 A,B是相容的 （ ）？A. 活动 A于活动 B开始前开始B. 活动 A于活动 B结束前开始C. 活动 A于活动 B开始前结束D. 活动 A于活动 B开始后开始10. 衡量一个算法好坏的标准是（ ）。A. 运行速度快B. 占用空间少C. 时间复杂度低D. 代码短11. 在最长公共子序列问题中，如果定义 ci, j 为 X1.i 和 Y 1.j 的最长公共子序列的长度，则长度为 m的 X序列与长度为 n的 Y序列的最长公共子序列的长度为（ ）。A. c0,0B. c1,1C. c1,mD. cm,n12. 以下关于贪心算法，不正确的说法是 （ ）。A. 用于解决优化问题B. 总是选择在当前看
4、来最好的选择C. 期望通过局部最优达到全局最优D. 所需求解的问题可以不满足最优子结构性质13. 一个 p行 q列的矩形同一个 q行 r列的矩形相乘，总共要作多少次乘法运算？（ ）A. p x rB. q2C. p x q x rD. q314. 在最优二叉搜索树问题中，考虑如下的 BST:如果要搜索 k3 ，总共要经过多少次比较 （ ）。A. 1次B. 2次C. 3次D. 4次15. JAVA程序主要有以下两种类型（ ）A. 应用程序和 APPLET 应用程序和理论程序B. 系统程序和应用程序C. 系统程序和理论程序D. D系统程序和 APPLET应用程序16. 如图所示的 Huffmann
5、树，字符 s的编码是（ ）。A. 1010B. 1110C. 1111D. 01017. 适用动态规划解决的问题必须满足最优子结构和 ( )性质。A. 无后效性B. 无前效性C. 重叠子问题D. 递归18. 对于 n个元素的排序问题。 n2 时,只要作（ ）次比较即可排好序A. 3B. 2C. 1D. 419. 二分搜索算法的基本思想是将 n个元素分成个数大致相同的两半，取an/2与 x进行比较：如果（ ），则只要在数组 a的左半部继续搜索 x。A. xan/2B. x=an/2C. xan/2D. x=an/220. 备忘录方法的递归方式是 （ ）A. 自顶向下B. 自右向左C. 忽上忽下D
6、. 自底向上二、判断题（本大题共 40分，共 20 小题，每小题 2 分）1. 应用 Huffmann编码的目的是用更少的比特流表达更多的信息。（ ）2. 两个序列的最长公共子序列可以帮助评价两个序列的相似度。（ ）3. 算法就是一组有穷的规则。( )4. 要想在电脑上扩大所处理问题的规模,有效的途径是提高算法的计算复杂度。( )5. 归并排序算法是渐近最优算法？( )6. 快速排序算法是基于贪心策略的一个算法( )。7. 二分搜索方法在最坏的情况下用 O(log n)时间完成搜索任务。（ ）8. 快速排序法是基于分治策略的。 （ ）9. 基于三数取中划分的快速排序算法其最坏时间复杂度比基本的
7、快速排序算法要好( )10. 递归算法解题通常显得很简洁,而且运行效率较高？( )11. 最坏情况下的时间复杂度和平均时间复杂度一样。（ ）12. 计算机只能运行在有穷步内终止的算法。（）13. 在活动选择问题中，如果活动 A晚于活动 B开始，则两个活动相容。（ ）14. T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数 n0和 c，nn0，有 T(n)cf(n)，这种关系记作 T(n)=O(f(n)。 （ ）15. 动态规划的一个重要思想是要记住已经计算过的子问题的解。（ ）16. 能否利用分治法完全取决于问题是否具有如下特征：利用该问题分解出的子问题的解可以合并为该问题的
8、解。( )17. 贪心算法所做的选择都是目前最佳的( )。18. 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。( )19. 矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。（ ）20. 对钢管切割问题反复应用“总是切单位价值最高的允许长度”的贪心规则可以获得最优解。（ ）答案：一、单项选择题（60 分，共 20 题，每小题 3 分）1. D 2. A 3. B 4. A 5. D 6. C 7. A 8. C 9. C 10. C 11. D 12. D 13. C 14. C 15. A 16. B 17. C 18. C 19. A 20. A 二、判断题（40 分，共 20 题，每小题 2 分）1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
