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

什么是记忆化（memoisation）？

1. A函数返回后释放内存
2. B存储函数调用的结果，使重复调用能直接从内存中得到答案
3. C在每行代码旁边写注释
4. D自动把递归转换为等价的循环，从而不需要调用栈

递归函数的基本情况是什么？

1. A无需再进行递归调用就能直接给出答案的情况
2. B使用内存最多的那次调用
3. C输入最大的情况，它在任何递归调用之前就被处理
4. D函数的第一行

通过下标访问数组中的元素需要：

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

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

1. A长度为 2 的数组
2. B所有元素都不相同的数组
3. C随机顺序的数组
4. D已经有序的数组

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

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

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

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

关于 log(n!)，哪个界是正确的？

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

关于类 P 的哪个定义是正确的？

1. A能够并行求解的问题
2. B其解可以被验证、但绝不能在多项式时间内找到的问题
3. C在每台计算机上都需要指数时间的问题
4. D能由确定性算法在多项式时间内求解的判定问题