|
第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[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 所需要的硬币的最少数量，考虑下述递归表达式，
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[i, j ]为 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背包问题的动态规划算法，背包容量越大，算法执行所花费的时间越多。 （ ）
| 
