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

在包含 n 个元素的无序数组中进行线性查找（linear search）的时间复杂度（最坏情况）是多少？

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

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

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

在 n 个数的无序数组中找出最大值的时间复杂度是多少？

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

哪种排序算法是稳定的？

1. A堆排序
2. B归并排序
3. C选择排序（常见版本）
4. D快速排序（常见的原地版本）

在边权非负的图中，哪种算法用于求单源最短路径？

1. AKruskal 算法
2. B任何情况下都必须使用 Bellman–Ford
3. CDijkstra 算法
4. D深度优先搜索（DFS）

为什么许多库排序函数在子数组很小时会改用插入排序？

1. A递归算法无法处理少于 10 个元素的数组
2. B插入排序在最坏情况下是 O(n log n)
3. C插入排序开销小，在小规模或几乎有序的输入上很快
4. D在大规模输入上，插入排序比任何其他排序算法使用的内存都少

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

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

最短简单路径可以在多项式时间内求出。在一般图中求两个顶点之间的最长简单路径，已知情况如何？

1. A总能在 O(V + E) 内求解
2. B它是 NP 难的
3. C可以把权重取反后用 Dijkstra 算法求解
4. D它是不可判定的