算法分析与设计(山东财经大学) 中国大学mooc慕课答案2024版 m289033
1.1 知识梳理
1、
给定男孩和女孩的两张喜欢列表，GS算法的结果对（ ）是最好的选择。
答案: 男孩
2、
稳定匹配问题的输出是（ ）
答案: 完美匹配 ;
没有不稳定配对 ;
稳定匹配
3、
给定一个匹配，如果Z喜欢A甚于匹配的女朋友，A喜欢Z甚于匹配的男朋友，那么A和Z是一个不稳定配对。
答案: 正确
4、
任意给定两张喜欢列表，稳定匹配问题只有一个稳定匹配。
答案: 错误
1.2 知识梳理
1、
解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
答案: (3)(1)(5)(4)(2)
2、
问题的两个要素是（ ）和（）
答案: 输入;
输出
3、
算法的性质有（）
答案: 确定性;
有穷性;
输入;
输出
4、
程序总是在有穷步的运算后终止。
答案: 错误
5、
算法是一步步正确解决问题的方法或策略。
答案: 正确
6、
程序是算法用某种程序设计语言的具体实现，不能使用自然语言描述。
答案: 正确
7、
算法每次求解一个实例，而计算机需要求解该问题的所有实例。
答案: 错误
1.3 知识梳理
1、
从右向左计算p(x) = anxn + an-1xn-1 +… + a1x1 + a0 的数量级为（）
答案: n
2、
问题变换的目的（）
答案: 复杂变简单;
未知变已知;
隐式变显式;
难解变易解
3、
传教士和野人问题转换的图是状态空间图。
答案: 正确
4、
大学入学问题的核心是稳定匹配问题
答案: 正确
5、
一个问题的实例可以变换为更简单更便利的实例，变换为不同的表达形式。
答案: 正确
第一章 测验
1、
算法与程序的区别是（）
答案: 有穷性
2、
解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
答案: (3)(1)(5)(4)(2)
3、
下面说法关于算法与问题的说法错误的是（）。
答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。
4、
问题变换的目的有（）。(1)复杂变简单 (2)未知变已知 (3)隐式变显式 (4)难解变易解 （5）以上都是。
答案: (5)
5、
按照霍纳法则，计算p(x) = anxn + an-1xn-1 +… + a1x1 + a0 的数量级为（）
答案: n
6、
描述算法的基本方法有( )。(1)自然语言(2)流程图(3)伪代码(4)机器语言
答案: B.(1)(2)(3)
7、
问题变换的方法有（ ）
答案: 实例简单化;
问题约简 ;
表达变换
8、
下面关于程序和算法的说法正确的是（）。
答案: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。;
程序是算法用某种程序设计语言的具体实现。;
算法是一个过程，计算机每次求解是针对问题的一个实例求解
9、
最大独立集问题和（）问题等价。
答案: 最大团;
最小顶点覆盖
10、
给定两张喜欢列表，稳定匹配问题的输出是（ ）
答案: 完美匹配;
没有不稳定配对;
最大匹配 ;
稳定匹配
11、
给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。
答案: 错误
12、
计算机每次求解是针对问题的每个实例求解。
答案: 错误
13、
同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
答案: 正确
14、
证明算法不正确，只需给出一个反例，算法不能正确处理即可。
答案: 正确
15、
同一算法只有一种形式描述
答案: 错误
16、
一个问题的同一实例可以有不同的表示形式。
答案: 正确
17、
算法必须在有穷时间终止
答案: 正确
18、
一个问题的算法必须在有穷时间终止，并且对一切合法的输入都能得出满足要求的结果。
答案: 正确
19、
问题的两个要素是输入和实例。
答案: 错误
20、
算法是一个语句集合，按照顺序执行语句，处理实例，得到正确答案。
答案: 正确
第二章 算法分析
2.1 知识梳理
1、
计算算法的时间复杂度只要选取()
答案: 最复杂部分的运行时间 ;
关键操作的运行时间 ;
在最坏情况下运行时间
2、
算法分析的两种方法是事前分析和事后统计。
答案: 正确
3、
算法分析的两个阶段是粗粒度比较数量级和细粒度比较各种情况。
答案: 正确
4、
求解问题的输入量,称为问题的规模。
答案: 正确
5、
时间复杂度就是算法运行的时间的度量，衡量算法的效率。
答案: 正确
2.2 知识梳理
1、
g(n)为f(n)的下界,记为:f(n)= (g(n))
答案: Ω
2、
f(n)=3n^3+7n^2+4nlogn =（ ）(n^3）
答案: θ
3、
O(f(n))+O(g(n)) = O(min{f(n),g(n)})
答案: 错误
4、
任何多项式时间算法都是好算法，都是有效的。
答案: 错误
5、
f(n)=
(g(n)) 则 f(n)=Ο(g(n))且f(n)=Ω(g(n))
答案: 正确
6、
f=o(g)且g = o(h) 则 f=o(h)
答案: 正确
2.3 知识梳理
1、
如果 
=0, 则 f(n)= (g（(n)）
答案: o
2、
logn!=Q( )
答案: nlogn
3、
n!=()
答案: 
;
4、
答案: 正确
5、
对于任意 x > 0, log n = o(n^x)
答案: 正确
6、
, 常数a, b > 0.
答案: 正确
7、
对任意 r > 1 和 d > 0, nd = o(r^n).
答案: 正确
8、
, 常数a, b > 0.
答案: 正确
2.4 知识梳理
1、
顺序查找的时间复杂度为（）
答案: θ(n)
2、
下面程序的时间复杂度是（） i=1while(i<=n) do i=i*3
答案: Q(logn)
3、
快速幂求x^n的时间复杂度为O（）
答案: logn
4、
T1(n)+T2(n)=O(max(f(n),g(n)))，因此并行语句时间复杂度等于两者中高的复杂度。
答案: 正确
5、
O(f)*O(g)=O(f*g)，因此循环语句的时间复杂度等于循环体的时间复杂度与循环次数的乘积。
答案: 正确
6、
从n个数中查找最大值的时间复杂度为W (n)
答案: 错误
2.5 知识梳理
1、
给定图G=(V,E), |V|=n, |E|=m, 其邻接矩阵的空间复杂度为( )
答案: θ(n^2)
2、
下面以空间换时间的方法有（）
答案: 预处理 ;
预构造 ;
动态规划
3、
空间复杂度S(n)是算法执行所需所有空间的资源量
答案: 错误
4、
时空均衡可通过以时间换空间或以空间换时间实现
答案: 正确
5、
给定n个整数，n个数的取值范围为[1,k], 计数排序的时间复杂度是O （n+k） 。
答案: 正确
6、
使用散列可以降低查找的时间复杂度
答案: 正确
第二章 测验
1、
从资源划分，算法的复杂度分为()和()。
答案: 时间复杂度 空间复杂度
2、
算法复杂度分析的两种基本方法为（ ）和（ ）
答案: 事后统计 事前分析
3、
设f（N）、g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当N≥N0时有f（N）≥Cg（N），则称函数f（N）当N充分大时有下界g（N），记作f（N）=W（g（N）），即f（N）的阶（ ）g（N）的阶。
答案: 不低于
4、
f(n)= 100 当n为奇数 f(n)=5n^2+3n. 当n为偶数 f(n)的渐进性态f(n)= W( )
答案: 1
5、
下面程序的时间复杂度为（） x=1for i=1 to n dofor j=1 to i do for k=1 to j do
x++
答案: n^3
6、
对近似递增序列的线性表从小到大排序，使用哪种方法好？
答案: 插入排序
7、
给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。
答案: 100
8、
给定图G=(V,E), |V|=n, |E|=m, 遍历其邻接表的时间复杂度为θ( )
答案: n+m
9、
logn!=Q( )
答案: nlogn
10、
给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。
答案: 100
11、
下面程序的时间复杂度是（） i=1while(i<=n)
do i=i*5
答案: Q(logn)
12、
给定n个整数，n个数的取值范围为[1,k],计数排序的时间复杂度是O （n+k） 。
答案: n+k
13、
给定图G=(V,E), |V|=n, |E|=m, 其邻接矩阵的空间复杂度为( )
答案: θ(n^2)
14、
顺序查找适合的数据结构是（）
答案: 顺序存储;
链式存储
15、
f(n)=3n^3+7n^2+4nlogn =（）（n^3）
答案: Ο;
Ω;
θ
16、
下面那些算法的时间复杂度为O（n^2）?
答案: 插入排序;
冒泡排序;
折半插入排序
17、
两个n*n的矩阵相加的时间复杂度是（ ）
答案: θ(n^2);
O(n^2);
W(n^2)
18、
以空间换时间的方法有（）
答案: 预处理 ;
预构造;
动态规划
19、
时间复杂度是指算法最坏情况下的运行时间。
答案: 正确
20、
f(n)=O(g(n)) 且 g(n)=O(h(n))，则h(n)=O(f(n))
答案: 错误
21、
f(n)=O(g(n)) 则 f(n)^2=O(g(n)^2)
答案: 正确
22、
f(n)=3n^3+7n^2+4nlogn =O（n^2）
答案: 错误
23、
如果一个算法是多项式时间算法，该算法是有效的,是好算法。
答案: 正确
24、
n!=o(2^n)
答案: 错误
25、
答案: 正确
26、
折半查找的时间复杂度为Q(nlogn)
答案: 错误
27、
f(n)=θ(g(n)) 当且仅当 g(n)=θ(f(n))
答案: 正确
28、
f=O(g)当且仅当 g =Ω (f)
答案: 正确
29、
时间复杂度就是算法运行的时间的度量，衡量算法的效率。
答案: 正确
30、
求解问题的输入量,称为问题的规模 。
答案: 正确
31、
O(f(n))+O(g(n)) = O(min{f(n),g(n)})
答案: 错误
32、
任何多项式时间算法都是好算法，都是有效的。
答案: 错误
33、
任何情况下，复杂性渐近阶低的算法都比复杂性渐近阶高的算法有效。
答案: 错误
34、
对任意 r > 1 和 d > 0, n^d= o(r^n).
答案: 正确
35、
f(n)=O(g(n)) 则 log（f(n)) =O(log(g(n)))
答案: 正确
36、
常数阶算法的运行时间与规模n无关。
答案: 正确
37、
从n个数中查找最大值的时间复杂度为W (n)
答案: 错误
38、
使用合适的数据结构可以同时减少时间和空间
答案: 正确
第三章 枚举算法
3.1 知识梳理
1、
枚举算法的优化方法有（）
答案: 减少枚举变量;
减少枚举变量的值域;
优化算法;
优化数学模型
2、
冒泡排序的时间复杂度为O(nlogn)
答案: 错误
3、
0/1背包问题的时间复杂度为O（n2^n）
答案: 正确
4、
在某些问题实例中枚举是唯一的解决方法。
答案: 正确
5、
最好情况下，冒泡排序和选择排序的时间复杂度都是O（n^2）
答案: 错误
3.2 知识梳理
1、
子集生成方法有（）
答案: 增量构造法;
二进制法;
位向量法
2、
位向量法生成子集，不直接构造子集本身。
答案: 正确
3、
二进制法生成子集，子集与运算可以生成并集
答案: 错误
4、
增量构造法生成子集前需要定序
答案: 正确
第三章 测验
1、
便于实现集合操作的子集生成算法是（）
答案: 二进制法
2、
logn^2=( )(logn+5)
答案: θ
3、
0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？
答案: 40
4、
A公司处理器速度是B公司的100倍。对于复杂度为n^2的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时能处理的问题规模是()
答案: 10n
5、
直接插入排序的时间复杂度是（）。
答案: O(n^2)
6、
选择排序的时间复杂度是O（____）
答案: n^2
7、
分数拆分问题的枚举算法通过（）方法进行了优化。
答案: 减少枚举变量 ;
减少枚举变量的值域 ;
优化数学模型
8、
子集生成方法有（）
答案: 增量构造法 ;
二进制法;
位向量法
9、
枚举算法的优化方法有（）
答案: 减少枚举变量 ;
减少枚举变量的值域 ;
优化算法;
优化数学模型
10、
冒泡排序的时间复杂度为W(n^2)
答案: 错误
11、
0-1背包问题的枚举算法的时间复杂度为O(2^n）
答案: 错误
12、
增量构造法生成子集前需要对集合中元素从小到大排列。
答案: 正确
13、
二进制法生成子集，子集与运算可以生成并集
答案: 错误
14、
枚举法适用于问题的小规模实例。
答案: 正确
15、
减少枚举变量可以减少枚举算法的时间复杂度
答案: 正确
16、
位向量法生成子集，子集或运算可以生成差集
答案: 错误
17、
分块查找一般设分块的长度是n/2.
答案: 错误
18、
旅行商问题的枚举算法的时间复杂度为O（n!）
答案: 正确
19、
在某些问题实例中枚举是唯一的解决方法。
答案: 正确
20、
蛮力法适用于问题的小规模实例。
答案: 正确
第四章 贪心算法
4.1 知识梳理
1、
部分背包问题的时间复杂度是O( )
答案: nlogn
2、
贪心算法的思想是依据贪婪准则作出决策，逐步构造解值。
答案: 正确
3、
贪心算法的思想是寻求局部最优解，逐步达到全局最优解
答案: 正确
4、
贪心算法总能找到可行解，并且是最优解。
答案: 错误
5、
部分背包问题的证明方法是领先的方法
答案: 正确
4.2 知识梳理
1、
原问题的最优解包含其子问题的最优解是最优子结构的性质。
答案: 正确
2、
通过一系列局部最优的选择（贪心选择）达到全局最优是贪心选择的性质
答案: 正确
3、
问题的全过程可以分为若干个阶段，而且在任何一个阶段x后的行为都只仅仅依赖于x的状态，而与x之前如何达到这种状态的方式无关。这是无后效性的性质
答案: 正确
4、
负权的最短路问题可以使用Dijkstra算法计算。
答案: 错误
5、
贪心法处理问题的核心是贪婪准则的选取
答案: 正确
6、
贪心算法一般在开始贪心策略前会进行预处理，预处理后再进行最优化选择。
答案: 正确
4.3 知识梳理
1、
区间调度问题贪心算法的时间复杂度是（）
答案: O(nlogn)
2、
交换论证方法把任意一个解逐渐变为贪心算法的解，不会影响其最优性。
答案: 正确
3、
区间划分问题的证明方法是界的方法
答案: 正确
4、
区间选点问题的预处理方法是按照区间的终点递增排序
答案: 正确
5、
区间调度问题可以变换为最大独立集问题
答案: 正确
4.4 知识梳理
1、
Kruskal算法的时间复杂度是()，更适用于稀疏图。
答案: mlogn
2、
最小生成树问题可以使用的算法有（ ）
答案: Kruskal ;
Prim;
Solim
3、
MST是最小连通子图包含n 个顶点和n-1条边
答案: 正确
4、
Prim算法的贪婪准则是选取割集中的最小边
答案: 正确
5、
Kruskal算法的预处理是边权非递减排序。
答案: 正确
6、
设S是顶点子集，e是正好一个端点在S中的边中的最小边，那么最小生成树中肯定包含e.
答案: 正确
4.5 知识梳理
1、
最优前缀码数属于（ ）
答案: 变长码;
前缀码 ;
哈夫曼编码
2、
前缀码中任一字符的0-1编码都不是其他字符的前缀
答案: 正确
3、
哈夫曼编码给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。
答案: 正确
4、
哈夫曼编码的预处理是根据频率大小，构造优先队列。
答案: 正确
第四章 测验
1、
贪心算法基本要素有（ ）和最优子结构性质。
答案: 贪心选择性质
2、
下面不是证明贪心算法证明方法的有（）。
答案: 优化
3、
未来与过去无关指的是（ ）的性质
答案: 无后效性
4、
使目标函数最大（小）的解是问题的（）
答案: 最优解
5、
对于稠密图，使用（）算法计算MST更适合
答案: Prim
6、
把任意一个解逐渐变为贪心算法的解，不会影响其最优性。这种证明方法是_()
答案: 交换论证
7、
原问题的最优解包含其子问题的最优解是贪心算法的（）性质。
答案: 最优子结构性质
8、
区间调度问题贪心算法的时间复杂度是（）
答案: O(nlogn)
9、
最小生成树问题可以使用的算法有（ ）
答案: Kruskal ;
Prim ;
Solim
10、
区间问题包含()
答案: 区间调度;
区间划分;
区间选点;
区间覆盖
11、
贪心算法的基本要素是（）
答案: 贪心选择的性质 ;
无后效性性质;
最优子结构性质
12、
贪心算法的证明方法有（）
答案: 领先 ;
交换论证;
界;
反证;
归纳
13、
最小生成树问题可以使用的算法有（ ）
答案: Kruskal ;
Prim ;
Solim
14、
最优前缀码数属于（ ）
答案: 变长码 ;
前缀码 ;
哈夫曼编码
15、
贪心算法总能找到可行解，但未必是最优解。
答案: 正确
16、
贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。
答案: 正确
17、
问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
答案: 正确
18、
MST中若在树中任意增加一条边，将出现一个回路；若去掉一条边，将变成非连通图。
答案: 正确
19、
设C是一个环， f 是C中的最大边，那么最小生成树中肯定包含f.
答案: 错误
20、
Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。
答案: 正确
21、
哈夫曼编码的平均码长最小
答案: 正确
22、
负权的单源最短路问题可以使用Dijkstra算法求解。
答案: 错误
23、
如果e是图G中权重最小的边，它至少是G的一颗最小生成树的边。
答案: 正确
24、
如果图G中每条边的权重都是互不相同的，图G必定只有一颗最小生成树。
答案: 正确
25、
问题的可行解是满足约束条件的解
答案: 正确
26、
贪心算法的思想是寻求局部最优解，逐步达到全局最优解
答案: 正确
27、
贪心算法总能找到可行解，并且是最优解。
答案: 错误
28、
负权的最短路问题可以使用Dijkstra算法计算。
答案: 错误
29、
未来不影响过去指的是无后效性的性质。
答案: 错误
30、
贪心法处理问题的核心是贪婪准则的选取
答案: 正确
31、
区间划分问题的预处理方法是按照开始时间递减排序。
答案: 错误
32、
区间选点问题的预处理方法是按照区间的终点递增排序
答案: 正确
33、
设S是顶点子集，e是正好一个端点在S中的边中的最小边，那么最小生成树中肯定包含e.
答案: 正确
34、
Kruskal算法的预处理是边权非递减排序。
答案: 正确
35、
任意变长码的平均码长最小
答案: 错误
36、
哈夫曼编码的贪婪准则是从队列中选择频率最小的两个。
答案: 正确
37、
哈夫曼编码给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。
答案: 正确
第五章 递推算法
5.1 知识梳理
1、
递归函数的要素是递归方程和（）
答案: 边界条件
2、
递归一般用于解决的问题有（）
答案: 数据的定义是按递归定义的;
问题解法按递归实现;
数据的结构形式是按递归定义的
3、
递推是从小规模的问题推解出大规模间题的一种方法，是选代算法的最基本的表现形式。
答案: 正确
4、
递归与循环都是解决“重复操作”的机制
答案: 正确
5、
递归的效率高于递推
答案: 错误
6、
每个递归算法原则上总可以转换成与它等价的迭代算法；反之不然 。
答案: 错误
5.2 知识梳理
1、
使用递推关系求解问题的常用方法有（）
答案: 递归 ;
正推 ;
倒推;
迭代
2、
倒推法是从后向前推解问题的方法.
答案: 正确
3、
不知前提条件的情况下，经常使用倒推求解问题。
答案: 正确
4、
由结果倒过来推解前提条件是倒推方法的一种
答案: 正确
5、
由于存储的要求从后向前进行推算是倒推方法的一种
答案: 正确
5.3 知识梳理
1、
迭代法分为（ ）
答案: 直接迭代;
差消迭代;
换元迭代
2、
求解递推方程的方法有（）
答案: 迭代法 ;
递归树;
归纳法;
主定理
3、
主方法可以求解满足T(n)=aT(n/b) + f (n) 形式的递推方程， 则下列关于方程正确的是？A 对于系数a，必须满足a>=1B对于系数b，必须满足b>1C若对于常数ε>0，f(n)=O(nlogba-ε)，则T(n)=Θ(nlogba)D若f(n)=O(nlogba)，则T(n)=Θ(nlogbalogn)
答案: 对于系数a，必须满足a>=1;
对于系数b，必须满足b>1;
若对于常数ε>0，
, 则
;
若
,则
4、
迭代法从原始递推方程出发，反复将对应方程左边的函数用右边等式带入，直至得到初值，然后将所得的结果化简。
答案: 正确
5、
迭代一般用于一阶递推方程，高阶方程需要使用差消法化简为一阶方程求解
答案: 正确
6、
快速排序平均情况下的时间复杂度是O（nlogn）
答案: 正确
第五章 测验
1、
从大规模问题逐步化为小规模问题的算法是（）
答案: 递归
2、
求解高阶递推方程一般使用（）迭代方法
答案: 差消迭代
3、
下面有关递归与迭代的说法错误的是（）
答案: 每个递归算法原则上总可以转换成与它等价的迭代算法
4、
主方法可以求解满足T(n)=aT(n/b) + f (n) 形式的递推方程， 则下列关于方程中的约束中不准确的是？
答案: 
5、
T(n) = 2T(n/2) +n^2，T(1)=1，则 T(n) =（）
答案: Q(n^2)
6、
从小规模问题推解出大规模问题的算法是（）
答案: 递推
7、
递归函数的要素是（）
答案: 边界条件 ;
递归方程
8、
递归变为非递归的方法有（）
答案: 模拟栈 ;
递推 ;
尾递归
9、
递归一般用于解决问题有（）：
答案: 数据的定义是按递归定义的。 ;
问题解法按递归实现。;
数据的结构形式是按递归定义的
10、
求解递推方程的迭代法分为（ ）
答案: 直接迭代 ;
差消迭代;
换元迭代
11、
T(n) = T(n-1) + n ，T(1)=1，则 T(n) =（）
答案: W(n^2);
n(n+1)/2;
(n^2);
Q(n^2)
12、
求解快速排序时间复杂度使用的方法有（）
答案: 迭代法 ;
递归树;
归纳法 ;
主定理
13、
正推是从小规模的问题推解出大规模间题的一种方法
答案: 正确
14、
循环用于重复性的工作。循环体的特点是：“以不变应万变”。
答案: 正确
15、
递归算法是直接或间接地调用自身的算法。
答案: 正确
16、
尾递归中的递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分。
答案: 正确
17、
一般来说，递归的效率高于递推。
答案: 错误
18、
递推是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题。
答案: 错误
19、
有些问题采用倒推法，容易理解和解决。
答案: 正确
20、
递归是从简单问题出发，一步步的向前发展，最终求得问题，是正向的。
答案: 错误
21、
一般来说，递推的效率高于递归,因此将递归转化为递推
答案: 正确
22、
每个递归算法原则上总可以转换成与它等价的迭代算法，反之不然。
答案: 错误
23、
由结果倒过来推解前提条件是倒推方法的一种。
答案: 正确
24、
迭代法从原始递推方程出发，反复将对应方程左边的函数用右边等式带入，直至得到初值，然后将所得的结果化简。
答案: 正确
25、
快速排序和插入排序最好情况下的时间复杂度是O（nlogn）
答案: 错误
第六章 分治算法
6.1 知识梳理
1、
合并排序的时间复杂度是O（）
答案: nlogn
2、
分治法的适用条件是（ ）。
答案: 问题可以分解为规模较小的子问题;
小规模子问题可解;
子问题可合并为问题的解 ;
子问题相互独立
3、
分治法的设计思想是大事化小，各个击破，分而治之。
答案: 正确
4、
每次都将问题分解为原问题规模的一半进行求解，称为二分法
答案: 正确
5、
分治法一般在每一层递归上有分解、解决、合并三个步骤
答案: 正确
6、
减治法是把一个问题转化成一个子问题来解决，从子问题的解得到原问题的解。
答案: 正确
7、
分治法将原问题分解为若干个规模较小、相互独立、完全相同的子问题。
答案: 错误
6.2 知识梳理
1、
减治法常见的形式有（）
答案: 减一个常量 ;
减一个常量因子;
减可变规模
2、
二分法子问题独立而不相似的情况可以转化为相似子问题求解
答案: 正确
3、
二分法子问题不独立的情况可以计算，但计算量大，一般使用动态规划计算。
答案: 正确
4、
N个元素排序的时间复杂度不可能是线性时间。
答案: 错误
5、
任何基于元素比较的排序算法的时间复杂度>=élogn!ù= Q(nlogn)
答案: 正确
6.3 知识梳理
1、
二分搜索算法将分治的2个子问题减少为1个，时间复杂度由n降低为logn
答案: 正确
2、
大整数乘法将分治的四个子问题减少为2个，时间复杂度由n2降低为n
答案: 错误
3、
Strassen矩阵乘法将分治的8个子问题减少为7个，时间复杂度由n3降低为n^log7
答案: 正确
4、
减少子问题的个数，可以降低分治算法的时间复杂度。
答案: 正确
5、
存在O(n2.376 )时间的矩阵乘法分治算法
答案: 正确
6.4 知识梳理
1、
改进分治的均衡度，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（）值。
答案: b
2、
随机快速排序的时间是O（n^2）
答案: 错误
3、
给定n个元素，找其中位数的时间是O（n）
答案: 正确
4、
给定n个元素，使用分治算法找k小元素，如果保证分治的两个子数组中最小的数组是原数组的ε倍，时间复杂度可以由nlogn降低为n. 0<ε<1.
答案: 正确
6.5 知识梳理
1、
减少合并时间，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（）值。
答案: f(n)
2、
最接近点对问题的时间复杂度为（）
答案: nlogn
3、
最接近点对问题将合并的时间从n^2减少为n，从而将算法的时间复杂度由n^减少为nlogn。
答案: 正确
4、
计数逆序问题将合并计数逆序的时间由n^2减少为n，从而将算法的时间复杂度由n^2减少为nlogn。
答案: 正确
第六章 测验
1、
设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用( )法。
答案: 冒泡排序
2、
堆排序的时间复杂度是O（）。
答案: O（nlogn）
3、
使用分治法求解不需要满足的条件是（ ）。
答案: 子问题必须是一样的
4、
找n个元素的中位数的分治算法的时间复杂度为O(___).
答案: n
5、
合并排序的时间复杂度是（）
答案: nlogn
6、
军事上迂回包围、穿插分割、各个歼灭是（）思想。
答案: 分治
7、
堆排序的时间复杂度是（）
答案: nlogn
8、
大整数乘法分治算法的时间为O（）
答案: n^log3
9、
对线性表进行折半查找最方便的数据结构是（)
答案: 有序顺序表
10、
减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（）值。
答案: a
11、
分治法在每一层递归上有三个步骤（）
答案: 分解;
解决 ;
合并
12、
通过减少子问题个数，降低分治算法时间复杂度的有（）
答案: 大整数乘法;
Strassen矩阵乘法
13、
分治法所能解决的问题一般具有（ ）特征.
答案: 问题可以分解为规模较小的子问题;
小规模子问题可解 ;
子问题可合并为问题的解 ;
子问题相互独立
14、
减治法常见的形式有（)
答案: 减一个常量;
减一个常量因子;
减可变规模
15、
改进分治算法的方法有（）
答案: 减少子问题的个数 ;
改进分治的均衡度;
减少合并的时间
16、
分治法分解的子问题与原问题形式相同。
答案: 正确
17、
N个元素排序的时间复杂度不可能是线性时间。
答案: 错误
18、
分治法分解的子问题与原问题形式相同。
答案: 正确
19、
三分法的判定树是三叉树
答案: 正确
20、
减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)
答案: 错误
21、
最小堆中每个元素调整的次数不超过树高 Q(logn)。
答案: 正确
22、
分治算法的思想是将难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。
答案: 正确
23、
任何排序算法至少需要O(nlog n)次比较。
答案: 错误
24、
改进子问题合并的时间复杂度可以减少分治算法的时间。
答案: 正确
25、
分治与递归都是从大规模问题逐步化为小规模问题，因此分治算法经常使用递归实现。
答案: 正确
26、
分治法将原问题分解为若干个规模较小、相互独立、完全相同的子问题。
答案: 错误
27、
减治法是把一个问题转化成一个子问题来解决，从子问题的解得到原问题的解。
答案: 正确
28、
任何基于元素比较的排序算法的时间复杂度>=élogn!ù= Q(nlogn)
答案: 正确
29、
建立n个元素的最大堆的时间为O(n)
答案: 正确
30、
存在O(n2.376 )时间的矩阵乘法分治算法
答案: 正确
31、
随机快速排序的时间是O（n^2）
答案: 错误
32、
给定n个元素，找其中位数的时间是O（n）
答案: 正确
33、
给定n个元素，使用分治算法找k小元素，如果保证分治的两个子数组中最小的数组是原数组的ε倍，时间复杂度可以由nlogn降低为n
答案: 正确
34、
两个有序数组合并的时间不会超过两个数组的长度和。
答案: 正确
第七章 动态规划
7.1 知识梳理
1、
下面不是动态规划算法特点的是（）
答案: 从大到小计算
2、
备忘录与递归算法的相同点是（）
答案: 递推关系;
最优子结构
3、
动态规划算法本质上是空间换时间的算法，每一个子问题只解一次,存储子问题结果，避免重复计算。
答案: 正确
4、
备忘录方法为每一子问题建立记录项，初始化时，存入特殊值。求解时遇到特殊值时计算并保存在相应记录项中，下次遇到时直接查表即可。
答案: 正确
5、
最优子结构是问题能用动态规划算法求解的前提。
答案: 正确
6、
通常不同的子问题个数随问题规模呈多项式增长。动态规划算法对于每个子问题求解一次，并保存子问题结果，因此只需要多项式时间。
答案: 正确
7.2 知识梳理
1、
确定第 i 阶段的收益函数和从第1阶段出发到第i 阶段末所获得收益的最优值，建立动态规划基本方程。这种方法是（）
答案: 正推
2、
动态规划定义递推关系的方法有（）
答案: 正推;
反推
3、
动态规划是“带决策的多阶段、多方位的递推算法”
答案: 正确
4、
给定n层数字三角形，动态规划计算的时间为O（n^3）
答案: 错误
5、
状态转移方程是状态间的递推关系，也是子问题间的递推关系。状态变量取值不同对应不同问题状态，也对应不同子问题。
答案: 正确
7.3 知识梳理
1、
OPT[i][w]=max{OPT[i-1][w],OPT[i][w-w[i]]+v[i]}，这是()问题的递推关系。
答案: 完全0-1背包
2、
OPT[i][w]=max{OPT[i-1][w],OPT[i-1][w-k*w[i]] +k*v[i]，0<=k<=n[i]}。这是()问题的递推关系。
答案: 多重0/1背包
3、
0-1背包问题的动态规划算法的时间复杂度是Q(n W)，是多项式时间算法.
答案: 错误
4、
恰好装满的0-1背包问题，初始化时除了M[0]为0，其它M[1..C]均设为-∞，可以保证最终得到的M[C]是一种恰好装满背包的最优解。
答案: 正确
7.4 知识梳理
1、
动态规划算法的计算矩阵连乘问题的时间为O（）
答案: n^3
2、
区间动态规划的计算次序是（）
答案: 先小区间后大区间;
先小规模后大规模
3、
区间动归使用链长，先计算小区间，再递增计算大区间。
答案: 正确
4、
矩阵连乘的计算次序可以用完全加括号的方式来确定。
答案: 正确
5、
矩阵连乘问题的不同子问题个数为 O（n^2）
答案: 正确
7.5 知识梳理
1、
拓扑排序的时间复杂度是O( )
答案: m+n
2、
动态规划计算最长不降子序列的时间是O（）
答案: n^2
3、
拓扑排序的结果是一个顶点序列，顶点间存在先序关系。
答案: 正确
4、
嵌套矩形问题本质上求DAG上的最长路径，但没有给出起点和终点。
答案: 正确
5、
反推求解嵌套矩形问题，很难打印字典序最小的方案。
答案: 错误
6、
硬币问题本质上是DAG上的最长路径和最短路，且给出起点和终点。
答案: 正确
7、
DAG图最长路的正推关系是 L(j) = 1 + max {L(i) : (i, j) 为边}
答案: 正确
7.7 知识梳理
1、
Floyd算法的复杂度为O（）
答案: n^3
2、
如果图中存在负环，那么从s到t没有最短路。
答案: 正确
3、
Bellman算法的计算时间为Q(mn), 空间为 Q(n^2)，可以求最短路，也可求最长路。
答案: 正确
4、
SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
答案: 正确
5、
Floyd算法可以构造无向或有向加权图（包含长度为负的回路）的完全最短路径
答案: 错误
6、
SPFA算法计算时，如果一个顶点入队列的次数超过n，则存在负权回路。
答案: 正确
7、
动态规划计算树上的最大独立集时，从叶子开始，先计算子树，逐步计算到根节点。
答案: 正确
7.8 知识梳理
1、
LCS问题的不同子问题个数为 O（）
答案: mn
2、
序列 
. 设LCS(X, Y)=
。若
则
，且
是
和
的最长公共子序列。
答案: 正确
3、
给定串
， 一个比对M是有序对 
的集合，每一项至多参与一个配对，并且允许交叉。
答案: 错误
4、
动态规划方程中子问题个数为n^t，依赖的子问题个数为n^e， 则算法的时间复杂度为n^(t+e)
答案: 正确
5、
序列的编辑距离是间隔的惩罚值和错配的惩罚值之和。
答案: 正确
6、
动态规划方程M[i,j]=min(M[k]+wk), 1≤i≤k≤j≤n, 则算法的时间复杂度为n^2
答案: 错误
下方是付费阅读内容：本平台商品均为虚拟商品，无法用作二次销售，不支持退换货，请在购买前确认您需要购买的资料准确无误后再购买，望知悉！
完整答案需点击上方按钮支付5元购买,所有答案均为章节测试答案，购买后上方矩形框将出现已付费的隐藏内容。
,
1、
给定男孩和女孩的两张喜欢列表，GS算法的结果对（ ）是最好的选择。
答案: 男孩
2、
稳定匹配问题的输出是（ ）
答案: 完美匹配 ;
没有不稳定配对 ;
稳定匹配
3、
给定一个匹配，如果Z喜欢A甚于匹配的女朋友，A喜欢Z甚于匹配的男朋友，那么A和Z是一个不稳定配对。
答案: 正确
4、
任意给定两张喜欢列表，稳定匹配问题只有一个稳定匹配。
答案: 错误
1.2 知识梳理
1、
解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
答案: (3)(1)(5)(4)(2)
2、
问题的两个要素是（ ）和（）
答案: 输入;
输出
3、
算法的性质有（）
答案: 确定性;
有穷性;
输入;
输出
4、
程序总是在有穷步的运算后终止。
答案: 错误
5、
算法是一步步正确解决问题的方法或策略。
答案: 正确
6、
程序是算法用某种程序设计语言的具体实现，不能使用自然语言描述。
答案: 正确
7、
算法每次求解一个实例，而计算机需要求解该问题的所有实例。
答案: 错误
1.3 知识梳理
1、
从右向左计算p(x) = anxn + an-1xn-1 +… + a1x1 + a0 的数量级为（）
答案: n
2、
问题变换的目的（）
答案: 复杂变简单;
未知变已知;
隐式变显式;
难解变易解
3、
传教士和野人问题转换的图是状态空间图。
答案: 正确
4、
大学入学问题的核心是稳定匹配问题
答案: 正确
5、
一个问题的实例可以变换为更简单更便利的实例，变换为不同的表达形式。
答案: 正确
第一章 测验
1、
算法与程序的区别是（）
答案: 有穷性
2、
解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
答案: (3)(1)(5)(4)(2)
3、
下面说法关于算法与问题的说法错误的是（）。
答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。
4、
问题变换的目的有（）。(1)复杂变简单 (2)未知变已知 (3)隐式变显式 (4)难解变易解 （5）以上都是。
答案: (5)
5、
按照霍纳法则，计算p(x) = anxn + an-1xn-1 +… + a1x1 + a0 的数量级为（）
答案: n
6、
描述算法的基本方法有( )。(1)自然语言(2)流程图(3)伪代码(4)机器语言
答案: B.(1)(2)(3)
7、
问题变换的方法有（ ）
答案: 实例简单化;
问题约简 ;
表达变换
8、
下面关于程序和算法的说法正确的是（）。
答案: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。;
程序是算法用某种程序设计语言的具体实现。;
算法是一个过程，计算机每次求解是针对问题的一个实例求解
9、
最大独立集问题和（）问题等价。
答案: 最大团;
最小顶点覆盖
10、
给定两张喜欢列表，稳定匹配问题的输出是（ ）
答案: 完美匹配;
没有不稳定配对;
最大匹配 ;
稳定匹配
11、
给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。
答案: 错误
12、
计算机每次求解是针对问题的每个实例求解。
答案: 错误
13、
同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
答案: 正确
14、
证明算法不正确，只需给出一个反例，算法不能正确处理即可。
答案: 正确
15、
同一算法只有一种形式描述
答案: 错误
16、
一个问题的同一实例可以有不同的表示形式。
答案: 正确
17、
算法必须在有穷时间终止
答案: 正确
18、
一个问题的算法必须在有穷时间终止，并且对一切合法的输入都能得出满足要求的结果。
答案: 正确
19、
问题的两个要素是输入和实例。
答案: 错误
20、
算法是一个语句集合，按照顺序执行语句，处理实例，得到正确答案。
答案: 正确
第二章 算法分析
2.1 知识梳理
1、
计算算法的时间复杂度只要选取()
答案: 最复杂部分的运行时间 ;
关键操作的运行时间 ;
在最坏情况下运行时间
2、
算法分析的两种方法是事前分析和事后统计。
答案: 正确
3、
算法分析的两个阶段是粗粒度比较数量级和细粒度比较各种情况。
答案: 正确
4、
求解问题的输入量,称为问题的规模。
答案: 正确
5、
时间复杂度就是算法运行的时间的度量，衡量算法的效率。
答案: 正确
2.2 知识梳理
1、
g(n)为f(n)的下界,记为:f(n)= (g(n))
答案: Ω
2、
f(n)=3n^3+7n^2+4nlogn =（ ）(n^3）
答案: θ
3、
O(f(n))+O(g(n)) = O(min{f(n),g(n)})
答案: 错误
4、
任何多项式时间算法都是好算法，都是有效的。
答案: 错误
5、
f(n)=(g(n)) 则 f(n)=Ο(g(n))且f(n)=Ω(g(n))
答案: 正确
6、
f=o(g)且g = o(h) 则 f=o(h)
答案: 正确
2.3 知识梳理
1、
如果 =0, 则 f(n)= (g（(n)）
答案: o
2、
logn!=Q( )
答案: nlogn
3、
n!=()
答案: ;
4、
答案: 正确
5、
对于任意 x > 0, log n = o(n^x)
答案: 正确
6、
, 常数a, b > 0.
答案: 正确
7、
对任意 r > 1 和 d > 0, nd = o(r^n).
答案: 正确
8、
, 常数a, b > 0.
答案: 正确
2.4 知识梳理
1、
顺序查找的时间复杂度为（）
答案: θ(n)
2、
下面程序的时间复杂度是（） i=1while(i<=n) do i=i*3
答案: Q(logn)
3、
快速幂求x^n的时间复杂度为O（）
答案: logn
4、
T1(n)+T2(n)=O(max(f(n),g(n)))，因此并行语句时间复杂度等于两者中高的复杂度。
答案: 正确
5、
O(f)*O(g)=O(f*g)，因此循环语句的时间复杂度等于循环体的时间复杂度与循环次数的乘积。
答案: 正确
6、
从n个数中查找最大值的时间复杂度为W (n)
答案: 错误
2.5 知识梳理
1、
给定图G=(V,E), |V|=n, |E|=m, 其邻接矩阵的空间复杂度为( )
答案: θ(n^2)
2、
下面以空间换时间的方法有（）
答案: 预处理 ;
预构造 ;
动态规划
3、
空间复杂度S(n)是算法执行所需所有空间的资源量
答案: 错误
4、
时空均衡可通过以时间换空间或以空间换时间实现
答案: 正确
5、
给定n个整数，n个数的取值范围为[1,k], 计数排序的时间复杂度是O （n+k） 。
答案: 正确
6、
使用散列可以降低查找的时间复杂度
答案: 正确
第二章 测验
1、
从资源划分，算法的复杂度分为()和()。
答案: 时间复杂度 空间复杂度
2、
算法复杂度分析的两种基本方法为（ ）和（ ）
答案: 事后统计 事前分析
3、
设f（N）、g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当N≥N0时有f（N）≥Cg（N），则称函数f（N）当N充分大时有下界g（N），记作f（N）=W（g（N）），即f（N）的阶（ ）g（N）的阶。
答案: 不低于
4、
f(n)= 100 当n为奇数 f(n)=5n^2+3n. 当n为偶数 f(n)的渐进性态f(n)= W( )
答案: 1
5、
下面程序的时间复杂度为（） x=1for i=1 to n dofor j=1 to i do for k=1 to j do
x++
答案: n^3
6、
对近似递增序列的线性表从小到大排序，使用哪种方法好？
答案: 插入排序
7、
给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。
答案: 100
8、
给定图G=(V,E), |V|=n, |E|=m, 遍历其邻接表的时间复杂度为θ( )
答案: n+m
9、
logn!=Q( )
答案: nlogn
10、
给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。
答案: 100
11、
下面程序的时间复杂度是（） i=1while(i<=n)
do i=i*5
答案: Q(logn)
12、
给定n个整数，n个数的取值范围为[1,k],计数排序的时间复杂度是O （n+k） 。
答案: n+k
13、
给定图G=(V,E), |V|=n, |E|=m, 其邻接矩阵的空间复杂度为( )
答案: θ(n^2)
14、
顺序查找适合的数据结构是（）
答案: 顺序存储;
链式存储
15、
f(n)=3n^3+7n^2+4nlogn =（）（n^3）
答案: Ο;
Ω;
θ
16、
下面那些算法的时间复杂度为O（n^2）?
答案: 插入排序;
冒泡排序;
折半插入排序
17、
两个n*n的矩阵相加的时间复杂度是（ ）
答案: θ(n^2);
O(n^2);
W(n^2)
18、
以空间换时间的方法有（）
答案: 预处理 ;
预构造;
动态规划
19、
时间复杂度是指算法最坏情况下的运行时间。
答案: 正确
20、
f(n)=O(g(n)) 且 g(n)=O(h(n))，则h(n)=O(f(n))
答案: 错误
21、
f(n)=O(g(n)) 则 f(n)^2=O(g(n)^2)
答案: 正确
22、
f(n)=3n^3+7n^2+4nlogn =O（n^2）
答案: 错误
23、
如果一个算法是多项式时间算法，该算法是有效的,是好算法。
答案: 正确
24、
n!=o(2^n)
答案: 错误
25、
答案: 正确
26、
折半查找的时间复杂度为Q(nlogn)
答案: 错误
27、
f(n)=θ(g(n)) 当且仅当 g(n)=θ(f(n))
答案: 正确
28、
f=O(g)当且仅当 g =Ω (f)
答案: 正确
29、
时间复杂度就是算法运行的时间的度量，衡量算法的效率。
答案: 正确
30、
求解问题的输入量,称为问题的规模 。
答案: 正确
31、
O(f(n))+O(g(n)) = O(min{f(n),g(n)})
答案: 错误
32、
任何多项式时间算法都是好算法，都是有效的。
答案: 错误
33、
任何情况下，复杂性渐近阶低的算法都比复杂性渐近阶高的算法有效。
答案: 错误
34、
对任意 r > 1 和 d > 0, n^d= o(r^n).
答案: 正确
35、
f(n)=O(g(n)) 则 log（f(n)) =O(log(g(n)))
答案: 正确
36、
常数阶算法的运行时间与规模n无关。
答案: 正确
37、
从n个数中查找最大值的时间复杂度为W (n)
答案: 错误
38、
使用合适的数据结构可以同时减少时间和空间
答案: 正确
第三章 枚举算法
3.1 知识梳理
1、
枚举算法的优化方法有（）
答案: 减少枚举变量;
减少枚举变量的值域;
优化算法;
优化数学模型
2、
冒泡排序的时间复杂度为O(nlogn)
答案: 错误
3、
0/1背包问题的时间复杂度为O（n2^n）
答案: 正确
4、
在某些问题实例中枚举是唯一的解决方法。
答案: 正确
5、
最好情况下，冒泡排序和选择排序的时间复杂度都是O（n^2）
答案: 错误
3.2 知识梳理
1、
子集生成方法有（）
答案: 增量构造法;
二进制法;
位向量法
2、
位向量法生成子集，不直接构造子集本身。
答案: 正确
3、
二进制法生成子集，子集与运算可以生成并集
答案: 错误
4、
增量构造法生成子集前需要定序
答案: 正确
第三章 测验
1、
便于实现集合操作的子集生成算法是（）
答案: 二进制法
2、
logn^2=( )(logn+5)
答案: θ
3、
0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？
答案: 40
4、
A公司处理器速度是B公司的100倍。对于复杂度为n^2的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时能处理的问题规模是()
答案: 10n
5、
直接插入排序的时间复杂度是（）。
答案: O(n^2)
6、
选择排序的时间复杂度是O（____）
答案: n^2
7、
分数拆分问题的枚举算法通过（）方法进行了优化。
答案: 减少枚举变量 ;
减少枚举变量的值域 ;
优化数学模型
8、
子集生成方法有（）
答案: 增量构造法 ;
二进制法;
位向量法
9、
枚举算法的优化方法有（）
答案: 减少枚举变量 ;
减少枚举变量的值域 ;
优化算法;
优化数学模型
10、
冒泡排序的时间复杂度为W(n^2)
答案: 错误
11、
0-1背包问题的枚举算法的时间复杂度为O(2^n）
答案: 错误
12、
增量构造法生成子集前需要对集合中元素从小到大排列。
答案: 正确
13、
二进制法生成子集，子集与运算可以生成并集
答案: 错误
14、
枚举法适用于问题的小规模实例。
答案: 正确
15、
减少枚举变量可以减少枚举算法的时间复杂度
答案: 正确
16、
位向量法生成子集，子集或运算可以生成差集
答案: 错误
17、
分块查找一般设分块的长度是n/2.
答案: 错误
18、
旅行商问题的枚举算法的时间复杂度为O（n!）
答案: 正确
19、
在某些问题实例中枚举是唯一的解决方法。
答案: 正确
20、
蛮力法适用于问题的小规模实例。
答案: 正确
第四章 贪心算法
4.1 知识梳理
1、
部分背包问题的时间复杂度是O( )
答案: nlogn
2、
贪心算法的思想是依据贪婪准则作出决策，逐步构造解值。
答案: 正确
3、
贪心算法的思想是寻求局部最优解，逐步达到全局最优解
答案: 正确
4、
贪心算法总能找到可行解，并且是最优解。
答案: 错误
5、
部分背包问题的证明方法是领先的方法
答案: 正确
4.2 知识梳理
1、
原问题的最优解包含其子问题的最优解是最优子结构的性质。
答案: 正确
2、
通过一系列局部最优的选择（贪心选择）达到全局最优是贪心选择的性质
答案: 正确
3、
问题的全过程可以分为若干个阶段，而且在任何一个阶段x后的行为都只仅仅依赖于x的状态，而与x之前如何达到这种状态的方式无关。这是无后效性的性质
答案: 正确
4、
负权的最短路问题可以使用Dijkstra算法计算。
答案: 错误
5、
贪心法处理问题的核心是贪婪准则的选取
答案: 正确
6、
贪心算法一般在开始贪心策略前会进行预处理，预处理后再进行最优化选择。
答案: 正确
4.3 知识梳理
1、
区间调度问题贪心算法的时间复杂度是（）
答案: O(nlogn)
2、
交换论证方法把任意一个解逐渐变为贪心算法的解，不会影响其最优性。
答案: 正确
3、
区间划分问题的证明方法是界的方法
答案: 正确
4、
区间选点问题的预处理方法是按照区间的终点递增排序
答案: 正确
5、
区间调度问题可以变换为最大独立集问题
答案: 正确
4.4 知识梳理
1、
Kruskal算法的时间复杂度是()，更适用于稀疏图。
答案: mlogn
2、
最小生成树问题可以使用的算法有（ ）
答案: Kruskal ;
Prim;
Solim
3、
MST是最小连通子图包含n 个顶点和n-1条边
答案: 正确
4、
Prim算法的贪婪准则是选取割集中的最小边
答案: 正确
5、
Kruskal算法的预处理是边权非递减排序。
答案: 正确
6、
设S是顶点子集，e是正好一个端点在S中的边中的最小边，那么最小生成树中肯定包含e.
答案: 正确
4.5 知识梳理
1、
最优前缀码数属于（ ）
答案: 变长码;
前缀码 ;
哈夫曼编码
2、
前缀码中任一字符的0-1编码都不是其他字符的前缀
答案: 正确
3、
哈夫曼编码给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。
答案: 正确
4、
哈夫曼编码的预处理是根据频率大小，构造优先队列。
答案: 正确
第四章 测验
1、
贪心算法基本要素有（ ）和最优子结构性质。
答案: 贪心选择性质
2、
下面不是证明贪心算法证明方法的有（）。
答案: 优化
3、
未来与过去无关指的是（ ）的性质
答案: 无后效性
4、
使目标函数最大（小）的解是问题的（）
答案: 最优解
5、
对于稠密图，使用（）算法计算MST更适合
答案: Prim
6、
把任意一个解逐渐变为贪心算法的解，不会影响其最优性。这种证明方法是_()
答案: 交换论证
7、
原问题的最优解包含其子问题的最优解是贪心算法的（）性质。
答案: 最优子结构性质
8、
区间调度问题贪心算法的时间复杂度是（）
答案: O(nlogn)
9、
最小生成树问题可以使用的算法有（ ）
答案: Kruskal ;
Prim ;
Solim
10、
区间问题包含()
答案: 区间调度;
区间划分;
区间选点;
区间覆盖
11、
贪心算法的基本要素是（）
答案: 贪心选择的性质 ;
无后效性性质;
最优子结构性质
12、
贪心算法的证明方法有（）
答案: 领先 ;
交换论证;
界;
反证;
归纳
13、
最小生成树问题可以使用的算法有（ ）
答案: Kruskal ;
Prim ;
Solim
14、
最优前缀码数属于（ ）
答案: 变长码 ;
前缀码 ;
哈夫曼编码
15、
贪心算法总能找到可行解，但未必是最优解。
答案: 正确
16、
贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。
答案: 正确
17、
问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
答案: 正确
18、
MST中若在树中任意增加一条边，将出现一个回路；若去掉一条边，将变成非连通图。
答案: 正确
19、
设C是一个环， f 是C中的最大边，那么最小生成树中肯定包含f.
答案: 错误
20、
Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。
答案: 正确
21、
哈夫曼编码的平均码长最小
答案: 正确
22、
负权的单源最短路问题可以使用Dijkstra算法求解。
答案: 错误
23、
如果e是图G中权重最小的边，它至少是G的一颗最小生成树的边。
答案: 正确
24、
如果图G中每条边的权重都是互不相同的，图G必定只有一颗最小生成树。
答案: 正确
25、
问题的可行解是满足约束条件的解
答案: 正确
26、
贪心算法的思想是寻求局部最优解，逐步达到全局最优解
答案: 正确
27、
贪心算法总能找到可行解，并且是最优解。
答案: 错误
28、
负权的最短路问题可以使用Dijkstra算法计算。
答案: 错误
29、
未来不影响过去指的是无后效性的性质。
答案: 错误
30、
贪心法处理问题的核心是贪婪准则的选取
答案: 正确
31、
区间划分问题的预处理方法是按照开始时间递减排序。
答案: 错误
32、
区间选点问题的预处理方法是按照区间的终点递增排序
答案: 正确
33、
设S是顶点子集，e是正好一个端点在S中的边中的最小边，那么最小生成树中肯定包含e.
答案: 正确
34、
Kruskal算法的预处理是边权非递减排序。
答案: 正确
35、
任意变长码的平均码长最小
答案: 错误
36、
哈夫曼编码的贪婪准则是从队列中选择频率最小的两个。
答案: 正确
37、
哈夫曼编码给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。
答案: 正确
第五章 递推算法
5.1 知识梳理
1、
递归函数的要素是递归方程和（）
答案: 边界条件
2、
递归一般用于解决的问题有（）
答案: 数据的定义是按递归定义的;
问题解法按递归实现;
数据的结构形式是按递归定义的
3、
递推是从小规模的问题推解出大规模间题的一种方法，是选代算法的最基本的表现形式。
答案: 正确
4、
递归与循环都是解决“重复操作”的机制
答案: 正确
5、
递归的效率高于递推
答案: 错误
6、
每个递归算法原则上总可以转换成与它等价的迭代算法；反之不然 。
答案: 错误
5.2 知识梳理
1、
使用递推关系求解问题的常用方法有（）
答案: 递归 ;
正推 ;
倒推;
迭代
2、
倒推法是从后向前推解问题的方法.
答案: 正确
3、
不知前提条件的情况下，经常使用倒推求解问题。
答案: 正确
4、
由结果倒过来推解前提条件是倒推方法的一种
答案: 正确
5、
由于存储的要求从后向前进行推算是倒推方法的一种
答案: 正确
5.3 知识梳理
1、
迭代法分为（ ）
答案: 直接迭代;
差消迭代;
换元迭代
2、
求解递推方程的方法有（）
答案: 迭代法 ;
递归树;
归纳法;
主定理
3、
主方法可以求解满足T(n)=aT(n/b) + f (n) 形式的递推方程， 则下列关于方程正确的是？A 对于系数a，必须满足a>=1B对于系数b，必须满足b>1C若对于常数ε>0，f(n)=O(nlogba-ε)，则T(n)=Θ(nlogba)D若f(n)=O(nlogba)，则T(n)=Θ(nlogbalogn)
答案: 对于系数a，必须满足a>=1;
对于系数b，必须满足b>1;
若对于常数ε>0，, 则;
若,则
4、
迭代法从原始递推方程出发，反复将对应方程左边的函数用右边等式带入，直至得到初值，然后将所得的结果化简。
答案: 正确
5、
迭代一般用于一阶递推方程，高阶方程需要使用差消法化简为一阶方程求解
答案: 正确
6、
快速排序平均情况下的时间复杂度是O（nlogn）
答案: 正确
第五章 测验
1、
从大规模问题逐步化为小规模问题的算法是（）
答案: 递归
2、
求解高阶递推方程一般使用（）迭代方法
答案: 差消迭代
3、
下面有关递归与迭代的说法错误的是（）
答案: 每个递归算法原则上总可以转换成与它等价的迭代算法
4、
主方法可以求解满足T(n)=aT(n/b) + f (n) 形式的递推方程， 则下列关于方程中的约束中不准确的是？
答案:
5、
T(n) = 2T(n/2) +n^2，T(1)=1，则 T(n) =（）
答案: Q(n^2)
6、
从小规模问题推解出大规模问题的算法是（）
答案: 递推
7、
递归函数的要素是（）
答案: 边界条件 ;
递归方程
8、
递归变为非递归的方法有（）
答案: 模拟栈 ;
递推 ;
尾递归
9、
递归一般用于解决问题有（）：
答案: 数据的定义是按递归定义的。 ;
问题解法按递归实现。;
数据的结构形式是按递归定义的
10、
求解递推方程的迭代法分为（ ）
答案: 直接迭代 ;
差消迭代;
换元迭代
11、
T(n) = T(n-1) + n ，T(1)=1，则 T(n) =（）
答案: W(n^2);
n(n+1)/2;
(n^2);
Q(n^2)
12、
求解快速排序时间复杂度使用的方法有（）
答案: 迭代法 ;
递归树;
归纳法 ;
主定理
13、
正推是从小规模的问题推解出大规模间题的一种方法
答案: 正确
14、
循环用于重复性的工作。循环体的特点是：“以不变应万变”。
答案: 正确
15、
递归算法是直接或间接地调用自身的算法。
答案: 正确
16、
尾递归中的递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分。
答案: 正确
17、
一般来说，递归的效率高于递推。
答案: 错误
18、
递推是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题。
答案: 错误
19、
有些问题采用倒推法，容易理解和解决。
答案: 正确
20、
递归是从简单问题出发，一步步的向前发展，最终求得问题，是正向的。
答案: 错误
21、
一般来说，递推的效率高于递归,因此将递归转化为递推
答案: 正确
22、
每个递归算法原则上总可以转换成与它等价的迭代算法，反之不然。
答案: 错误
23、
由结果倒过来推解前提条件是倒推方法的一种。
答案: 正确
24、
迭代法从原始递推方程出发，反复将对应方程左边的函数用右边等式带入，直至得到初值，然后将所得的结果化简。
答案: 正确
25、
快速排序和插入排序最好情况下的时间复杂度是O（nlogn）
答案: 错误
第六章 分治算法
6.1 知识梳理
1、
合并排序的时间复杂度是O（）
答案: nlogn
2、
分治法的适用条件是（ ）。
答案: 问题可以分解为规模较小的子问题;
小规模子问题可解;
子问题可合并为问题的解 ;
子问题相互独立
3、
分治法的设计思想是大事化小，各个击破，分而治之。
答案: 正确
4、
每次都将问题分解为原问题规模的一半进行求解，称为二分法
答案: 正确
5、
分治法一般在每一层递归上有分解、解决、合并三个步骤
答案: 正确
6、
减治法是把一个问题转化成一个子问题来解决，从子问题的解得到原问题的解。
答案: 正确
7、
分治法将原问题分解为若干个规模较小、相互独立、完全相同的子问题。
答案: 错误
6.2 知识梳理
1、
减治法常见的形式有（）
答案: 减一个常量 ;
减一个常量因子;
减可变规模
2、
二分法子问题独立而不相似的情况可以转化为相似子问题求解
答案: 正确
3、
二分法子问题不独立的情况可以计算，但计算量大，一般使用动态规划计算。
答案: 正确
4、
N个元素排序的时间复杂度不可能是线性时间。
答案: 错误
5、
任何基于元素比较的排序算法的时间复杂度>=élogn!ù= Q(nlogn)
答案: 正确
6.3 知识梳理
1、
二分搜索算法将分治的2个子问题减少为1个，时间复杂度由n降低为logn
答案: 正确
2、
大整数乘法将分治的四个子问题减少为2个，时间复杂度由n2降低为n
答案: 错误
3、
Strassen矩阵乘法将分治的8个子问题减少为7个，时间复杂度由n3降低为n^log7
答案: 正确
4、
减少子问题的个数，可以降低分治算法的时间复杂度。
答案: 正确
5、
存在O(n2.376 )时间的矩阵乘法分治算法
答案: 正确
6.4 知识梳理
1、
改进分治的均衡度，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（）值。
答案: b
2、
随机快速排序的时间是O（n^2）
答案: 错误
3、
给定n个元素，找其中位数的时间是O（n）
答案: 正确
4、
给定n个元素，使用分治算法找k小元素，如果保证分治的两个子数组中最小的数组是原数组的ε倍，时间复杂度可以由nlogn降低为n. 0<ε<1.
答案: 正确
6.5 知识梳理
1、
减少合并时间，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（）值。
答案: f(n)
2、
最接近点对问题的时间复杂度为（）
答案: nlogn
3、
最接近点对问题将合并的时间从n^2减少为n，从而将算法的时间复杂度由n^减少为nlogn。
答案: 正确
4、
计数逆序问题将合并计数逆序的时间由n^2减少为n，从而将算法的时间复杂度由n^2减少为nlogn。
答案: 正确
第六章 测验
1、
设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用( )法。
答案: 冒泡排序
2、
堆排序的时间复杂度是O（）。
答案: O（nlogn）
3、
使用分治法求解不需要满足的条件是（ ）。
答案: 子问题必须是一样的
4、
找n个元素的中位数的分治算法的时间复杂度为O(___).
答案: n
5、
合并排序的时间复杂度是（）
答案: nlogn
6、
军事上迂回包围、穿插分割、各个歼灭是（）思想。
答案: 分治
7、
堆排序的时间复杂度是（）
答案: nlogn
8、
大整数乘法分治算法的时间为O（）
答案: n^log3
9、
对线性表进行折半查找最方便的数据结构是（)
答案: 有序顺序表
10、
减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（）值。
答案: a
11、
分治法在每一层递归上有三个步骤（）
答案: 分解;
解决 ;
合并
12、
通过减少子问题个数，降低分治算法时间复杂度的有（）
答案: 大整数乘法;
Strassen矩阵乘法
13、
分治法所能解决的问题一般具有（ ）特征.
答案: 问题可以分解为规模较小的子问题;
小规模子问题可解 ;
子问题可合并为问题的解 ;
子问题相互独立
14、
减治法常见的形式有（)
答案: 减一个常量;
减一个常量因子;
减可变规模
15、
改进分治算法的方法有（）
答案: 减少子问题的个数 ;
改进分治的均衡度;
减少合并的时间
16、
分治法分解的子问题与原问题形式相同。
答案: 正确
17、
N个元素排序的时间复杂度不可能是线性时间。
答案: 错误
18、
分治法分解的子问题与原问题形式相同。
答案: 正确
19、
三分法的判定树是三叉树
答案: 正确
20、
减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)
答案: 错误
21、
最小堆中每个元素调整的次数不超过树高 Q(logn)。
答案: 正确
22、
分治算法的思想是将难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。
答案: 正确
23、
任何排序算法至少需要O(nlog n)次比较。
答案: 错误
24、
改进子问题合并的时间复杂度可以减少分治算法的时间。
答案: 正确
25、
分治与递归都是从大规模问题逐步化为小规模问题，因此分治算法经常使用递归实现。
答案: 正确
26、
分治法将原问题分解为若干个规模较小、相互独立、完全相同的子问题。
答案: 错误
27、
减治法是把一个问题转化成一个子问题来解决，从子问题的解得到原问题的解。
答案: 正确
28、
任何基于元素比较的排序算法的时间复杂度>=élogn!ù= Q(nlogn)
答案: 正确
29、
建立n个元素的最大堆的时间为O(n)
答案: 正确
30、
存在O(n2.376 )时间的矩阵乘法分治算法
答案: 正确
31、
随机快速排序的时间是O（n^2）
答案: 错误
32、
给定n个元素，找其中位数的时间是O（n）
答案: 正确
33、
给定n个元素，使用分治算法找k小元素，如果保证分治的两个子数组中最小的数组是原数组的ε倍，时间复杂度可以由nlogn降低为n
答案: 正确
34、
两个有序数组合并的时间不会超过两个数组的长度和。
答案: 正确
第七章 动态规划
7.1 知识梳理
1、
下面不是动态规划算法特点的是（）
答案: 从大到小计算
2、
备忘录与递归算法的相同点是（）
答案: 递推关系;
最优子结构
3、
动态规划算法本质上是空间换时间的算法，每一个子问题只解一次,存储子问题结果，避免重复计算。
答案: 正确
4、
备忘录方法为每一子问题建立记录项，初始化时，存入特殊值。求解时遇到特殊值时计算并保存在相应记录项中，下次遇到时直接查表即可。
答案: 正确
5、
最优子结构是问题能用动态规划算法求解的前提。
答案: 正确
6、
通常不同的子问题个数随问题规模呈多项式增长。动态规划算法对于每个子问题求解一次，并保存子问题结果，因此只需要多项式时间。
答案: 正确
7.2 知识梳理
1、
确定第 i 阶段的收益函数和从第1阶段出发到第i 阶段末所获得收益的最优值，建立动态规划基本方程。这种方法是（）
答案: 正推
2、
动态规划定义递推关系的方法有（）
答案: 正推;
反推
3、
动态规划是“带决策的多阶段、多方位的递推算法”
答案: 正确
4、
给定n层数字三角形，动态规划计算的时间为O（n^3）
答案: 错误
5、
状态转移方程是状态间的递推关系，也是子问题间的递推关系。状态变量取值不同对应不同问题状态，也对应不同子问题。
答案: 正确
7.3 知识梳理
1、
OPT[i][w]=max{OPT[i-1][w],OPT[i][w-w[i]]+v[i]}，这是()问题的递推关系。
答案: 完全0-1背包
2、
OPT[i][w]=max{OPT[i-1][w],OPT[i-1][w-k*w[i]] +k*v[i]，0<=k<=n[i]}。这是()问题的递推关系。
答案: 多重0/1背包
3、
0-1背包问题的动态规划算法的时间复杂度是Q(n W)，是多项式时间算法.
答案: 错误
4、
恰好装满的0-1背包问题，初始化时除了M[0]为0，其它M[1..C]均设为-∞，可以保证最终得到的M[C]是一种恰好装满背包的最优解。
答案: 正确
7.4 知识梳理
1、
动态规划算法的计算矩阵连乘问题的时间为O（）
答案: n^3
2、
区间动态规划的计算次序是（）
答案: 先小区间后大区间;
先小规模后大规模
3、
区间动归使用链长，先计算小区间，再递增计算大区间。
答案: 正确
4、
矩阵连乘的计算次序可以用完全加括号的方式来确定。
答案: 正确
5、
矩阵连乘问题的不同子问题个数为 O（n^2）
答案: 正确
7.5 知识梳理
1、
拓扑排序的时间复杂度是O( )
答案: m+n
2、
动态规划计算最长不降子序列的时间是O（）
答案: n^2
3、
拓扑排序的结果是一个顶点序列，顶点间存在先序关系。
答案: 正确
4、
嵌套矩形问题本质上求DAG上的最长路径，但没有给出起点和终点。
答案: 正确
5、
反推求解嵌套矩形问题，很难打印字典序最小的方案。
答案: 错误
6、
硬币问题本质上是DAG上的最长路径和最短路，且给出起点和终点。
答案: 正确
7、
DAG图最长路的正推关系是 L(j) = 1 + max {L(i) : (i, j) 为边}
答案: 正确
7.7 知识梳理
1、
Floyd算法的复杂度为O（）
答案: n^3
2、
如果图中存在负环，那么从s到t没有最短路。
答案: 正确
3、
Bellman算法的计算时间为Q(mn), 空间为 Q(n^2)，可以求最短路，也可求最长路。
答案: 正确
4、
SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
答案: 正确
5、
Floyd算法可以构造无向或有向加权图（包含长度为负的回路）的完全最短路径
答案: 错误
6、
SPFA算法计算时，如果一个顶点入队列的次数超过n，则存在负权回路。
答案: 正确
7、
动态规划计算树上的最大独立集时，从叶子开始，先计算子树，逐步计算到根节点。
答案: 正确
7.8 知识梳理
1、
LCS问题的不同子问题个数为 O（）
答案: mn
2、
序列 . 设LCS(X, Y)=。若则，且是和的最长公共子序列。
答案: 正确
3、
给定串 ， 一个比对M是有序对 的集合，每一项至多参与一个配对，并且允许交叉。
答案: 错误
4、
动态规划方程中子问题个数为n^t，依赖的子问题个数为n^e， 则算法的时间复杂度为n^(t+e)
答案: 正确
5、
序列的编辑距离是间隔的惩罚值和错配的惩罚值之和。
答案: 正确
6、
动态规划方程M[i,j]=min(M[k]+wk), 1≤i≤k≤j≤n, 则算法的时间复杂度为n^2
答案: 错误
,
第七章 测验
1、
含负权的最短路问题一般使用（）求解。
答案: 动态规划
2、
动态规划算法的基本要素有（ ）和最优子结构性质。
答案: 重叠子问题性质
3、
下面不是动态规划的基本方法有（）。
答案: 舍入
4、
下面不是动态规划算法的基本要素的是（ ）。
答案: 独立子问题性质
5、
动态规划方法使用（ ）计算方式。
答案: 自底向上
6、
确定第 i 阶段的收益函数和从第1阶段出发到第i 阶段末所获得收益的最优值，建立动态规划基本方程。这种方法是（）
答案: 正推
7、
OPT[i][w]=max{OPT[i-1][w],OPT[i][w-w[i]]+v[i]}，这是()问题的递推关系。
答案: 完全0-1背包
8、
Floyd算法的复杂度为O（）
答案: n^3
9、
最短路算法中适用于稀疏图的是（）
答案: SPFA算法 ;
Bellman算法 ;
Dijkstra算法
10、
动态规划算法的特点（）
答案: 自底向上计算 ;
从小到大计算
11、
分治算法与动态规划算法的相同点是（）
答案: 递推关系;
最优子结构
12、
备忘录算法的特点（）
答案: 自顶向下计算 ;
从大到小计算
13、
备忘录与递归算法的相同点是（）
答案: 递推关系 ;
最优子结构
14、
OPT(i，w): 从1-i个物品中选择，放入容量为w的背包时的最大价值。这是（）问题动态规划算法的递推函数。
答案: 0/1背包 ;
恰好装满的0/1背包
15、
区间动态规划的计算次序是（）
答案: 先小区间后大区间 ;
先小规模后大规模
16、
下面哪些问题可以转化为DAG图进行计算？
答案: 嵌套矩形 ;
最长不降子序列;
硬币问题 ;
数字三角形
17、
最短路算法中适用于稠密图的是（）
答案: Floyd算法;
Dijkstra算法
18、
下面哪些问题的动态规划算法的时间复杂度为Q(mn)？
答案: LCS ;
序列比对;
SPFA算法
19、
动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。
答案: 正确
20、
0/1背包问题的动态规划算法是多项式时间算法。
答案: 错误
21、
对于稀疏图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA算
答案: 错误
22、
Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。
答案: 正确
23、
DAG上最短路，固定起点和终点没有意义。
答案: 错误
24、
DAG图最长路的递推函数d(i)表示从某个顶点i出发的最长路长度 。
答案: 正确
25、
最大权独立集不包含u，可能包含其儿子结点，也可能不包含儿子结点
答案: 正确
26、
最优子结构是问题能用动态规划算法求解的前提。
答案: 正确
27、
通常不同的子问题个数随问题规模呈多项式增长。动态规划算法对于每个子问题求解一次，并保存子问题结果，因此只需要多项式时间。
答案: 正确
28、
贪心和递推算法是线性解决问题，动态规划则是全面分阶段地解决问题。
答案: 正确
29、
状态变量取值不同对应不同问题状态，也对应不同子问题。
答案: 正确
30、
状态转移方程表示状态间的递推关系，也是子问题间的递推关系。
答案: 正确
31、
0-1背包问题的动态规划算法可以使用一维数组实现。
答案: 正确
32、
矩阵乘法满足结合律，所以计算矩阵连乘，不同的计算次序计算量相同。
答案: 错误
33、
矩阵连乘问题的不同子问题个数为 O（n^2）
答案: 正确
34、
硬币问题本质上是DAG上的最长路径和最短路，且给出起点和终点。
答案: 正确
35、
DAG图最长路的反推关系是 L(i) = 1 + max {L(j) : (i, j) 为边}
答案: 正确
36、
Bellman算法在求解过程中，每次循环都要检查修改所有顶点的路径，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来
答案: 正确
37、
SPFA算法计算时，如果一个顶点入队列的次数超过n，则存在负权回路。
答案: 正确
38、
动态规划计算树上的最大独立集时，从叶子开始，先计算子树，逐步计算到根节点。
答案: 正确
39、
动态规划方程中子问题个数为n^t，依赖的子问题个数为n^e， 则算法的时间复杂度为n^(t+e)
答案: 正确
40、
动态规划方程M[i]=min(M[j]+wij), 1≤i≤j≤n, 则算法的时间复杂度为n^2
答案: 正确
第八章 回溯算法
8.1 知识梳理
1、
装载问题的回溯算法所需的计算时间为（ ）
答案: O（2^n）
2、
装载问题的剪枝函数有（）
答案: 可行性约束函数 
;
上界函数 Cw + r £ bestw
3、
下列哪个结点属于回溯法的结点类型？（ ）
答案: 扩展结点;
活结点;
死结点
4、
具有剪枝函数的深度优先生成法称为回溯法
答案: 正确
5、
装载问题的解空间树是子集树。
答案: 正确
8.2 知识梳理
1、
旅行商问题的回溯算法所需的计算时间为（ ）
答案: O（n！）
2、
旅行商问题使用（）进行剪枝
答案: 剪枝函数;
约束函数 ;
下界函数
3、
旅行商问题的解空间树为排列树
答案: 正确
4、
旅行商问题的限界函数是当前路>已记录最小路程 bestc
答案: 正确
5、
旅行商问题的约束条件是两结点间有边相连。
答案: 正确
知识梳理
1、
下面哪种函数是回溯法中为避免无效搜索采取的策略（ ）
答案: 剪枝函数
2、
回溯法的回溯方式有（）
答案: 递归回溯 ;
迭代回溯
3、
回溯法的效率依赖于下列哪些因素（ ）
答案: 满足显约束的值的个数;
计算约束函数的时间 ;
计算限界函数的时间
4、
回溯算法用约束函数在扩展结点处剪去不满足约束的子树
答案: 正确
5、
回溯算法用限界函数剪去得不到最优解的子树 。
答案: 正确
第八章 测验
1、
下列算法中，通常以深度优先方式系统搜索问题解的是（ ）。
答案: 回溯法
2、
下面哪种函数是回溯法中为避免无效搜索采取的策略（ ）
答案: 剪枝函数
3、
剪枝函数包括（ ）和约束函数。
答案: 限界函数
4、
旅行商问题的回溯算法所需的计算时间为O（ ）
答案: n！
5、
装载问题的回溯算法所需的计算时间为O（ ）
答案: 2^n
6、
回溯法的效率依赖于下列哪些因素（ ）
答案: 满足显约束的值的个数 ;
计算约束函数的时间;
计算限界函数的时间
7、
下列哪个结点属于回溯法的结点类型？（ ）
答案: 扩展结点 ;
活结点;
死结点
8、
问题的状态生成法有（）
答案: 深度优先生成法 ;
宽度优先生成法
9、
回溯法解题步骤：
答案: 针对所给问题，定义问题的解空间;
确定易于搜索的解空间结构;
以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索。
10、
回溯法的两种解空间树为
答案: 子集树;
排列树
11、
旅行商问题使用（）进行剪枝。
答案: 剪枝函数 ;
约束函数;
下界函数
12、
装载问题的剪枝函数有（）
答案: 可行性约束函数： 
;
上界函数： Cw + r £ bestw
13、
回溯法是按广度优先策略搜索解空间树。
答案: 错误
14、
死结点是正在产生儿子的结点
答案: 错误
15、
回溯法中，如果解空间树是子集树，当所给的问题规模为n时，通常有2^n个叶结点，遍历子集树需O(2^n)计算时间
。
答案: 正确
16、
回溯法不适用于解一些组合数相当大的问题。
答案: 错误
17、
好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。
答案: 正确
18、
回溯法搜索解空间时，在搜索试探时选取x[i]的值顺序是任意的，顺序对于计算量没有差别。
答案: 错误
19、
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但是，当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术，称为回溯法。
答案: 正确
20、
回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。
答案: 正确
21、
装载问题，当所给的问题规模为n时，通常有2^n个叶结点。
答案: 正确
22、
扩展结点是所有儿子已经产生的结点。
答案: 错误
23、
旅行商问题，当所给的问题规模为n时，通常有2^n个叶结点。
答案: 错误
24、
旅行商问题的限界函数是当前路>已记录最小路程 bestc
答案: 正确
25、
回溯算法用限界函数剪去得不到最优解的子树 。
答案: 正确
第九章 分支限界
9.1 知识梳理
1、
0-1背包问题中剪枝函数是（）
答案: 约束函数 
;
限界函数 当前价值Cv＋当前尚未考虑的剩余物品价值总和 r>当前最优价值bestv
2、
分支限界法以广度优先或以最小耗费/最大效益优先的方式产生状态空间树的结点，并使用剪枝函数进行修剪解空间树。
答案: 正确
3、
0-1背包问题的的解空间树是子集树
答案: 正确
4、
分支限界活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
答案: 正确
9.2 知识梳理
1、
旅行商问题中，优先队列分支限界法选取扩展结点的原则是（ ）。
答案: 结点的优先级
2、
优先队列分支限界法解旅行商问题时，活结点表的组织形式是（ ）。
答案: 最小堆
3、
旅行商问题搜索方式包含（ ）。
答案: 广度优先 ;
最小路程优先;
深度优先
4、
旅行商问题中，分支限界法的目标是找出满足约束条件的所有解。
答案: 错误
9.3 知识梳理
1、
从活结点表中，选择下一扩展结点的两种方式是队列式和优先队列式。
答案: 正确
2、
队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。
答案: 正确
3、
优先队列式分支限界为了加速搜索的进程，按照优先队列中规定的优先级，选取优先级最高的结点，成为当前扩展结点 。
答案: 正确
4、
分支限界法在对问题的解空间树进行搜索的方法中，一个结点有多次机会成为活结点
答案: 错误
第九章 测验
1、
下列算法中不能解决0/1背包问题的是（）
答案: 贪心法
2、
分支限界法解旅行商问题时的解空间树是（ ）。
答案: 排列树
3、
优先队列式分支限界法选取扩展结点的原则是（ ）
答案: 结点的优先级
4、
在对问题的解空间树进行搜索的方法中，一个结点最多有一次机会成为活结点的是（ ）。
答案: 分支限界法
5、
FIFO是（ ）的搜索方式。
答案: 分支限界
6、
采用最大效益优先搜索方式的算法是（ ）。
答案: 分支界限法
7、
优先队列分支限界法解旅行商问题时，活结点表的组织形式是（ ）
答案: 最小堆
8、
用分支限界法设计算法的步骤是：
答案: 针对所给问题，定义问题的解空间（对解进行编码）；;
确定易于搜索的解空间结构（按树或图组织解）;
以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
9、
分支限界法与回溯法的不同点是什么？
答案: 求解目标不同;
搜索方式不同;
对扩展结点的扩展方式不同;
存储空间的要求不同
10、
下面说法正确的是（）
答案: 用约束函数在扩展结点处剪去不满足约束的子树;
用限界函数剪去得不到最优解的子树。;
回溯和分支限界都是动态生成解空间树。
11、
常见的分支限界法为（）
答案: 队列式分支限界;
优先队列式分支限界;
FIFO分支限界
12、
分支界限法搜索方式包含（ ）。
答案: 广度优先 ;
最小耗费优先;
最大效益优先
13、
回溯算法和分支限界法的问题的解空间树可能是( ).
答案: 有序树 ;
子集树;
排列树
14、
分支限界法不能解决0/1背包问题
答案: 错误
15、
分支限界法在对问题的解空间树进行搜索的方法中，一个结点有多次机会成为活结点。
答案: 错误
16、
分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
答案: 正确
17、
队列式分支限界法以最小耗费优先的方式搜索解空间树。
答案: 错误
18、
优先队列式分支限界法按照优先队列中规定的优先级，选取优先级最高的结点，成为当前扩展结点。
答案: 正确
19、
优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。
答案: 错误
20、
分支限界法与回溯法，都是在问题的解空间树上搜索问题解。
答案: 正确
21、
使用限界函数作优先级, 第一个扩展的叶子就是最优解
答案: 正确
22、
分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者搜索方式不同，但求解目标相同。
答案: 错误
23、
回溯法和分支限界法的主要区别在于，回溯法求取问题的一个解或所有解。
答案: 正确
24、
分支限界按广度优先的原则进行搜索，每一活结点只有一次机会成为扩展结点
答案: 正确
25、
分支限界活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
答案: 正确
26、
解决旅行商问题，采用的是优先队列式分支限界法。
答案: 正确
27、
旅行商问题中，分支限界法的目标是找出满足约束条件的所有解。
答案: 错误
28、
优先队列式分支限界为了加速搜索的进程，按照优先队列中规定的优先级，选取优先级最高的结点，成为当前扩展结点
答案: 正确
29、
分支界限法采用深度优先策略搜索。
答案: 错误
30、
分支限界法在对问题的解空间树进行搜索的方法中，一个结点有多次机会成为活结点
答案: 错误
第十章 网络流算法
10.1 知识梳理
1、
FF算法的时间复杂度是（)
答案: mnC
2、
给定网络 N=(V, E)的一个流 f，f需满足的两个条件是
答案: 容量条件 ;
守恒条件
3、
给定网络 N=(V, E)的一个流 f ，源点 s 的流出量等于汇点 t 的流入量
答案: 正确
4、
设f 为任意流, (A, B) 是任意 s-t 割. 则流出割的净流量等于离开s的流量
答案: 正确
5、
最大流和最小割的值相等
答案: 正确
6、
FF算法得到最大流当且仅当FF找不到增广路径
答案: 正确
7、
如果所有容量为整数, 最大流的每一个流值 f(e) 是整数.
答案: 正确
10.2 知识梳理
1、
容量缩放算法的时间复杂度为（）
答案: m^2logC
2、
EK算法的时间复杂度为（）
答案: nm^2
3、
ISAP算法的时间复杂度为（）
答案: mn^2
4、
改进FF网络流算法的途径有
答案: 有效的发现增广路径.;
迭代次数减少
5、
层次网络中删除了比汇点层次高和相同层次的顶点和关联边、同层边和从高层指向低层的边，剩余边的容量与剩余图相同。
答案: 正确
6、
最短增广路算法每次都找一条包含弧数最少的增广路
答案: 正确
7、
层次网络为剩余图基础上的最短路径图。从源点出发，到达终点，肯定是最短路径。
答案: 正确
10.3 知识梳理
1、
最高标号预流推进算法的时间复杂度为O()
答案: n^2m^1/2
2、
预流推进算法不关注于每一条弧的操作和处理,而是一次一定处理一条增广路.
答案: 错误
3、
预流推进算法的引导机制是高度标号和重标号机制
答案: 正确
4、
预流推进算法中，从源点到汇点，完全由允许弧组成的路径，是最短增广路。
答案: 正确
5、
使用了重标号操作后,至多存在一条边(u,v)满足h(u)=h(v)+1.
答案: 错误
6、
最高标号预流推进算法从具有最大标号的盈余结点开始预流推进。使小标号的盈余顶点累计尽可能多的来自大标号结点的流量，然后对累积的盈余进行推进，减少非饱和推进的次数。
答案: 正确
10.4 知识梳理
1、
有下界的流通问题，转换为带需求的流通问题有可行的流通，下面错误的是（）
答案: 每条边的流量不变
2、
多源点和多汇点的网络流问题可以通过增加一个“超源点”和“超汇点”转化为单源点和单汇点的网络流问题
答案: 正确
3、
无向图的每条边变为方向相反的两条边，容量是原边的容量，这样无向图的最大流问题变换为有向图的最大流问题。
答案: 正确
4、
将有顶点容量限制的顶点u用一条边(u,v)代替，顶点u的入边仍为u的入边，顶点u的出边变为顶点v的出边。 (u,v)的容量等于原先顶点u的容量。变换后 网络的最大流等于原网络的最大流
答案: 正确
5、
带需求的流通的必要条件是供给和 = 需求和.
答案: 正确
10.5 知识梳理
1、
始终保持网络中的可行流是最小费用流，然后不断调整，使流量逐步增大， 最终成为最小费用的最大流。这种算法是（）
答案: 最小费用路算法
2、
始终保持可行流是最大流，通过不断调整使费用逐步减小，最终成为最大流量的最小费用流。这种算法是（）
答案: 消圈算法
3、
最小费用最大流算法求得解需满足（）条件。
答案: 对于任意边 e Î E: 0£f(e)£c(e);
对任意顶点v，顶点的净流量=0;
每条边的流量乘以单位流量费用之和最小
4、
给定网络G，最小费用最大流问题求G的一个最大流flow，使流的总费用最小。
答案: 正确
5、
剩余网络中从源s到汇t的最小费用路是剩余网络中从s到t的以费用为权的最短路
答案: 正确
6、
剩余网络中，前向边和后向边(v,w)的费用都为cost(w,v)。
答案: 错误
10.6 知识梳理
1、
求解二分图最大匹配的算法有(）
答案: 网络流算;
匈牙利算法;
Hopcroft-Karp算法
2、
无向图 G = (V, E) 的顶点着红或蓝色，使每一条边的一端为红色，一端为蓝色。则该图是二分图。
答案: 正确
3、
图 G 是二分图 iff 无奇数长的环
答案: 正确
4、
匈牙利算法求解二分匹配，既能判定一个二分图中完美匹配是否存在，又能在存在时求出一个完美匹配。
答案: 正确
5、
给定连通图G, BFS遍历得到层次图， 同一层中存在连接两个结点的边，则G是二分图.
答案: 错误
6、
设G = (L È R, E) 是一个二分图且 |L| = |R|，则G 有完美匹配 iff 对所有的子集S Í L有|N(S)| ³ |S|.
答案: 正确
10.7 知识梳理
1、
给定二分图G = <V, E>中无孤立点，其最大流算法求得最大流f, 则 G的（）=f
答案: 最大匹配数;
最小顶点覆盖数
2、
设G = <V, E>中无孤立点, V*(V*ÌV)为G的顶点覆盖, 当且仅当V-V*为G的独立集。
答案: 正确
3、
设G = <V, E>中无孤立点。M为G的最大匹配, 对于G中每个未覆盖顶点v, 选取与v关联的边组成集合N,则MÈN是G的最小边覆盖。
答案: 正确
4、
一个二分图中的最大匹配数等于这个图中的最小边覆盖数
答案: 错误
5、
给定G = <V, E>, G的匹配中任何两条边都没有公共顶点。
答案: 正确
6、
给定二分图G = <V, E>中无孤立点，其最大流算法求得最大流f, 则 G的最小边覆盖数=n-f
答案: 正确
10.8 知识梳理
1、
Kuhn-Munkres算法的总时间复杂度为（）
答案: n^3
2、
给定赋权二分图G，求权值总和最大的完备匹配称为最佳匹配。
答案: 正确
3、
相等子图是G的生成子图，包含G的所有点，但只包含满足l(x)+l(y)=w(x,y)的所有边(x,y)。
答案: 正确
4、
给定赋权二分图G,如果G的相等子图G’有完美匹配M * ，则M *是G的最大权匹配。
答案: 正确
5、
KM算法逐次修改可行顶标l(v)，使对应的相等子图的边增多，最大匹配逐次增大，最后出现完备匹配。
答案: 正确
6、
KM算法将赋权二分图G所有的边权值取其相反数，求最大权完备匹配，匹配的值再取反即为最小权完备匹配。
答案: 正确
第十章 测验
1、
Dinic算法的时间复杂度为（）
答案: mn^2
2、
如果每条边的最大容量为1，则时间复杂度是O（nm）的网络流算法有（）
答案: FF算法
3、
FF算法的时间复杂度是（）
答案: mnC
4、
最高标号预流推进算法的时间复杂度为O()
答案: n^2m^1/2
5、
有下界的流通问题，转换为带需求的流通问题有可行的流通，下面错误的是（）
答案: 每条边的流量不变
6、
设G是n阶无孤立点的图，V*是G的最小顶点覆盖，则V-V*是G的（）。
答案: 最大独立集
7、
给定二分图G = <V, E>中无孤立点，|V|=n，其最大流算法求得最大流f, 则 G的（）=n-f.
答案: 最大独立数 ;
最小边覆盖
8、
改进FF网络流算法，可以通过选择（ ）增广路，降低时间复杂度。
答案: 最大容量 ;
最短路径;
最大瓶颈容量;
边数最少
9、
给定网络 N=(V, E)的一个流 f，f需满足的两个条件是
答案: 容量条件 ;
守恒条件
10、
改进FF网络流算法，可以选择好的增广路径，使
答案: 有效的发现增广路径. ;
迭代次数减少;
存储空间减少;
算法复杂度降低
11、
预流推进算法的关键操作有（）
答案: 推进 ;
重标号;
初始化
12、
带需求的流通满足（），才是可行流。
答案: 对于任意边 e Î E: 0£f(e)£c(e) ;
对任意顶点v，顶点的净流量=d(v);
供给和 = 需求和
13、
最小费用最大流算法求得解需满足（）条件。
答案: 对于任意边 e Î E: 0£f(e)£c(e);
对任意顶点v，顶点的净流量=0;
每条边的流量乘以单位流量费用之和最小
14、
求解二分图最大匹配的算法有()
答案: 网络流算法 ;
匈牙利算法;
Hopcroft-Karp算法
15、
给定二分图G = <V, E>中无孤立点，其最大流算法求得最大流f, 则 G的（）=f
答案: 最大匹配数;
最小顶点覆盖
16、
网络流满足容量约束，但一般不满足流量守恒约束。
答案: 错误
17、
设 f 任意流, (A, B) 是任意 s-t 割. 则流值至多等于割的容量.
答案: 正确
18、
存在割 (A, B) 使流值 v(f)
= 割的容量cap(A, B).，则割 (A, B)是最小割。
答案: 正确
19、
对于简单网络，最短增广路算法时间复杂度
(nm)
答案: 错误
20、
有下界的流通问题不一定有可行流。
答案: 正确
21、
带需求的流通必须满足供给和 = 需求和.
答案: 正确
22、
重标号操作使它的标号上升到比周围最低的结点高度+1,使他的赢余能流出去
答案: 正确
23、
设G是n阶无孤立点的图，则V*是G的顶点覆盖，当且仅当V-V*是G的独立集。
答案: 正确
24、
设G = <V, E>中无孤立点。W为G的最小边覆盖, 若G中存在相邻边就移去其中一条。设移去的边集为N，则W-N是G的最大匹配。
答案: 正确
25、
给定二分图G = <V, E>中无孤立点，其最大流算法求得最大流f, 则 G的最大匹配数=f
答案: 正确
26、
匈牙利算法中起点和终点都是未匹配点的交错路径称为可增广路径，可增广路径有奇数条边。
答案: 正确
27、
设G = <V1, V2, E>为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配，也是最大匹配。
答案: 正确
28、
给定网络 N=(V, E)，设 f 为任意流, (A, B) 是任意 s-t 割. 则流值至少是割的容量
答案: 错误
29、
如果所有容量为整数, 最大流的每一个流值 f(e) 是整数
答案: 正确
30、
FF算法得到最大流当且仅当FF找不到增广路径
答案: 正确
31、
最短增广路算法在最坏情况下找增广路的次数不超过nm/2次。不同在于找增光路的时间. EK算法使用BFS找增广路的时间为 O(m)，Dinic算法使用BFS+ DFS 找增广路的时间为O(n)。
答案: 正确
32、
层次网络为剩余图基础上的最短路径图。从源点出发，到达终点，肯定是最短路径。
答案: 正确
33、
使用了重标号操作后,至多存在一条边(u,v)满足h(u)=h(v)+1.
答案: 错误
34、
最高标号预流推进算法从具有最大标号的盈余结点开始预流推进。使小标号的盈余顶点累计尽可能多的来自大标号结点的流量，然后对累积的盈余进行推进，减少非饱和推进的次数。
答案: 正确
35、
将有顶点容量限制的顶点u用一条边(u,v)代替，顶点u的入边仍为u的入边，顶点u的出边变为顶点v的出边。 (u,v)的容量等于原先顶点u的容量。变换后网络的最大流等于原网络的最大流
答案: 正确
36、
有下界的流通问题一定有可行流。
答案: 错误
37、
剩余网络中从源s到汇t的最小费用路是剩余网络中从s到t的以费用为权的最短路
答案: 正确
38、
剩余网络中后向边(v,w)的费用为cost(v,w).
答案: 错误
39、
最小费用最大流算法寻找从源点s到汇点t的最小费用路，然后沿最小费用路增流，直至找到最小费用流。
答案: 正确
40、
给定连通图G, BFS遍历得到层次图， 同一层中存在连接两个结点的边，则G是二分图.
答案: 错误
41、
设G = (L È R, E) 是一个二分图且 |L| = |R|，则G 有完美匹配 iff 对所有的子集S Í L有|N(S)| ³ |S|.
答案: 正确
42、
匈牙利算法根本上是最大流算法，但不需要建网络模型。
答案: 正确
43、
给定G = <V, E>, G的匹配中任何两条边都没有公共顶点。
答案: 正确
44、
设G = <V, E>中无孤立点，M是G的最大匹配，N为G的最小边覆盖，则M∩N=0
答案: 错误
第十一章 随机算法
11.1 知识梳理
1、
下面属于随机算法的是（）
答案: 数值随机算法;
舍伍德算法 ;
蒙特卡罗算法;
拉斯维加斯算法
2、
确定性算法的每一计算步骤都确定,求解同一实例用同一算法求解两次，所用时间和所得结果可能不同。
答案: 错误
3、
随机算法求解同一实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。
答案: 正确
4、
计算时间越多或运行次数越多正确性越高，这是随机算法的特点。
答案: 正确
5、
现实计算机上无法产生真正的随机数，因此在随机算法中使用的随机数都是一定程度上随机的，即伪随机数.
答案: 正确
6、
随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法.
答案: 正确
7、
数值随机算法的解一般是近似解。
答案: 正确
11.2 知识梳理
1、
调用一个偏真的p（>1/2）正确的蒙特卡罗算法，只要返回一次true, 就可得到正确解。重复调用6次，正确率提高到（）%.
答案: 99
2、
下列随机算法中运行时,有时候成功有时候失败,有时候正确有时候错误的有（ ）
答案: 拉斯维加斯算法;
蒙特卡罗算法
3、
舍伍德算法总有解, 且解总是正确的.但平均性能未改变.
答案: 正确
4、
蒙特卡罗算法总能求得问题的一个解,但可能给出错误解。
答案: 正确
5、
拉斯维加斯算法肯定得到正确解或找不到解, 一旦找到一个解,一定是正确解。
答案: 正确
6、
使用拉斯维加斯算法增加对问题反复求解次数, 可使求解无效的概率任意小。
答案: 正确
第十一章 测验
1、
在下列算法中有时找不到问题解的是（ ）。
答案: 拉斯维加斯算法
2、
肯定获得可行解，但不一定是正确解的算法是（）。
答案: 蒙特卡罗算法
3、
在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用（ ）对输入进行预处理。
答案: 舍伍德算法
4、
调用一个偏真的p（>1/2）正确的蒙特卡罗算法，只要返回一次true, 就可得到正确解。重复调用6次，正确率提高到（）%.
答案: 99
5、
（ ）肯定获得最优解。
答案: 分支限界 ;
动态规划算法
6、
下面说法正确的是（）
答案: 现实计算机上无法产生真正的随机数;
求解同一实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。;
蒙特卡罗算法总是能提供问题的一个解,但可能给出错误解;
舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。
7、
下面说法正确的是（）
答案: 随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法;
当最坏和平均情况差别较大时, 舍伍德算法可以消除好坏实例的差别，达到平均实例的性能.;
线性同余法是产生伪随机数的最常用的方法;
增加蒙特卡罗算法的求解次数, 可使求解错误的概率任意小
8、
下面属于随机算法的是（）
答案: 数值随机算法;
舍伍德算法 ;
蒙特卡罗算法 ;
拉斯维加斯算法
9、
下列随机算法中运行时,有时候成功有时候失败,有时候正确有时候错误的有（ ）
答案: 拉斯维加斯算法 ;
蒙特卡罗算法
10、
对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!º -1(mod n)。
答案: 正确
11、
Sherwood算法随机选择一个数组元素作为划分标准求解k小元素问题,保证线性时间的平均性能。
答案: 正确
12、
借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。
答案: 正确
13、
如果p是一个素数，且0<x<p，则方程x^2 º1 (mod p)的解为x=1，p-1。反之成立。
答案: 错误
14、
确定性算法的每一计算步骤都确定,求解同一实例用同一算法求解两次，所得结果完全相同。
答案: 正确
15、
增加拉斯维加斯算法的反复求解次数, 可使求解无效的概率任意小。
答案: 正确
16、
蒙特卡罗算法的结果肯定是一个正确解。
答案: 错误
17、
随机算法共同点是计算时间越多或运行次数越多,正确性越高.
答案: 正确
18、
舍伍德算法总是有解, 且解总是正确的，但最坏性能未改变。
答案: 错误
19、
拉斯维加斯算法肯定得到一个正确解。
答案: 错误
20、
随机抽取数组元素k次,从最接近搜索元素x 的位置顺序搜索, 顺序搜索的平均比较次数为O(n/(k+1)).
答案: 正确
21、
设p是一个实数，且1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。
答案: 正确
22、
确定性算法的每一计算步骤都确定,求解同一实例用同一算法求解两次，所用时间和所得结果可能不同。
答案: 错误
23、
随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法.
答案: 正确
24、
舍伍德算法设法消除最坏情况和特定实例的关联性，达到平均实例的性能.
答案: 正确
第十二章 P与NP
知识梳理
1、
问题Y ÎNP，对于任意的NP类问题X， X £ p Y.则Y是()
答案: NP完全问题
2、
求解NPC问题必须牺牲下面（）特性之一
答案: 求问题的最优解.;
多项式时间求解;
求解问题的任意实例.
3、
P类是所有多项式时间可解的判定问题组成的问题类
答案: 正确
4、
EXP ÍNP
答案: 错误
5、
如果对于X的任意实例，通过多项式次的计算步骤，加多项式次调用Y的算法，可解决X，则 X可多项式时间归约到Y。
答案: 正确
6、
不存在多项式时间算法的问题是难解问题
答案: 正确
7、
给定问题X的任何输入x,构造问题Y的输入y（多项式大小），X回答是iff Y回答是.则问题 X 可以多项式变换到问题Y。
答案: 正确
8、
NP是所有多项式时间可验证的判定问题组成的问题类
答案: 正确
点关注，不迷路，微信扫一扫下方二维码
关注我们的公众号：阿布查查 随时查看答案，网课轻松过
为了方便下次阅读，建议在浏览器添加书签收藏本网页
电脑浏览器添加/查看书签方法
1.按键盘的ctrl键+D键，收藏本页面
2.下次如何查看收藏的网页？
点击浏览器右上角-【工具】或者【收藏夹】查看收藏的网页
手机浏览器添加/查看书签方法
一、百度APP添加/查看书签方法
1.点击底部五角星收藏本网页
2.下次如何查看收藏的网页？
点击右上角【┇】-再点击【收藏中心】查看
二、其他手机浏览器添加/查看书签方法
1.点击【设置】-【添加书签】收藏本网页
2.下次如何查看收藏的网页？
点击【设置】-【书签/历史】查看收藏的网页
