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