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

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

1. A1 秒
2. B8 秒
3. C2 秒
4. D4 秒

一个循环从 i = 1 开始，每次迭代将 i 翻倍，直到 i > n。它运行多少次迭代？

1. A约 n² 次
2. B约 n / 2 次
3. C约 n 次
4. D约 log₂ n 次

在有序数组上进行二分查找（binary search）的时间复杂度是多少？

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

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

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

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

1. A已经有序的数组
2. B长度为 2 的数组
3. C随机顺序的数组
4. D所有元素都不相同的数组

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

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

使用主定理，T(n) = 8T(n/2) + O(n²) 的解是：

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n³)

停机问题（halting problem）表明：

1. A每个程序最终都会停机
2. B不存在一种算法能对所有程序和输入判定其是否会停机
3. C应当避免使用循环
4. D有些程序在更快的计算机上运行得更快，所以是否停机取决于硬件