橇辫凤棺葛女修荤前稿顿呛霖
第一章 算法与问题
1.1 知识梳理
1、单选题：
给定男孩和女孩的两张喜欢列表，GS算法的结果对（ ）是最好的选择。
A: 男孩
B: 女孩
C: 男孩或女孩
D: 男孩和女孩
答案: 男孩
2、多选题：
稳定匹配问题的输出是（ ）
A: 完美匹配
B: 没有不稳定配对
C: 稳定匹配
D: 不稳定匹配
答案: 完美匹配 ;
没有不稳定配对 ;
稳定匹配
3、判断题：
给定一个匹配，如果Z喜欢A甚于匹配的女朋友，A喜欢Z甚于匹配的男朋友，那么A和Z是一个不稳定配对。
A: 正确
B: 错误
答案: 正确
4、判断题：
任意给定两张喜欢列表，稳定匹配问题只有一个稳定匹配。
A: 正确
B: 错误
答案: 错误
1.2 知识梳理
1、单选题：
解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
A: (3)(1)(4)(5)(2)
B: (3)(4)(1)(5)(2)
C: (3)(1)(5)(4)(2)
D: (1)(2)(3)(4)(5)
答案: (3)(1)(5)(4)(2)
2、多选题：
问题的两个要素是（ ）和（）
A: 输入
B: 输出
C: 提问
D: 算法
答案: 输入;
输出
3、多选题：
算法的性质有（）
A: 确定性
B: 有穷性
C: 输入
D: 输出
答案: 确定性;
有穷性;
输入;
输出
4、判断题：
程序总是在有穷步的运算后终止。
A: 正确
B: 错误
答案: 错误
5、判断题：
算法是一步步正确解决问题的方法或策略。
A: 正确
B: 错误
答案: 正确
6、判断题：
程序是算法用某种程序设计语言的具体实现，不能使用自然语言描述。
A: 正确
B: 错误
答案: 正确
7、判断题：
算法每次求解一个实例，而计算机需要求解该问题的所有实例。
A: 正确
B: 错误
答案: 错误
1.3 知识梳理
1、单选题：
从右向左计算p(x) = anxn + an-1xn-1 +… + a1x1 + a0 的数量级为（）
A: n
B: n^2
C: nlogn
D: logn
答案: n
2、多选题：
问题变换的目的（）
A: 复杂变简单
B: 未知变已知
C: 隐式变显式
D: 难解变易解
答案: 复杂变简单;
未知变已知;
隐式变显式;
难解变易解
3、判断题：
传教士和野人问题转换的图是状态空间图。
A: 正确
B: 错误
答案: 正确
4、判断题：
大学入学问题的核心是稳定匹配问题
A: 正确
B: 错误
答案: 正确
5、判断题：
一个问题的实例可以变换为更简单更便利的实例，变换为不同的表达形式。
A: 正确
B: 错误
答案: 正确
第一章 测验
1、单选题：
算法与程序的区别是（）
A: 输入
B: 输出
C: 确定性
D: 有穷性
答案: 有穷性
2、单选题：
解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
A: (3)(1)(4)(5)(2)
B: (3)(4)(1)(5)(2)
C: (3)(1)(5)(4)(2)
D: (1)(2)(3)(4)(5)
答案: (3)(1)(5)(4)(2)
3、单选题：
下面说法关于算法与问题的说法错误的是（）。
A: 如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。
B: 算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
C: 同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
D: 证明算法不正确，需要证明对任意实例算法都不能正确处理。
答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。
4、单选题：
问题变换的目的有（）。(1)复杂变简单 (2)未知变已知 (3)隐式变显式 (4)难解变易解 （5）以上都是。
A: (1)
B: (2)
C: (3)
D: (4)
E: (5)
答案: (5)
5、单选题：
按照霍纳法则，计算p(x) = anxn + an-1xn-1 +… + a1x1 + a0 的数量级为（）
A: n
B: n^2
C: nlogn
D: logn
答案: n
6、单选题：
描述算法的基本方法有( )。(1)自然语言(2)流程图(3)伪代码(4)机器语言
A: A.(2)(3)(4)
B: B.(1)(2)(3)
C: C.(1)(2)(4)
D: D.(1)(2)(3)(4)
答案: B.(1)(2)(3)
7、多选题：
问题变换的方法有（ ）
A: 实例简单化
B: 问题约简
C: 表达变换
D: 分支
答案: 实例简单化;
问题约简 ;
表达变换
8、多选题：
下面关于程序和算法的说法正确的是（）。
A: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
B: 程序是算法用某种程序设计语言的具体实现。
C: 程序总是在有穷步的运算后终止。
D: 算法是一个过程，计算机每次求解是针对问题的一个实例求解
答案: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。;
程序是算法用某种程序设计语言的具体实现。;
算法是一个过程，计算机每次求解是针对问题的一个实例求解
9、多选题：
最大独立集问题和（）问题等价。
A: 最大团
B: 最小顶点覆盖
C: 区间调度问题
D: 稳定匹配问题
答案: 最大团;
最小顶点覆盖
10、多选题：
给定两张喜欢列表，稳定匹配问题的输出是（ ）
A: 完美匹配
B: 没有不稳定配对
C: 最大匹配
D: 稳定匹配
答案: 完美匹配;
没有不稳定配对;
最大匹配 ;
稳定匹配
11、判断题：
给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。
A: 正确
B: 错误
答案: 错误
12、判断题：
计算机每次求解是针对问题的每个实例求解。
A: 正确
B: 错误
答案: 错误
13、判断题：
同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
A: 正确
B: 错误
答案: 正确
14、判断题：
证明算法不正确，只需给出一个反例，算法不能正确处理即可。
A: 正确
B: 错误
答案: 正确
15、判断题：
同一算法只有一种形式描述
A: 正确
B: 错误
答案: 错误
16、判断题：
一个问题的同一实例可以有不同的表示形式。
A: 正确
B: 错误
答案: 正确
17、判断题：
算法必须在有穷时间终止
A: 正确
B: 错误
答案: 正确
18、判断题：
一个问题的算法必须在有穷时间终止，并且对一切合法的输入都能得出满足要求的结果。
A: 正确
B: 错误
答案: 正确
19、判断题：
问题的两个要素是输入和实例。
A: 正确
B: 错误
答案: 错误
20、判断题：
算法是一个语句集合，按照顺序执行语句，处理实例，得到正确答案。
A: 正确
B: 错误
答案: 正确
第二章 算法分析
2.1 知识梳理
1、多选题：
计算算法的时间复杂度只要选取()
A: 最复杂部分的运行时间
B: 关键操作的运行时间
C: 在最坏情况下运行时间
D: 在平均情况下的运行时间
答案: 最复杂部分的运行时间 ;
关键操作的运行时间 ;
在最坏情况下运行时间
2、判断题：
算法分析的两种方法是事前分析和事后统计。
A: 正确
B: 错误
答案: 正确
3、判断题：
算法分析的两个阶段是粗粒度比较数量级和细粒度比较各种情况。
A: 正确
B: 错误
答案: 正确
4、判断题：
求解问题的输入量,称为问题的规模。
A: 正确
B: 错误
答案: 正确
5、判断题：
时间复杂度就是算法运行的时间的度量，衡量算法的效率。
A: 正确
B: 错误
答案: 正确
2.2 知识梳理
1、单选题：
g(n)为f(n)的下界,记为:f(n)= (g(n))
A: Ο
B: Ω
C: θ
D: ω
答案: Ω
2、单选题：
f(n)=3n^3+7n^2+4nlogn =（ ）(n^3）
A: Ο
B: Ω
C: θ
D: ω
答案: ω
3、判断题：
O(f(n))+O(g(n)) = O(min{f(n),g(n)})
A: 正确
B: 错误
答案: 错误
4、判断题：
任何多项式时间算法都是好算法，都是有效的。
A: 正确
B: 错误
答案: 错误
5、判断题：
f(n)=
(g(n)) 则 f(n)=Ο(g(n))且f(n)=Ω(g(n))
A: 正确
B: 错误
答案: 正确
6、判断题：
f=o(g)且g = o(h) 则 f=o(h)
A: 正确
B: 错误
答案: 正确
2.3 知识梳理
1、单选题：
如果 
=0, 则 f(n)= (g（(n)）
A: Ο
B: Ω
C: θ
D: o
答案: o
2、单选题：
logn!=Q( )
A: n
B: nlogn
C: n^2
D: logn
答案: nlogn
3、多选题：
n!=()
A: 
B: 
C: 
D: 
答案: ;
4、判断题：
A: 正确
B: 错误
答案: 正确
5、判断题：
对于任意 x > 0, log n = o(n^x)
A: 正确
B: 错误
答案: 正确
6、判断题：
, 常数a, b > 0.
A: 正确
B: 错误
答案: 正确
7、判断题：
对任意 r > 1 和 d > 0, nd = o(r^n).
A: 正确
B: 错误
答案: 正确
8、判断题：
, 常数a, b > 0.
A: 正确
B: 错误
答案: 正确
2.4 知识梳理
1、单选题：
顺序查找的时间复杂度为（）
A: θ(n)
B: O（n^2)）
C: O(nlogn)
D: o（n^2）
答案: θ(n)
2、单选题：
下面程序的时间复杂度是（） i=1while(i<=n) do i=i*3
A: Q(logn)
B: Q(n)
C: O(n)
D: Ω(n)
答案: Q(logn)
3、单选题：
快速幂求x^n的时间复杂度为O（）
A: n
B: logn
C: nlogn
D: n^1/2
答案: logn
4、判断题：
T1(n)+T2(n)=O(max(f(n),g(n)))，因此并行语句时间复杂度等于两者中高的复杂度。
A: 正确
B: 错误
答案: 正确
5、判断题：
O(f)*O(g)=O(f*g)，因此循环语句的时间复杂度等于循环体的时间复杂度与循环次数的乘积。
A: 正确
B: 错误
答案: 正确
6、判断题：
从n个数中查找最大值的时间复杂度为W (n)
A: 正确
B: 错误
答案: 错误
2.5 知识梳理
1、单选题：
给定图G=(V,E), |V|=n, |E|=m, 其邻接矩阵的空间复杂度为( )
A: θ(n^2)
B: O(n)
C: W(n^3)
D: o(n^2)
答案: θ(n^2)
2、多选题：
下面以空间换时间的方法有（）
A: 预处理
B: 预构造
C: 动态规划
D: 数据压缩
答案: 预处理 ;
预构造 ;
动态规划
3、判断题：
空间复杂度S(n)是算法执行所需所有空间的资源量
A: 正确
B: 错误
答案: 错误
4、判断题：
时空均衡可通过以时间换空间或以空间换时间实现
A: 正确
B: 错误
答案: 正确
5、判断题：
给定n个整数，n个数的取值范围为[1,k], 计数排序的时间复杂度是O （n+k） 。
A: 正确
B: 错误
答案: 正确
6、判断题：
使用散列可以降低查找的时间复杂度
A: 正确
B: 错误
答案: 正确
第二章 测验
1、单选题：
从资源划分，算法的复杂度分为()和()。
A: 时间复杂度 空间复杂度
B: 空间复杂度 平均复杂度
C: 最好复杂度 最坏复杂度
D: 时间间复杂度 平均复杂度
答案: 时间复杂度 空间复杂度
2、单选题：
算法复杂度分析的两种基本方法为（ ）和（ ）
A: 结构化方法 面向对象方法
B: 事后统计 事前分析
C: 几何复杂度 平均复杂度
D: 平摊复杂度 平滑复杂度
答案: 事后统计 事前分析
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）的阶。
A: 不高于
B: 不低于
C: 等价于
D: 逼近
答案: 不低于
4、单选题：
f(n)= 100 当n为奇数 f(n)=5n^2+3n. 当n为偶数 f(n)的渐进性态f(n)= W( )
A: n
B: n^2
C: 2^n
D: 1
答案: 1
5、单选题：
下面程序的时间复杂度为（） x=1for i=1 to n dofor j=1 to i do for k=1 to j do
x++
A: n
B: n^3
C: n^2
D: nlogn
答案: n^3
6、单选题：
对近似递增序列的线性表从小到大排序，使用哪种方法好？
A: 堆排序
B: 快速排序
C: 插入排序
D: 归并排序
答案: 插入排序
7、单选题：
给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。
A: 10
B: 100
C: 1000
D: 141
答案: 100
8、单选题：
给定图G=(V,E), |V|=n, |E|=m, 遍历其邻接表的时间复杂度为θ( )
A: n
B: m
C: n+m
D: n^m
答案: n+m
9、单选题：
logn!=Q( )
A: n
B: nlogn
C: n^2
D: logn
答案: nlogn
10、单选题：
给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。
A: 10
B: 100
C: 1000
D: 0.1
答案: 100
11、单选题：
下面程序的时间复杂度是（） i=1while(i<=n)
do i=i*5
A: Q(logn)
B: Q(n)
C: O(n)
D: Ω(n)
答案: Q(logn)
12、单选题：
给定n个整数，n个数的取值范围为[1,k],计数排序的时间复杂度是O （n+k） 。
A: n+k
B: n
C: k
D: nk
答案: n+k
13、单选题：
给定图G=(V,E), |V|=n, |E|=m, 其邻接矩阵的空间复杂度为( )
A: θ(n^2)
B: O(n)
C: W(n^2)
D: o(n^2)
答案: θ(n^2)
14、多选题：
顺序查找适合的数据结构是（）
A: 散列存储
B: 顺序存储
C: 链式存储
D: 压缩存储
答案: 顺序存储;
链式存储
15、多选题：
f(n)=3n^3+7n^2+4nlogn =（）（n^3）
A: Ο
B: Ω
C: θ
D: o
E: ω
答案: Ο;
Ω;
θ
16、多选题：
下面那些算法的时间复杂度为O（n^2）?
A: 顺序查找
B: 折半查找
C: 插入排序
D: 冒泡排序
E: 折半插入排序
答案: 插入排序;
冒泡排序;
折半插入排序
17、多选题：
两个n*n的矩阵相加的时间复杂度是（ ）
A: θ(n^2)
B: O(n^2)
C: W(n^2)
D: o(n^2)
答案: θ(n^2);
O(n^2);
W(n^2)
18、多选题：
以空间换时间的方法有（）
A: 预处理
B: 预构造
C: 动态规划
D: 数据压缩
答案: 预处理 ;
预构造;
动态规划
19、判断题：
时间复杂度是指算法最坏情况下的运行时间。
A: 正确
B: 错误
答案: 正确
20、判断题：
f(n)=O(g(n)) 且 g(n)=O(h(n))，则h(n)=O(f(n))
A: 正确
B: 错误
答案: 错误
21、判断题：
f(n)=O(g(n)) 则 f(n)^2=O(g(n)^2)
A: 正确
B: 错误
答案: 正确
22、判断题：
f(n)=3n^3+7n^2+4nlogn =O（n^2）
A: 正确
B: 错误
答案: 错误
23、判断题：
如果一个算法是多项式时间算法，该算法是有效的,是好算法。
A: 正确
B: 错误
答案: 正确
24、判断题：
n!=o(2^n)
A: 正确
B: 错误
答案: 错误
25、判断题：
A: 正确
B: 错误
答案: 正确
26、判断题：
折半查找的时间复杂度为Q(nlogn)
A: 正确
B: 错误
答案: 错误
27、判断题：
f(n)=θ(g(n)) 当且仅当 g(n)=θ(f(n))
A: 正确
B: 错误
答案: 正确
28、判断题：
f=O(g)当且仅当 g =Ω (f)
A: 正确
B: 错误
答案: 正确
29、判断题：
时间复杂度就是算法运行的时间的度量，衡量算法的效率。
A: 正确
B: 错误
答案: 正确
30、判断题：
求解问题的输入量,称为问题的规模 。
A: 正确
B: 错误
答案: 正确
31、判断题：
O(f(n))+O(g(n)) = O(min{f(n),g(n)})
A: 正确
B: 错误
答案: 错误
32、判断题：
任何多项式时间算法都是好算法，都是有效的。
A: 正确
B: 错误
答案: 错误
33、判断题：
任何情况下，复杂性渐近阶低的算法都比复杂性渐近阶高的算法有效。
A: 正确
B: 错误
答案: 错误
34、判断题：
对任意 r > 1 和 d > 0, n^d= o(r^n).
A: 正确
B: 错误
答案: 正确
35、判断题：
f(n)=O(g(n)) 则 log（f(n)) =O(log(g(n)))
A: 正确
B: 错误
答案: 正确
36、判断题：
常数阶算法的运行时间与规模n无关。
A: 正确
B: 错误
答案: 正确
37、判断题：
从n个数中查找最大值的时间复杂度为W (n)
A: 正确
B: 错误
答案: 错误
38、判断题：
使用合适的数据结构可以同时减少时间和空间
A: 正确
B: 错误
答案: 正确
第三章 枚举算法
3.1 知识梳理
1、多选题：
枚举算法的优化方法有（）
A: 减少枚举变量
B: 减少枚举变量的值域
C: 优化算法
D: 优化数学模型
答案: 减少枚举变量;
减少枚举变量的值域;
优化算法;
优化数学模型
2、判断题：
冒泡排序的时间复杂度为O(nlogn)
A: 正确
B: 错误
答案: 错误
3、判断题：
0/1背包问题的时间复杂度为O（n2^n）
A: 正确
B: 错误
答案: 正确
4、判断题：
在某些问题实例中枚举是唯一的解决方法。
A: 正确
B: 错误
答案: 正确
5、判断题：
最好情况下，冒泡排序和选择排序的时间复杂度都是O（n^2）
A: 正确
B: 错误
答案: 错误
3.2 知识梳理
1、多选题：
子集生成方法有（）
A: 增量构造法
B: 二进制法
C: 位向量法
D: 位向量法
答案: 增量构造法;
二进制法;
位向量法
2、判断题：
位向量法生成子集，不直接构造子集本身。
A: 正确
B: 错误
答案: 正确
3、判断题：
二进制法生成子集，子集与运算可以生成并集
A: 正确
B: 错误
答案: 错误
4、判断题：
增量构造法生成子集前需要定序
A: 正确
B: 错误
答案: 正确
第三章 测验
1、单选题：
便于实现集合操作的子集生成算法是（）
A: 增量构造法
B: 位向量法
C: 二进制法
D: 法向量法
答案: 二进制法
2、单选题：
logn^2=( )(logn+5)
A: θ
B: O
C: W
D: o
答案: θ
3、单选题：
0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？
A: 40
B: 60
C: 30
D: 50
答案: 40
4、单选题：
A公司处理器速度是B公司的100倍。对于复杂度为n^2的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时能处理的问题规模是()
A: 10n
B: 100n
C: 10000n
D: 1000n
答案: 10n
5、单选题：
直接插入排序的时间复杂度是（）。
A: θ(n)
B: O(n^2)
C: W(n^2)
D: o(n^2)
答案: O(n^2)
6、单选题：
选择排序的时间复杂度是O（____）
A: n
B: n^2
C: nlogn
D: logn
答案: n^2
7、多选题：
分数拆分问题的枚举算法通过（）方法进行了优化。
A: 减少枚举变量
B: 减少枚举变量的值域
C: 优化数据结构
D: 优化数学模型
答案: 减少枚举变量 ;
减少枚举变量的值域 ;
优化数学模型
8、多选题：
子集生成方法有（）
A: 增量构造法
B: 二进制法
C: 位向量法
D: 法向量法
答案: 增量构造法 ;
二进制法;
位向量法
9、多选题：
枚举算法的优化方法有（）
A: 减少枚举变量
B: 减少枚举变量的值域
C: 优化算法
D: 优化数学模型
答案: 减少枚举变量 ;
减少枚举变量的值域 ;
优化算法;
优化数学模型
10、判断题：
冒泡排序的时间复杂度为W(n^2)
A: 正确
B: 错误
答案: 错误
11、判断题：
0-1背包问题的枚举算法的时间复杂度为O(2^n）
A: 正确
B: 错误
答案: 错误
12、判断题：
增量构造法生成子集前需要对集合中元素从小到大排列。
A: 正确
B: 错误
答案: 正确
13、判断题：
二进制法生成子集，子集与运算可以生成并集
A: 正确
B: 错误
答案: 错误
14、判断题：
枚举法适用于问题的小规模实例。
A: 正确
B: 错误
答案: 正确
15、判断题：
减少枚举变量可以减少枚举算法的时间复杂度
A: 正确
B: 错误
答案: 正确
16、判断题：
位向量法生成子集，子集或运算可以生成差集
A: 正确
B: 错误
答案: 错误
17、判断题：
分块查找一般设分块的长度是n/2.
A: 正确
B: 错误
答案: 错误
18、判断题：
旅行商问题的枚举算法的时间复杂度为O（n!）
A: 正确
B: 错误
答案: 正确
19、判断题：
在某些问题实例中枚举是唯一的解决方法。
A: 正确
B: 错误
答案: 正确
20、判断题：
蛮力法适用于问题的小规模实例。
A: 正确
B: 错误
答案: 正确
第四章 贪心算法
4.1 知识梳理
1、单选题：
部分背包问题的时间复杂度是O( )
A: n
B: n^2
C: nlogn
D: logn
答案: nlogn
2、判断题：
贪心算法的思想是依据贪婪准则作出决策，逐步构造解值。
A: 正确
B: 错误
答案: 正确
3、判断题：
贪心算法的思想是寻求局部最优解，逐步达到全局最优解
A: 正确
B: 错误
答案: 正确
4、判断题：
贪心算法总能找到可行解，并且是最优解。
A: 正确
B: 错误
答案: 错误
5、判断题：
部分背包问题的证明方法是领先的方法
A: 正确
B: 错误
答案: 正确
4.2 知识梳理
1、判断题：
原问题的最优解包含其子问题的最优解是最优子结构的性质。
A: 正确
B: 错误
答案: 正确
2、判断题：
通过一系列局部最优的选择（贪心选择）达到全局最优是贪心选择的性质
A: 正确
B: 错误
答案: 正确
3、判断题：
问题的全过程可以分为若干个阶段，而且在任何一个阶段x后的行为都只仅仅依赖于x的状态，而与x之前如何达到这种状态的方式无关。这是无后效性的性质
A: 正确
B: 错误
答案:
上方为免费预览版答案，如需购买完整答案，请点击下方红字：
为了方便下次阅读，建议在浏览器添加书签收藏本网页
添加书签方法：
1.电脑按键盘的Ctrl键+D键即可收藏本网页
2.手机浏览器可以添加书签收藏本网页
点击浏览器底部菜单-【添加书签】-收藏本网页
点击浏览器底部菜单-【书签/历史】-可查看本网页
获取更多慕课答案，欢迎在浏览器访问我们的网站：
http://mooc.mengmianren.com
注：请切换至英文输入法输入域名，如果没有成功进入网站，请输入完整域名：http://mooc.mengmianren.com/
我们的公众号
打开手机微信，扫一扫下方二维码，关注微信公众号：萌面人APP
本公众号可查看各种网课答案，还可免费查看大学教材答案
点击这里，可查看公众号功能介绍
APP下载
APP功能说明
1.可查看各种网课答案
点击【萌面人官网】，可查看知到智慧树，超星尔雅学习通，学堂在线等网课答案
点击【中国大学慕课答案】，可查看mooc慕课答案
2.可一键领取淘宝/天猫/京东/拼多多无门槛优惠券
如图所示，点击对应图标即可领取淘宝/天猫/京东/拼多多无门槛优惠券
晃倍家糜时添狸前娩文怒鹃颈