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

什么是递归？

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

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

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

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

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

为什么动态规划不能真正加速归并排序？

1. A归并排序没有递归结构
2. B归并排序已经是 O(n)
3. C动态规划只适用于图问题，不适用于数组
4. D它的子问题不重叠，因此没有可以复用的结果

贪心算法（greedy algorithm）：

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

Prim 算法如何构建最小生成树？

1. A运行广度优先搜索并保留 BFS 树
2. B把所有边按权重排序，逐条加入，除非会在森林中形成环
3. C从一个起始顶点开始扩展一棵树，每次加入离开该树的最便宜的边
4. D不断删除最贵的边，直到没有环为止

为什么哈希表的平均查找时间是 O(1)，而最坏情况是 O(n)？

1. A哈希函数运行很慢
2. B许多键可能冲突（collision）到同一个桶中
3. C数组的访问时间是 O(n)
4. D键必须先排序

关于在无序数组中选择第 k 小的元素，下列哪个说法是正确的？

1. A快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)
2. B选择只能在 O(n²) 内完成
3. C快速选择的最坏情况为 O(log n)，因为它只对枢轴的一侧递归
4. D选择总是需要 Ω(n log n)，因为必须先排序