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

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

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

一个算法的运行时间是 O(n)。这种增长称为什么？

1. A常数
2. B平方
3. C线性
4. D对数

一个包含两层嵌套循环、每层都执行 n 次的算法，通常具有哪种复杂度？

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

对长度为 m 和 n 的两个字符串求最长公共子序列，标准动态规划算法的时间复杂度是多少？

1. AO(mn)
2. BO(mn log n)
3. CO(m + n)
4. DO(2^m+n)

关于一个没有可达基本情况的递归函数，下列哪个说法是正确的？

1. A它会自动返回 0
2. B编译器总会把它变成能安全结束的循环
3. C它会不断调用自身，直到调用栈溢出
4. D它的运行时间为 O(1)

为什么在 Big O 中通常省略对数的底，例如写成 O(log n)？

1. A对数总是被四舍五入为整数
2. B计算机科学中所有对数的底都是 10，所以可以省略
3. C不同底的对数之间只相差一个常数因子
4. D底只在 n 很小时才有影响

如果有人为某个 NP 完全问题找到了多项式时间算法，会有什么结果？

1. ANP 中的每个问题都能在多项式时间内求解，因此 P = NP
2. B只有那一个问题会进入 P
3. C停机问题将变得可判定
4. D所有指数时间算法都会立即变成线性时间

Cook–Levin 定理确立了什么？

1. A每个 NP 问题都能在指数时间内求解
2. B布尔可满足性问题（SAT）是 NP 完全的
3. CP 不等于 NP
4. D停机问题是不可判定的