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

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

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

什么是递归？

1. A在更小的输入上调用自身的函数
2. B永远不会结束的循环
3. C一种数据结构
4. D一种排序方法

算法的最坏情况运行时间描述的是什么？

1. A在所有规模为 n 的输入上所需的最长时间
2. B在规模为 n 的随机输入上所需的期望时间
3. C在最小输入上所需的时间
4. D在慢速计算机上所需的时间

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

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

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

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

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

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

Bellman–Ford 算法如何检测从源点可达的负权环？

1. A在 V − 1 轮之后，检查是否还有边可以被松弛
2. B用深度优先搜索统计环的数量
3. C检查是否有边的权重为负
4. D它运行两次 Dijkstra 算法，并比较两次的距离结果

Strassen 算法在矩阵乘法中对半尺寸的分块只做 7 次而不是 8 次递归乘法。它的运行时间是多少？

1. AΘ(n² log n)
2. BΘ(n^{log₂ 7})，约为 n^2.81
3. CΘ(n²)
4. DΘ(n³)