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

一个包含两层嵌套循环、每层都执行 n 次的算法，通常具有哪种复杂度？

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

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

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

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

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

一个函数先运行一个 n 次迭代的循环，然后再单独运行另一个 n 次迭代的循环。它的时间复杂度是多少？

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

均摊分析衡量的是什么？

1. A算法在最好输入上的代价
2. B在随机输入上的期望代价
3. C在最坏情况的操作序列上，每个操作的平均代价
4. D序列中任何位置上单个最昂贵操作的代价

哪种排序算法是稳定的？

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

下面代码的时间复杂度是多少：for i = 1 to n: for (j = i; j ≤ n; j = j + i) 执行 O(1) 的工作？

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

停机问题（halting problem）表明：

1. A每个程序最终都会停机
2. B应当避免使用循环
3. C有些程序在更快的计算机上运行得更快，所以是否停机取决于硬件
4. D不存在一种算法能对所有程序和输入判定其是否会停机