2020 硕士生算法设计与分析(辽宁工程技术大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-03-19到2020-05-10
本篇答案更新状态:已完结

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

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、 问题:实现下面POJ题目之一，上传代码和AC截图。1）稳定匹配 POJ 34872）最小公倍数 POJ 3970
评分规则: 【 上传代码，质量合格。上传截图，AC真实。
】

【作业】第三章 枚举算法 第三章 作业

1、 问题:实现下面POJ题目之一，上传代码和AC截图。1）尺取法 POJ 30612）折半+枚举 POJ 2785 （3977 2549）3）排列 POJ 1256
评分规则: 【 上传代码，质量合格。上传截图，AC真实。
】

【作业】第五章 递推算法 第五章 作业

1、 问题:实现下面POJ题目之一，上传代码和AC截图。1）递推 POJ 19422）递归 POJ 20833）约瑟夫 POJ 2244 3517 1012
评分规则: 【 上传代码，质量合格。上传截图，AC真实。
】

【作业】第二章 算法分析 第二章 作业

1、 问题:实现下面POJ题目之一，上传代码和AC截图。1）快速幂 POJ 19952）计数排序 POJ 20923）快速查找 POJ 2503
评分规则: 【 上传代码，质量合格。上传截图，AC真实。
】

【作业】第六章 分治算法 第六章 作业二

1、 问题:实现下面POJ题目之一，上传代码和AC截图。1) 大整数乘法 POJ 23892) 线性时间选择 POJ 23883) 最接近点对 POJ 3714 计数逆序 POJ 2299 1007
评分规则: 【 上传代码，质量合格。上传截图，AC真实有效。