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

空间复杂度衡量的是：

1. A代码的行数
2. B随着输入增大，算法所需的内存量
3. C程序编译后程序文件占用的磁盘空间
4. D计算机的物理尺寸

通过下标访问数组中的元素需要：

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

下列哪个运行时间是多项式的？

1. AO(2ⁿ)
2. BO(n!)
3. CO(n³)
4. DO(nⁿ)

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

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

你对一个 n 个元素的数组排序一次，然后用二分查找回答 k 次成员查询。总代价是多少？

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

递推式 T(n) = 2T(n/2) + O(n) 的解是：

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

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

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

拓扑排序只适用于：

1. A无向图
2. B带负权重的图
3. C有向无环图（DAG）
4. D完全图