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

归并排序采用哪种设计策略？

1. A蛮力法
2. B分治法（divide and conquer）
3. C动态规划
4. D贪心选择

算法的最坏情况运行时间描述的是什么？

1. A在规模为 n 的随机输入上所需的期望时间
2. B在慢速计算机上所需的时间
3. C在所有规模为 n 的输入上所需的最长时间
4. D在最小输入上所需的时间

一个算法的运行时间是 O(n)。这种增长称为什么？

1. A常数
2. B对数
3. C平方
4. D线性

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

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

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

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

在有 V 个顶点、E 条边的图上，Bellman–Ford 算法的时间复杂度是多少？

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

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

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

Cook–Levin 定理确立了什么？

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