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

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

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

什么是记忆化（memoisation）？

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

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

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

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

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

哪种排序算法是稳定的？

1. A选择排序（常见版本）
2. B堆排序
3. C快速排序（常见的原地版本）
4. D归并排序

一个函数先运行一个 n 次迭代的循环，然后再单独运行另一个 n 次迭代的循环。它的时间复杂度是多少？

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

关于 P 和 NP，下列哪个说法是正确的？

1. ANP 表示“not polynomial”（非多项式）
2. BNP 问题无法被快速验证
3. C已经证明 P ≠ NP
4. DP 中的每个问题也都属于 NP

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

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