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

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

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

在以邻接表存储的图上进行深度优先搜索，时间复杂度是多少？

1. AO(V²)
2. BO(V × E)
3. CO(V + E)
4. DO(E log V)

f(n) = Θ(g(n)) 是什么意思？

1. A对每个 n，f 总是小于 g，因此 g 是它的上界，但绝不是下界
2. Bf 的增长严格快于 g
3. Cf 的增长严格慢于 g
4. Df 与 g 以相同的速率增长，上下都被 g 的常数倍所界定

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

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

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

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

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

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

为什么在单链表上二分查找不能达到 O(log n) 的时间？

1. A二分查找至少需要两倍的内存
2. B链表节点上的比较更慢
3. C链表无法排序
4. D由于不能按下标直接访问，到达中间元素需要 O(n) 步

Cook–Levin 定理确立了什么？

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