重庆大学2022年《算法设计分析 》( 第2次 )
发布时间:2023-05-31 14:05:02浏览次数:30第 2 次作业一、单项选择题(本大题共 60 分,共 20 小题,每小题 3 分)1. 对于 01 背包问题,定义: OPT(i, w) 背包容量为 w, 可选物品为 1..i 时的最优解所对应的最大收益。则 n 个物品,容量为 W 的原问题的最优解的最优值为( )。A. OPT(0,W)B. OPT(1,W)C. OPT(n,W)D. OPT(n+1,W)2. 实现快速排序算法如下: 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. Hu*man 编码的贪心算法所需的计算时间为( )。A. O(n2) B. O(nlogn)C. O(2n)D. O(n)4. 使用分治法求解不需要满足的条件是( )。A. 子问题必须是一样的 B. 子问题不能够重复C. 子问题的解可以合并D. 原问题和子问题使用相同的方法解5. 在钢管切割问题里,我们用如下递归表达式表达原问题的最优解的最优值:请问,其中的 i 是指什么?( )A. 1 英寸钢管的价值B. 子问题的钢管长度C. 第一刀所切割的钢管长度D. 价值/长度比6. Edmonds-Karp 算法中寻找增广路径的方法是( )。A. 深度优先算法B. 广度优先算法
C. Prim 算法D. Dijkstra 算法7. 矩阵连乘问题里,对于矩阵链 A5A6A7A8A9,如果最外层加括号形式为(A5A6)(A7A8A9),则子问题 m[5,9]的子问题为( )。A. m[1,5],' m[6,9]B. m[5,6], m[6,9]C. m[5,6], m[7,10]D. m[5,6], m[7,9]8. 找零钱问题中,定义 C[j]为兑换 j 所需要的硬币的最少数量,考虑下述递归表达式,下列关于对 i 的寻优的最恰当描述是( )。A. 考虑找出的第一个硬币面值的各种可能性B. 考虑先找给客户几分钱C. 考虑最多可以用几个硬币D. 考虑最少可以用几个硬币9. 算法必须具备输入、输出和( )等 5 个特性。A. 可执行性、可移植性和可扩充性B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性10. 当子问题之间包含公共的子问题则分治法要做许多不必要的工作,重复地解公共的子问题,此时一般用( )法较好。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. 下面是贪心算法的基本要素的是( )。A. 重叠子问题B. 构造最优解C. 贪心选择性质D. 定义最优解14. 分治法所能解决的问题应具有的关键特征是( )。A. 该问题的规模缩小到一定的程度就可以容易地解决B. 该问题可以分解为若干个规模较小的相同问题C. 利用该问题分解出的子问题的解可以合并为该问题的解D. 该问题所分解出的各个子问题是相互独立的15. 在钢管切割问题里,如果用 rn表示长度为 n 英寸的钢管的最优切割方案所获得的最大收益,且已知 rn所代表的最优解里,第一刀切下了 3 英寸,则下述公式哪一个是正确的?( )A. rn '= p3 + rn-3B. rn '= rn – 3C. rn '= rn-3 + 3D. rn '= r3 + p316. ( )是贪心算法与动态规划算法的共同点。A. 重叠子问题B. 构造最优解C. 贪心选择性质D. 最优子结构性质17.
使用分治法求解不需要满足的条件是( )。A. 子问题必须是一样的B. 子问题不能够重复C. 子问题的解可以合并D. 原问题和子问题使用相同的方法解18. 递归算法不能适用以下场合( )A. 数据的定义形式按递归定义B. 数据之间的关系(即数据结构)按递归定义C. 问题解法按递归算法实现D. 概率问题19. 在最优二叉搜索树问题中,定义 e[i, j ]为 ki,...,kj的最优二叉查找树的期望搜索成本,而我们需要通过寻优来确定最优二叉查找树的根结点的下标 r, 问,r的取值范围为( )。A. i≤r≤jB. 'i<r<jC. i≤r<jD. i<r≤j20. 程序可以不满足算法性质的( )A. 输入B. 输出C. 确定性D. 有限性二、判断题(本大题共 40 分,共 20 小题,每小题 2 分)1. Prim 算法是一种动态规划算法。( )2. 标准动态规划是在研究多阶段决策问题时推导出来的,具有严格的数学形式,适合用于理论上的分析。( )3. 如果两个序列的最后一个字符相同,则其最长公共子序列必以那个相同的字符结尾。( )4.
递归是从函数本身出发来达到边界条件。( )5. 备忘录方法可以看作是动态规划算法的变形( )6. Hu*mann 编码树一定是满树。( )7. 算法分析的目的是分析算法占用计算机资源的情况,对算法做出比较和评价,设计出额更好的算法 ( )8. 归并排序算法的基本思想是将待排序的元素分成大小大致相同的 2 个子集合( )9. 算法的渐进时间复杂性是指当问题的规模 n 趋向无穷大时,影响算法效率的重要因素是 T(n)的数量级,而其他因素仅是使时间复杂度相差常数倍,因此可以用 T(n)的数量级(阶)评价算法。时间复杂度 T(n)的数量级(阶)称为渐进时间复杂性。()10. 快速排序是一个递归的算法( )11. 对于最优二叉搜索树问题,搜索概率最高的元素一定在根结点上。( )12. 找零钱问题应用“找不超过当前剩余应找钱数的最大面值硬币”可以保证获得最优解。( )
13. 一个算法产生一个或多个输出,它们是同输入有某种特定关系的量( )14. 程序性能评估主要包含两方面,性能分析与性能测量( )15. 最优子结构性质特征反映了递归思想的应用 ( )16. 有些数据结构如二叉树等,由于其本身的递归特性、特别适合用递归的形式来描述。( )17. 对同一个问题,动态规划算法和分治算法计算复杂性可能是不同的( )。18. 分治法中的各个子问题是独立的( )19. 贪心法的当前选择不依赖于有待于做出的选择和子问题。( )20. 对于 01 背包问题的动态规划算法,背包容量越大,算法执行所花费的时间越多。 ( )答案:一、单项选择题(60 分,共 20 题,每小题 3 分)1. C 2. A 3. B 4. A 5. C 6. B 7. D 8. A 9. B 10. A 11. D 12. B 13. C 14.
C 15. A 16. D 17. A 18. D 19. A 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. √