第 2 次作业一、单项选择题（本大题共 60 分，共 20 小题，每小题 3 分）1. 一个长度为 n 英寸的钢管的最优切割问题，总共有多少个不同的子问题？（）A. n+1B. n2C. nlognD. logn2. 实现快速排序算法如下：QuickSort (A, p, r) IF p < r THEN q ← Partition(A, p, r) % (%%% ) % QuickSort(A, q+1, r) A. quickSort(p,q-1)B. quickSort(p+1,q-1)C. quickSort(p,q+1)D. quickSort(p,q-2)3. 在钢管切割问题里，我们用如下递归表达式表达原问题的最优解的最优值：请问，其中的 i 是指什么？（）A. 1 英寸钢管的价值B. 子问题的钢管长度C. 第一刀所切割的钢管长度D. 价值/长度比4. 在最优二叉搜索树问题中，我们的优化目标是（）。A. 只经过最少次数的比较就可以找到概率最大的元素B. 经过最多次数的比较就可以找到概率最小的元素C. 找到每个元素所需要的平均比较次数为最小 D. 元素搜索代价的数学期望为最小5. Edmonds-Karp 算法中寻找增广路径的方法是（）。A. 深度优先算法B. 广度优先算法C. Prim 算法D. Dijkstra 算法6. 关于 0，1 背包问题的下述形式化公式描述：下述说法不正确的是（）。A. i 表示物品的重量B. C 表示背包容量C. xi=0 表示编号为 i 的物品不被选择D. 求解目标是最大化装入背包内的物品的总价值7. 在活动安排问题中，如果把全部活动按照结束时间递增序排序后，按贪心算法，我们总是安排（）。A. 当前可选活动中结束时间最早的活动B. 当前可选活动中开始时间最早的活动C. 当前可选活动中冲突数量最少的活动D. 当前可选活动中持续时间最长的活动8. 找零钱问题中，定义C[j]为兑换 j 所需要的硬币的最少数量，考虑下述递归表达式， 下列关于对 i 的寻优的最恰当描述是（）。A. 考虑找出的第一个硬币面值的各种可能性B. 考虑先找给客户几分钱C. 考虑最多可以用几个硬币D. 考虑最少可以用几个硬币9. 算法必须具备输入、输出和（）等 5 个特性。A. 可执行性、可移植性和可扩充性B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性10. 当问题的规模 n 趋向无穷大时，（）的数量级(阶)称为算法的渐进时间复杂度。A. 时间复杂度B. 空间复杂度C. 冗余度D. 迭代次数11. 最优二叉搜索树的时间复杂度为（）。A. O(n)B. O(n!)C. O(n2)D. O(n3)12. 递归函数 f(n)=f(n-1)+n(n>1)的递归出口是( )。A. f(0)=0B. f(1)=1C. f(0)=1D. f(n)=n13. 在最优二叉搜索树问题中，定义 e[i, j ]为ki,...,kj的最优二叉查找树的期望搜索成本，而我们确定根结点下标为 r, 则其左子树的下标范围是（）。A. i..rB. i..r-1C. i..r+1D. i+1..r14. 下面是贪心算法的基本要素的是（）。A. 重叠子问题B. 构造最优解C. 贪心选择性质D. 定义最优解 15. 分治法所能解决的问题应具有的关键特征是（）。A. 该问题的规模缩小到一定的程度就可以容易地解决B. 该问题可以分解为若干个规模较小的相同问题C. 利用该问题分解出的子问题的解可以合并为该问题的解D. 该问题所分解出的各个子问题是相互独立的16. 在钢管切割问题里，如果用 rn表示长度为 n 英寸的钢管的最优切割方案所获得的最大收益，且已知 rn所代表的最优解里，第一刀切下了 3 英寸，则下述公式哪一个是正确的？（）A. rn %= p3 + rn-3B. rn %= rn – 3C. rn %= rn-3 + 3D. rn %= r3 + p317. （）是贪心算法与动态规划算法的共同点。A. 重叠子问题B. 构造最优解C. 贪心选择性质D. 最优子结构性质18. 使用分治法求解不需要满足的条件是（）。A. 子问题必须是一样的B. 子问题不能够重复C. 子问题的解可以合并D. 原问题和子问题使用相同的方法解19. 递归算法不能适用以下场合（）A. 数据的定义形式按递归定义B. 数据之间的关系(即数据结构)按递归定义C. 问题解法按递归算法实现D. 概率问题20. 程序可以不满足算法性质的（） A. 输入B. 输出C. 确定性D. 有限性二、判断题（本大题共 40 分，共 20 小题，每小题 2 分）1. 对于矩阵链连乘的子问题 m[i,j]，当 i=j 时表明该矩阵链有两个矩阵。（）2. 如果各子问题是不独立的，一般用动态规划法比分治法较差( )。3. 一般认为，执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。(% )%% 4. 如果两个序列的最后一个字符相同，则其最长公共子序列必以那个相同的字符结尾。（）5. 适宜于用贪心策略来解的问题都有两个特点:贪心选择性质和最优子结构。( )6. Hu@mann 编码树一定是满树。（）7. 分治法设计出的程序一般是一个递归过程( )8. f(n)=6×2n+n2，f(n)的渐进性态 f(n)=W(2n)（） 9. 算法分析的目的是分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法( )10. 快速排序是一个递归的算法( )11. 对于最优二叉搜索树问题，搜索概率最高的元素一定在根结点上。（）12. 0-1 背包问题，贪心选择能得到最优解。( )13. 贪心算法是一种不追求最优解，只希望得到较为满意解的方法。( )14. 绝大多数情况下，快速排序算法的时间复杂度位 O(n log(n))。（）15. 最优子结构性质特征反映了递归思想的应用( )16. 如果全部元素的搜索概率是相等的，此时最优二叉搜索树应接近一棵完美二叉树，其搜索代价与折半查找法相当。（）17. 分治法的基本思想是将一个规模较大的问题分解成若干个规模较小的问题，这些子问题之间并不一定相互独立( )18. 操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。( )19. 对同一个问题，动态规划算法和分治算法计算复杂性是一样的。（）20. 对于 01 背包问题的动态规划算法，背包容量越大，算法执行所花费的时间越多。（）答案：一、单项选择题（60 分，共 20 题，每小题 3 分）1. A 2. A 3. C 4. D 5. B 6. A 7. A 8. A 9. B 10. A 11. D 12. B 13. B 14. C 15. C 16. A 17. D 18. A 19. D 20. D 二、判断题（40 分，共 20 题，每小题 2 分）1. × 2. × 3. √ 4. √ 5. √ 6. √ 7. √ 8. √ 9. √ 10. √ 11. × 12. × 13. × 14. √ 15. √ 16. √ 17. √ 18. √ 19. × 20. √