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

f(n) = Θ(g(n)) 是什么意思？

1. Af 的增长严格快于 g
2. Bf 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
3. C对每个 n，f 总是小于 g，因此 g 是它的上界，但绝不是下界
4. Df 的增长严格慢于 g

什么是算法？

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

二分查找对输入有什么要求？

1. A数组长度必须是 2 的幂
2. B数组元素不能超过 1000 个
3. C数组只能包含正数
4. D数组必须有序

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

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

说一个 O(n²) 算法也是 O(n³)，这正确吗？

1. A正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
2. B正确，但仅当 n 小于 100 时
3. C不正确，因为 Big O 必须始终给出函数的确切增长率
4. D不正确，因为当 n 很大时 n³ 小于 n²

对于在满时将容量翻倍的动态数组，追加元素的均摊（amortised）时间复杂度是多少？

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

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

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

Held–Karp 动态规划算法能精确求解旅行商问题。对 n 个城市，它的运行时间是多少？

1. AO(n!)
2. BO(2^n²)
3. CO(n³)
4. DO(n² 2ⁿ)