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

一个循环从 i = 1 开始，每次迭代将 i 翻倍，直到 i > n。它运行多少次迭代？

1. A约 n / 2 次
2. B约 n² 次
3. C约 log₂ n 次
4. D约 n 次

下列哪个运行时间是多项式的？

1. AO(nⁿ)
2. BO(n³)
3. CO(2ⁿ)
4. DO(n!)

如果一个操作的运行时间是 O(1)，这意味着什么？

1. A它只能运行一次
2. B它每秒运行时间恰好处理一个元素
3. C它的运行时间不随输入规模增长
4. D它总是恰好花费一秒

Floyd–Warshall 算法计算什么？速度如何？

1. A以 O(V²) 计算拓扑序
2. B以 O(V + E) 计算从一个源顶点到所有其他顶点的最短路径
3. C以 O(V³) 计算所有顶点对之间的最短路径
4. D以 O(E log V) 计算最小生成树

下面代码的时间复杂度是多少：for i = 1 to n: (j = 1; while j < n: j = j × 2)？

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

对于在满时将容量翻倍的动态数组，追加元素的均摊（amortised）时间复杂度是多少？

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

为什么在单链表上二分查找不能达到 O(log n) 的时间？

1. A链表无法排序
2. B二分查找至少需要两倍的内存
3. C由于不能按下标直接访问，到达中间元素需要 O(n) 步
4. D链表节点上的比较更慢

用动态规划求解 0/1 背包问题需要 O(nW) 时间。为什么称之为伪多项式（pseudo-polynomial）？

1. AW 是一个数值，因此运行时间相对于表示 W 所需的位数是指数级的
2. B因为它只适用于 W = 0
3. C因为 n 总是很小
4. D因为该算法是随机化的，其运行时间随每个输入而变化