算法与复杂度练习卷（附答案）

一个算法的运行时间是 O(n)。这种增长称为什么？

1. A平方
2. B对数
3. C常数
4. D线性

什么是算法？

1. A解决问题的、由有限个明确定义的步骤组成的序列
2. B一种为书写数学公式而设计的编程语言
3. C任何带有图形界面的计算机程序
4. D一种存储数字的数据结构

归并排序采用哪种设计策略？

1. A蛮力法
2. B动态规划
3. C贪心选择
4. D分治法（divide and conquer）

对 n 个元素的数组进行归并排序，递归共有多少层？

1. A约 n 层
2. B约 n / 2 层
3. C约 log₂ n 层
4. D约 √n 层

为什么动态规划不能真正加速归并排序？

1. A归并排序没有递归结构
2. B它的子问题不重叠，因此没有可以复用的结果
3. C归并排序已经是 O(n)
4. D动态规划只适用于图问题，不适用于数组

为什么许多库排序函数在子数组很小时会改用插入排序？

1. A在大规模输入上，插入排序比任何其他排序算法使用的内存都少
2. B递归算法无法处理少于 10 个元素的数组
3. C插入排序开销小，在小规模或几乎有序的输入上很快
4. D插入排序在最坏情况下是 O(n log n)

最短简单路径可以在多项式时间内求出。在一般图中求两个顶点之间的最长简单路径，已知情况如何？

1. A可以把权重取反后用 Dijkstra 算法求解
2. B总能在 O(V + E) 内求解
3. C它是 NP 难的
4. D它是不可判定的

关于类 NP 的哪个定义是正确的？

1. A不能在多项式时间内求解的问题
2. B非多项式的问题
3. C给定证书时，其"是"答案能在多项式时间内验证的判定问题
4. D任何算法都无法求解的问题