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

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

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

哪种排序算法会反复交换顺序错误的相邻元素？

1. A快速排序（Quicksort）
2. B冒泡排序（Bubble sort）
3. C堆排序（Heap sort）
4. D归并排序（Merge sort）

对范围在 0 到 k 之间的 n 个整数进行计数排序（counting sort），运行时间是多少？

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

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

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

用标准的三重循环计算两个 n × n 矩阵的乘积，时间复杂度是多少？

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

在无权图上进行广度优先搜索（BFS）可以求出：

1. A所有图的拓扑序
2. B含负权重边的图中的最短路径
3. C最小生成树
4. D从起始节点出发、按边数计的最短路径

Cook–Levin 定理确立了什么？

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

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

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