大学MOOC 硕士生算法设计与分析(辽宁工程技术大学)1456075163 最新慕课完整章节测试答案

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=1‎while(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: 错误
答案: 【 正确】

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: 错误
答案: 【 正确】

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: 错误
答案: 【 正确】

4、判断题：
负权的最短路问题可以使用Dijkstra算法计算。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

5、判断题：
贪心法处理问题的核心是贪婪准则的选取    ‎
选项：
A: 正确
B: 错误
答案: 【 正确】

6、判断题：
‍贪心算法一般在开始贪心策略前会进行预处理，预处理后再进行最优化选择。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

4.3 知识梳理

1、单选题：
‏区间调度问题贪心算法的时间复杂度是（）‎
选项：
A: Q(n^2)  
B: O(n)
C: W(n^2)
D: O(nlogn)
答案: 【 O(nlogn)】

2、判断题：
交换论证方法把任意一个解逐渐变为贪心算法的解，不会影响其最优性。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

3、判断题：
‍区间划分问题的证明方法是界的方法‎
选项：
A: 正确
B: 错误
答案: 【 正确】

4、判断题：
‍区间选点问题的预处理方法是按照区间的终点递增排序 ‍
选项：
A: 正确
B: 错误
答案: 【 正确】

5、判断题：
‍区间调度问题可以变换为最大独立集问题‏
选项：
A: 正确
B: 错误
答案: 【 正确】

4.4 知识梳理

1、单选题：
​Kruskal算法的时间复杂度是()，更适用于稀疏图。​
选项：
A: nlogn
B: mlogn
C: n^2
D: mn
答案: 【 mlogn】

2、多选题：
‍最小生成树问题可以使用的算法有（ ）‎
选项：
A: Kruskal    
B: Prim
C: Solim 
D: Dijkstra
答案: 【 Kruskal    ;
Prim;
Solim 】

3、判断题：
‏MST是最小连通子图包含n 个顶点和n-1条边​
选项：
A: 正确
B: 错误
答案: 【 正确】

4、判断题：
​Prim算法的贪婪准则是选取割集中的最小边‍
选项：
A: 正确
B: 错误
答案: 【 正确】

5、判断题：
‏Kruskal算法的预处理是边权非递减排序。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

6、判断题：
设S是顶点子集，e是正好一个端点在S中的边中的最小边，那么最小生成树中肯定包含e.‎
选项：
A: 正确
B: 错误
答案: 【 正确】

4.5 知识梳理

1、多选题：
最优前缀码数属于（  ）‍‍
选项：
A: 定长码
B: 变长码
C: 前缀码 
D: 哈夫曼编码
答案: 【 变长码;
前缀码 ;
哈夫曼编码】

2、判断题：
‌前缀码中任一字符的0-1编码都不是其他字符的前缀‏
选项：
A: 正确
B: 错误
答案: 【 正确】

3、判断题：
‏哈夫曼编码给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

4、判断题：
‏哈夫曼编码的预处理是根据频率大小，构造优先队列。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

第四章 测验

1、单选题：
贪心算法基本要素有（   ）和最优子结构性质。‏‌‏
选项：
A: 分解合并性质           
B: 独立子问题性质
C: 贪心选择性质   
D: 重叠子问题性质 
答案: 【 贪心选择性质   】

2、单选题：
‎下面不是证明贪心算法证明方法的有（）。‍
选项：
A: 领先
B: 优化
C: 交换论证  
D: 界 
答案: 【 优化】

3、单选题：
未来与过去无关指的是（  ）的性质‍‍‍
选项：
A: 贪心选择
B: 无后效性  
C: 最优子结构 
D: 重叠子问题
答案: 【 无后效性  】

4、单选题：
使目标函数最大（小）的解是问题的（）‌‌‌
选项：
A: 最优解    
B: 可行解
C: 最大解
D: 最小解
答案: 【 最优解    】

5、单选题：
对于稠密图，使用（）算法计算MST更适合‏​‏
选项：
A:  Kruskal  
B:  Prim 
C: Dijistra
D: Floyd
答案: 【  Prim  】

6、单选题：
‎把任意一个解逐渐变为贪心算法的解，不会影响其最优性。这种证明方法是_()‌
选项：
A: 交换论证
B: 领先
C: 界
D: 归纳
答案: 【 交换论证】

7、单选题：
原问题的最优解包含其子问题的最优解是贪心算法的（）性质。​​​
选项：
A: 贪心选择的性质  
B: 无后效性性质
C: 最优子结构性质 
D: 独立子问题的性质
答案: 【 最优子结构性质 】

8、单选题：
‍区间调度问题贪心算法的时间复杂度是（）​
选项：
A: Q(n^2)  
B: O(n) 
C: W(n^2) 
D: O(nlogn)
答案: 【 O(nlogn)】

9、多选题：
最小生成树问题可以使用的算法有（ ）​
选项：
A: Kruskal   
B: Prim  
C: Solim  
D: Dijkstra
答案: 【 Kruskal   ;
Prim   ;
Solim  】

10、多选题：
区间问题包含()​
选项：
A: 区间调度
B: 区间划分
C: 区间选点
D: 区间覆盖
答案: 【 区间调度;
区间划分;
区间选点;
区间覆盖】

11、多选题：
​贪心算法的基本要素是（）‌
选项：
A: 贪心选择的性质   
B: 无后效性性质
C: 最优子结构性质
D: 独立子问题的性质
答案: 【 贪心选择的性质   ;
无后效性性质;
最优子结构性质】

12、多选题：
​​贪心算法的证明方法有（）  ​​​
选项：
A: 领先
B: 交换论证
C