大学MOOC 算法分析与设计(山东财经大学)1206352809 最新慕课完整章节测试答案

第一章 测验

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

第二章 测验

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=1‍‎‍for i=1 to n  do‍‎‍for 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、单选题：
​顺序查找的时间复杂度为（） ‍
选项：
A: θ(n)  
B: O(n^2）
C: O(logn)
D: o(n^2)
答案: 【 θ(n)   】

11、单选题：
‌‏下面程序的时间复杂度是（）             ‏‌‏i=1‏‌‏while(i<=n)
do‏‌‏       i=i*3‏‌‏
选项：
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、判断题：
‏logn^logn=n^loglogn     ​
选项：
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))  则 logf(n)=O(logg(n))  ‌
选项：
A: 正确
B: 错误
答案: 【 正确】

36、判断题：
‍‏常数阶算法的运行时间与规模n无关。   ‏‍‏
选项：
A: 正确
B: 错误
答案: 【 正确】

37、判断题：
‌从n个数中查找最大值的时间复杂度为W (n)​
选项：
A: 正确
B: 错误
答案: 【 错误】

38、判断题：
​使用合适的数据结构可以同时减少时间和空间​
选项：
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: 错误
答案: 【 正确】

第四章 测验

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、单选题：
‍把任意一个解逐渐变为贪心算法的解，不会影响其最优性。这种证明方法是_()‎