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

标准的基于数组的归并排序使用多少额外内存？

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

O(2ⁿ) 的增长称为什么？

1. A线性
2. B对数级
3. C多项式级
4. D指数级

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

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

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

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

为什么在 Big O 中通常省略对数的底，例如写成 O(log n)？

1. A不同底的对数之间只相差一个常数因子
2. B底只在 n 很小时才有影响
3. C计算机科学中所有对数的底都是 10，所以可以省略
4. D对数总是被四舍五入为整数

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

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

为什么当某些边权为负时，Dijkstra 算法可能给出错误结果？

1. A顶点被取出时距离就被确定，但之后的负权边仍可能给它一条更短的路径
2. B每遇到一条负权边它就会陷入无限循环
3. C它只适用于无向图
4. D优先队列中不能存储负数

在有 V 个顶点、E 条边的图上，使用二叉堆的 Dijkstra 算法运行时间是多少？

1. AO(V³)
2. BO(V × E)
3. CO((V + E) log V)
4. DO(V + E)