第 1 次作业一、单项选择题（本大题共 60 分，共 20 小题，每小题 3 分）设 为计算矩阵链 所需的乘法运算次数的最小值，则矩阵链 所需的乘法运算次数的最小值为（ ）。二分搜索算法是基于（ ）设计的算法。分治法动态规划法贪心法穷尽法直接或间接的调用自身的算法称为（ ）。贪心算法递归算法迭代算法动态规划算法算法分析的两个主要方面是（ ）。空间复杂度和时间复杂度正确性和简单性可读性和文档性下述关于最优子结构的说法，不正确的是（ ）。原问题的最优解包含子问题的最优解原问题的最优解建立在子问题的最优解基础之上原问题的最优解依赖于子问题的最优解原问题的最优解通过子问题的非最优解合并而得当  越来越大时，下列函数中，增长速度最快的应该是（　　）实现归并排序利用的算法是（）。分治策略 动态规划法 贪心法回溯法算法的时间复杂度是指（）执行算法程序所需要的时间算法程序的长度算法执行过程中所需要的基本运算次数算法程序中的指令条数在活动安排问题中，下述哪项描述中的活动  是相容的 （ ）？活动  于活动  开始前开始活动  于活动  结束前开始活动  于活动  开始前结束活动  于活动  开始后开始衡量一个算法好坏的标准是（ ）。运行速度快占用空间少时间复杂度低代码短在最长公共子序列问题中，如果定义 为 !和 "的最长公共子序列的长度，则长度为  的 ! 序列与长度为  的 " 序列的最长公共子序列的长度为（ ）。    以下关于贪心算法，不正确的说法是 （ ）。用于解决优化问题总是选择在当前看来最好的选择期望通过局部最优达到全局最优所需求解的问题可以不满足最优子结构性质一个 # 行 $ 列的矩形同一个 $ 行 % 列的矩形相乘，总共要作多少次乘法运算？（ ）&#'%$&#'$'%$ 在最优二叉搜索树问题中，考虑如下的 ()*如果要搜索 +，总共要经过多少次比较 （ ）。 次 次 次 次,- 程序主要有以下两种类型（ ）应用程序和 ../0)应用程序和理论程序系统程序和应用程序系统程序和理论程序 系统程序和 ../0) 应用程序如图所示的 1234 树，字符 5 的编码是（ ）。 适用动态规划解决的问题必须满足最优子结构和 6&7性质。无后效性无前效性重叠子问题递归对于  个元素的排序问题。 ＝ 时只要作（ ）次比较即可排好序二分搜索算法的基本思想是将  个元素分成个数大致相同的两半，取48与 ' 进行比较：如果（ ），则只要在数组 4 的左半部继续搜索 '。'＜48'48'948'948备忘录方法的递归方式是 （ ）自顶向下自右向左忽上忽下 自底向上二、判断题（本大题共 40 分，共 20 小题，每小题 2 分）应用 1234 编码的目的是用更少的比特流表达更多的信息。（ ）两个序列的最长公共子序列可以帮助评价两个序列的相似度。（ ）算法就是一组有穷的规则。67要想在电脑上扩大所处理问题的规模有效的途径是提高算法的计算复杂度。67归并排序算法是渐近最优算法？67快速排序算法是基于贪心策略的一个算法67。二分搜索方法在最坏的情况下用 :67时间完成搜索任务。（ ）快速排序法是基于分治策略的。 （ ）基于三数取中划分的快速排序算法其最坏时间复杂度比基本的快速排序算法要好67递归算法解题通常显得很简洁而且运行效率较高？67 最坏情况下的时间复杂度和平均时间复杂度一样。（ ）计算机只能运行在有穷步内终止的算法。（）在活动选择问题中，如果活动  晚于活动  开始，则两个活动相容。（ ）)67是某算法的时间复杂性函数，;67是一简单函数，存在正整数 和 ，〉，有 )67< ;67，这种关系记作 )67:6;677。 （ ）动态规划的一个重要思想是要记住已经计算过的子问题的解。（ ）能否利用分治法完全取决于问题是否具有如下特征：利用该问题分解出的子问题的解可以合并为该问题的解。67贪心算法所做的选择都是目前最佳的67。任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。67矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。（ ） 对钢管切割问题反复应用“总是切单位价值最高的允许长度”的贪心规则可以获得最优解。（ ）答案：一、单项选择题（60 分，共 20 题，每小题 3 分）二、判断题（40 分，共 20 题，每小题 2 分）===>=>==>>>=>======>