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

在已经有序的数组上，插入排序的最好情况时间复杂度是多少？

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

平均情况运行时间描述的是什么？

1. A最好情况与最坏情况运行时间之间的中间值
2. B平均长度的输入所需的时间
3. C在最常见的计算机上所需的时间
4. D在给定的规模为 n 的输入分布上的期望时间

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

1. A9 秒
2. B12 秒
3. C3 秒
4. D6 秒

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

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

对于在满时将容量翻倍的动态数组，追加元素的均摊（amortised）时间复杂度是多少？

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

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

1. A对数级
2. B常数
3. C线性
4. D指数级

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

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

Held–Karp 动态规划算法能精确求解旅行商问题。对 n 个城市，它的运行时间是多少？

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