2020 年信奥赛 C++ 提高组 CSP-S 初赛真题解析（选择题 6-10）

2020 年信奥赛 C++ 提高组 CSP-S 初赛真题解析（选择题 6-10）

**第 6 题：**下列哪些问题不能用贪心法精确求解？（ ）

A. 霍夫曼编码问题

B. 0-1 背包问题

C. 最小生成树问题

D. 单源最短路径问题

答案：B

解析：贪心法适用于具有最优子结构和贪心选择性质的问题。霍夫曼编码、最小生成树、单源最短路径（非负权）均可用贪心精确求解，而 0-1 背包问题贪心无法保证最优解。

---

第 7 题：具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。

A. O(n+e)

B. O(n^2)