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

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

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

在有序数组上进行二分查找（binary search）的时间复杂度是多少？

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

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

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

哪种排序算法是稳定的？

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

关于一个没有可达基本情况的递归函数，下列哪个说法是正确的？

1. A它会不断调用自身，直到调用栈溢出
2. B它会自动返回 0
3. C它的运行时间为 O(1)
4. D编译器总会把它变成能安全结束的循环

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

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

使用主定理，T(n) = 8T(n/2) + O(n²) 的解是：

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n² log n)
4. DΘ(n²)

当 n 很大时，n! 与 2ⁿ 相比如何？

1. An! 是 O(n²)
2. B2ⁿ 比 n! 增长得快
3. Cn! 比 2ⁿ 增长得快
4. D两者以相同的速率增长