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

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

1. A9 秒
2. B6 秒
3. C3 秒
4. D12 秒

什么是蛮力算法（brute-force algorithm）？

1. A随机猜测答案的算法
2. B尝试所有可能的候选解的算法
3. C总是使用递归的算法
4. D在多个处理器上运行的算法

什么是记忆化（memoisation）？

1. A在每行代码旁边写注释
2. B函数返回后释放内存
3. C存储函数调用的结果，使重复调用能直接从内存中得到答案
4. D自动把递归转换为等价的循环，从而不需要调用栈

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

1. A指数级
2. B对数级
3. C线性
4. D常数

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

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

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

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

停机问题（halting problem）表明：

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

递推式 T(n) = 2T(n/2) + n log n 的解是什么？

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