Free Printable Final Exam（Chinese）

1.

算法的五个基本特性不包括：

a)

有穷性

b)

输出

c)

输入

d)

复杂性

e)

确定性

2.

（多选）关于算法复杂度的描述，正确的是：

a)

时间复杂度只考虑最坏情况

b)

$O(n)$ 算法在数据规模翻倍时，运行时间约翻倍

c)

$O(1)$ 表示算法执行时间与输入规模无关

d)

空间复杂度与时间复杂度无关

3.

下列哪个不是算法的描述方法：

a)

程序代码

b)

流程图

c)

伪代码

d)

诗歌

e)

自然语言

4.

如果算法 a 的时间复杂度为 $O(n)$ ，算法 b 为 $O(n^2)$ ，当 n 足够大时：

a)

B 比 A 快

b)

A 比 B 快

c)

无法确定

d)

两者一样快

5.

下列时间复杂度中，效率最高的是：

a)

$O(n!)$

b)

$O(n^2)$

c)

$O(2^n)$

d)

$O(n^3)$

6.

递归算法的基本组成部分是：

a)

函数和变量

b)

输入和输出

c)

基础条件和递归条件

d)

循环和条件

7.

分析下面代码的时间复杂度：for i in range(n): for j in range(i, n): print(i, j)

a)

$O(n^2)$

b)

$O(2^n)$

c)

$O(n)$

d)

$O(n\log n)$

8.

算法的健壮性指标是：

a)

占用内存少

b)

代码简洁

c)

运行速度快

d)

能处理异常输入

9.

冒泡排序的最好情况的时间复杂度是：

a)

$O(n^2)$

b)

$O(n)$

c)

$O(n\log n)$

d)

$O(1)$

10.

快速排序的平均时间复杂度是：

a)

$O(n)$

b)

$O(n\log n)$

c)

$O(\log n)$

d)

$O(n^2)$

11.

当数据基本有序时，哪种排序算法最快？

a)

选择排序

b)

快速排序

c)

插入排序

12.

在整理扑克牌时，人们通常不自觉使用的排序思维是：

a)

快速排序

b)

冒泡排序

c)

插入排序

d)

选择排序

13.

递归函数必须包含：

a)

循环结构，否则会没有难度

b)

全局变量，否则会无法正确输出

c)

多个参数，否则会没法计算

d)

基础条件，否则会鬼打墙

14.

汉诺塔问题的时间复杂度是：

a)

$O(2^n)$

b)

$O(n^2)$

c)

$O(n\log n)$

d)

$O(n)$

15.

用递归计算阶乘时，基础条件是：

a)

n == 0

b)

n < 0

c)

n = 1

d)

n > 1

16.

Dijkstra 算法用于解决：

a)

图着色

b)

最小生成树

c)

最短路径

d)

排序

17.

Dijkstra 算法不能处理：

a)

有向图

b)

稀密图

c)

负权边

d)

无向图

18.

下列哪种情况适合使用贪心算法？

a)

排序问题

b)

活动时间安排问题

c)

最短路径问题

d)

八皇后问题

19.

八皇后问题通常使用哪种方法解决？

a)

贪心算法

b)

分治算法

c)

回溯算法

d)

动态规划

20.

回溯法的核心思想是：

a)

分解问题

b)

试探并回退

c)

合并结果

d)

每一步选择最优

21.

贪心算法的关键特征是什么？

a)

用递归来解决问题

b)

时间复杂度为 $O(n\log n)$

c)

总能找到全局最优解

d)

在每一步做出局部最优选择

22.

哪种数据结构遵循后进先出（LIFO）原则？

a)

数组

b)

队列

c)

栈

d)

链表

23.

对 [5, 1, 4, 2, 8] 进行第一轮冒泡排序（升序）后的序列是：

a)

[1, 5, 4, 2, 8]

b)

[1, 2, 4, 5, 8]

c)

[1, 4, 2, 5, 8]

d)

[5, 1, 4, 2, 8]

24.

贪心算法在“找零钱”问题中（用最少硬币），如果币值为 [1, 3, 4]，要凑 6 元，贪心法给出：

a)

1+1+1+1+1+1（6 枚）

b)

3+3（2 枚）

c)

4+1+1（3 枚）

d)

4+3（无法凑出）

25.

八皇后问题中，判断冲突不包括检查：

a)

同列

b)

同颜色

c)

同对角线

d)

同行

26.

给地图上的国家染色，使相邻国家颜色不同，这本质上是：

a)

查找问题

b)

图着色问题

c)

最短路径问题

d)

排序问题

27.

如果一个算法的时间复杂度是 $O(2^n)$ ，当 n 增大时，运行时间会：

a)

保持不变

b)

缓慢增长

c)

指数级爆炸增长

d)

线性增长

28.

评价一个算法的好坏，我们通常更关注它的______。

a)

最好情况

b)

最坏情况

c)

平均情况

d)

空间情况

29.

在游戏中，需要按事件触发顺序来处理游戏逻辑（如先发生的攻击先计算伤害），应该使用：

a)

树

b)

队列

c)

栈

d)

图

30.

选择排序每一轮的操作是：

a)

递归分割数组

b)

交换相邻元素

c)

选择最小元素放到当前位置

d)

插入元素到已排序序列

31.

图着色问题要求相邻结点：

a)

度数相同

b)

颜色数量最少

c)

颜色相同

d)

颜色不同

32.

算法复杂度分析的主要目的是：

a)

证明算法正确性

b)

增加功能

c)

减少代码长度

d)

比较算法效率

33.

空间复杂度是衡量算法对______的占用。

a)

磁盘

b)

网络

c)

内存

d)

时间

34.

在图书馆整理按出版年份排序的书籍，适合用：

a)

插入排序

b)

快速排序

c)

选择排序

d)

冒泡排序

35.

导航软件计算最短路径通常使用：

a)

冒泡排序

b)

Prim 算法

c)

回溯算法

d)

Dijkstra 算法

36.

下列英文缩写中，FIFO 的含义是：

a)

First In Last Out

b)

First In First Out

c)

Use less memory

d)

Fast Input Fast Output

37.

分析以下代码的时间复杂度：

```python

def mystery_function(n):

count = 0

i = 1

while i < n:

j = 1

while j < n:

count += 1

j = j * 2

i = i + 1

return count

```

(a)

38.

用动态规划算法解决背包问题：根据图中“物品重量与价值”和右侧的动态规划表，求在背包容量为 $6$ 时表格“?”处应填写的数字和最后选择的物品序号。

(a)

Final Exam（Chinese）

Total questions: 38

Worksheet time: 22mins