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

什么是递归？

1. A在更小的输入上调用自身的函数
2. B一种数据结构
3. C一种排序方法
4. D永远不会结束的循环

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

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

一个问题通常在什么情况下被称为易解的（tractable）？

1. A能在多项式时间内求解
2. B能在常数时间内求解
3. C没有解
4. D只能通过尝试所有可能来求解

贪心算法（greedy algorithm）：

1. A在每一步都做出局部最优的选择
2. B尝试所有可能的解
3. C只使用递归
4. D总能给出最优解

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

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

当问题具有以下特征时，动态规划（dynamic programming）很有用：

1. A只有随机输入
2. B只有一个循环
3. C完全没有子问题，因此一步就能解决
4. D重叠子问题和最优子结构

Strassen 算法在矩阵乘法中对半尺寸的分块只做 7 次而不是 8 次递归乘法。它的运行时间是多少？

1. AΘ(n³)
2. BΘ(n^{log₂ 7})，约为 n^2.81
3. CΘ(n² log n)
4. DΘ(n²)

关于 log(n!)，哪个界是正确的？

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