算法设计分析 ( 第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. 下述关于最优子结构的说法，不正确的是（ ）。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. 在活动安排问题中，下述哪项描述中的活动A,B是相容的 （ ）？A. 活动A于活动B开始前开始B. 活动A于活动B结束前开始C. 活动A于活动B开始前结束D. 活动A于活动B开始后开始10. 衡量一个算法好坏的标准是（ ）。A. 运行速度快B. 占用空间少C. 时间复杂度低D. 代码短11. 在最长公共子序列问题中，如果定义 ci, j 为X1.i 和 Y1.j 的最长公共子序列的长度，则长度为m的X序列与长度为n的Y序列的最长公共子序列的长度为（ ）。A. c0,0B. c1,1C. c1,mD. cm,n12. 以下关于贪心算法，不正确的说法是 （ ）。A. 用于解决优化问题B. 总是选择在当前看来最好的选择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树，字符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. 自底向上二、判断题（本大题共40分，共 20 小题，每小题 2 分）1. 应用Huffmann编码的目的是用更少的比特流表达更多的信息。（ ）2. 两个序列的最长公共子序列可以帮助评价两个序列的相似度。（ ）3. 算法就是一组有穷的规则。( )4. 要想在电脑上扩大所处理问题的规模,有效的途径是提高算法的计算复杂度。( )5. 归并排序算法是渐近最优算法？( )6. 快速排序算法是基于贪心策略的一个算法( )。7. 二分搜索方法在最坏的情况下用O(log n)时间完成搜索任务。（ ）8. 快速排序法是基于分治策略的。 （ ）9. 基于三数取中划分的快速排序算法其最坏时间复杂度比基本的快速排序算法要好( )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. 能否利用分治法完全取决于问题是否具有如下特征：利用该问题分解出的子问题的解可以合并为该问题的解。( )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.