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

哪种排序算法选择一个基准，并把数组划分为较小元素和较大元素两部分？

1. A插入排序
2. B快速排序
3. C归并排序
4. D冒泡排序

选择排序（selection sort）是如何工作的？

1. A通过移动元素，把每个元素插入到不断增长的有序部分中
2. B把数组对半分开再合并
3. C反复找出未排序部分的最小值，并把它交换到前面
4. D反复交换顺序错误的相邻元素

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

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

对 n 个元素的数组进行归并排序，递归共有多少层？

1. A约 n / 2 层
2. B约 √n 层
3. C约 n 层
4. D约 log₂ n 层

均摊分析衡量的是什么？

1. A算法在最好输入上的代价
2. B在最坏情况的操作序列上，每个操作的平均代价
3. C序列中任何位置上单个最昂贵操作的代价
4. D在随机输入上的期望代价

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

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

为什么在有序数组中任何基于比较的查找在最坏情况下都需要 Ω(log n) 次比较？

1. A每个元素都必须至少比较一次
2. B二分查找是唯一可能的算法，它需要 log₂ n 次比较
3. C每次比较都需要对数时间
4. D有 n 种可能结果的决策树，其深度至少为 log₂ n

Bellman–Ford 算法如何检测从源点可达的负权环？

1. A在 V − 1 轮之后，检查是否还有边可以被松弛
2. B它运行两次 Dijkstra 算法，并比较两次的距离结果
3. C检查是否有边的权重为负
4. D用深度优先搜索统计环的数量