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

如果一个操作的运行时间是 O(1)，这意味着什么？

1. A它只能运行一次
2. B它每秒运行时间恰好处理一个元素
3. C它的运行时间不随输入规模增长
4. D它总是恰好花费一秒

算法的最坏情况运行时间描述的是什么？

1. A在慢速计算机上所需的时间
2. B在所有规模为 n 的输入上所需的最长时间
3. C在最小输入上所需的时间
4. D在规模为 n 的随机输入上所需的期望时间

归并排序的最坏情况时间复杂度是多少？

1. AO(log n)
2. BO(n²)
3. CO(n log n)
4. DO(n)

下面代码的时间复杂度是多少：for i = 1 to n: (j = 1; while j < n: j = j × 2)？

1. AO(n)
2. BO(log n)
3. CO(n²)
4. DO(n log n)

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

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

用标准的三重循环计算两个 n × n 矩阵的乘积，时间复杂度是多少？

1. AO(n)
2. BO(n³)
3. CO(n²)
4. DO(n² log n)

旅行商问题如何分类？

1. A它属于 P，因为 Dijkstra 算法通过把每个城市访问一次来求解它
2. B判定版本是 NP 完全的，优化版本是 NP 难的
3. C它是不可判定的
4. D判定版本属于 P，但优化版本是 NP 完全的

要证明一个判定问题 X 是 NP 完全的，必须证明哪两点？

1. AX 没有多项式算法，并且 X 是可判定的
2. BX 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X
3. CX 属于 P，并且 X 能归约到 SAT
4. DX 能归约到 P 中的某个问题，并且 X 属于 NP