算法分析与设计(新余学院) 中国大学慕课答案2024完整版100分

对应课程:点击查看
起止时间:2020-02-24到2020-08-01
更新状态:已完结

第一章 算法与问题 第一章 测验

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:逼近
答案: 不低于