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

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

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

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

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

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

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

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

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

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

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

递推式 T(n) = T(n/2) + O(1) 的解是什么？

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

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

1. A矛盾，因此这个下界是错的
2. B不矛盾，因为插入排序不是比较排序
3. C矛盾，但仅对长度小于 100 的数组
4. D不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入

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

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