算法分析与设计答案2023秋

第一章测试

1.算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。（ ）
A:错 B:对
答案:B
2.计算机的资源最重要的是内存和运算资源。因而，算法的复杂性有时间和空间之分。（ ）
A:对 B:错
答案:A
3.时间复杂度是指算法最坏情况下的运行时间。（ ）
A:错 B:对
答案:A
4.下面关于算法的说法中正确的是 。
（1）求解某一问题的算法是唯一的。
（2）算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
（3）算法的每一条指令是清晰无歧义的。
（4）算法可以用某种程序设计语言具体实现，所以算法和程序是等价的。（ ）
A:（1）（3）
B:（2）（4）
C:（2）（3）
D:（1）（2）

答案:C
5.描述算法的基本方法有 。
（1）自然语言
（2）流程图
（3）伪代码
（4）程序设计语言 （ ）
A:（1）(2)（3）(4)
B:（2）（3）(4)
C:（1）（2）（3）
D:（1）（3）(4)

答案:A
6.算法分析是（ ）
A:在抽象数据数据集合上执行程序，以确定是否产生错误结果
B:对算法需要多少计算时间和存储空间作定量分析
C:证明算法对所有可能的合法出入都能算出正确的答案
D:将算法用某种程序设计语言恰当地表示出来

答案:B
7.算法是由若干条指令组成的有穷序列，而且满足以下叙述中的 性质。
(1)输入：有0个或多个输入
(2)输出：至少有一个输出
(3)确定性：指令清晰、无歧义
(4)有限性：指令执行次数有限，而且执行时间有限 （ ）
A:（1）（3）（4）
B:（1）（2）（3）
C:（1）（2）（3）（4）
D:（1）（2）（4）

答案:C
8.

下面函数中增长率最低的是（ ）

A:log₂n B:n² C:n
D:2ⁿ
答案:A
9.下面属于算法的特性有( )。
A:有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
B:输入：有0个或多个外部量作为算法的输入。
C:确定性：组成算法的每条指令是清晰，无歧义的。
D:输出：算法产生至少一个量作为输出。

答案:ABCD
10.当m为24，n为60时，使用欧几里得算法求m和n的最大公约数，需要进行（ ）次除法运算。
A:4次
B:3次
C:2次
D:不确定

答案:B
1.

一个问题的同一实例可以有不同的表示形式

A:对 B:错
答案:A
2.

同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。

A:错 B:对
答案:B
3.

问题的两个要素是输入和实例。

A:对 B:错
答案:B
4.

算法与程序的区别是（）

A:确定性 B:输入 C:有穷性 D:输出
答案:C
5.

解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明

A:(3)(1)(5)(4)(2) B:(3)(4)(1)(5)(2) C:(1)(2)(3)(4)(5) D:(3)(1)(4)(5)(2)
答案:A
6.

下面说法关于算法与问题的说法错误的是（）。

A:证明算法不正确，需要证明对任意实例算法都不能正确处理。 B:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。 C:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。 D:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
答案:A
7.

下面关于程序和算法的说法正确的是（）。

A:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。 B:程序总是在有穷步的运算后终止。 C:程序是算法用某种程序设计语言的具体实现。 D:算法是一个过程，计算机每次求解是针对问题的一个实例求解。
答案:ACD
8.

最大独立集问题和（）问题等价。

A:最大团 B:区间调度问题 C:稳定匹配问题 D:最小顶点覆盖
答案:AD
9.

给定两张喜欢列表，稳定匹配问题的输出是（  ） 。

A:完美匹配 B:最大匹配 C:没有不稳定配对 D:稳定匹配
答案:ABCD
10.

问题变换的目的有（）。(1)复杂变简单 (2)未知变已知 (3)隐式变显式 (4)难解变易解 （5）以上都是。

A:（2）
B:（4）
C:（3）
D:（1）
E:（5）
答案:E
11.

按照霍纳法则，计算p(x) = a_nxⁿ + a_n-1x^n-1 +… + a₁x¹ + a₀   的数量级为____ 。

A:logn
B:n^2
C:n
D:nlogn

答案:C
1.算法是指解决问题的方法或过程，它包含一系列步骤，用来将输入数据转换成输出结果。
A:错 B:对
答案:B
2.使用伪代码描述算法具有（ ）等优点。
A:易于转化为程序语言代码 B:格式统一规范 C:简单易懂 D:容易修改
答案:ACD
3.算法通常具有（ ）的性质。
A:有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限 B:确定性：组成算法的每条指令清晰、无歧义 C:输出：至少有一个输出 D:输入：有零个或多个输入
答案:ABCD
4.程序是算法用某种程序设计语言的具体实现，程序需满足算法的所有性质。
A:对 B:错
答案:B
5.常用的描述算法的形式有（ ）。
A:程序流程图 B:机器语言 C:伪代码 D:自然语言
答案:ACD
6.函数f(n)=20log3^n的渐进表达式是（ ）。
A:0(log(n)) B:0（n^2） C:0(1) D:O(n)
答案:D
7.一个算法的优劣由（ ）决定。
A:时间复杂度 B:代码长度 C:空间复杂度 D:使用的编程语言
答案:AC
8.如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)),即f(N)的阶不高于g(N）的阶。
A:对 B:错
答案:A
9.分析以下代码的时间复杂度：
int func(int n)
{
int i=1, k=0;
while(i<=n) {
k++;
i=i*2;
}
return k;
}
A:O(n) B:O(n^2) C:O(logn) D:O(n/2)
答案:C
10.对于f(n)=n，下列说法正确的是（ ）。
A:f(n)=O(n) B:f(n)=O(1/n) C:f(n)=O(n^2) D:f(n)=O(n^3)
答案:ACD
1.

算法具备的四个基本性质是（）

A:输出 B:输入 C:有限性 D:确定性
答案:ABCD
2.

算法就是程序

A:错 B:对
答案:A
3.

描述渐进上界的符号是（）

A:Ω B:ω C:O D:θ
答案:C
4.

f(n)=3n2+n+1,下面不正确的是()

A:f(n)=O(3n2) B:f(n)=O(2n) C:f(n)=O(n3) D:f(n)=O(n2)
答案:B
5.

在算法分析中，我们希望找到更加高阶的上界函数

A:错 B:对
答案:A