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

空间复杂度衡量的是：

1. A程序编译后程序文件占用的磁盘空间
2. B随着输入增大，算法所需的内存量
3. C计算机的物理尺寸
4. D代码的行数

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

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

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

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

对长度为 m 和 n 的两个字符串求最长公共子序列，标准动态规划算法的时间复杂度是多少？

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

你对一个 n 个元素的数组排序一次，然后用二分查找回答 k 次成员查询。总代价是多少？

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

哪种排序算法是稳定的？

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

Cook–Levin 定理确立了什么？

1. A停机问题是不可判定的
2. B每个 NP 问题都能在指数时间内求解
3. CP 不等于 NP
4. D布尔可满足性问题（SAT）是 NP 完全的

下面代码的时间复杂度是多少：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²)