CSP 模拟 · CSP 2020 第一轮（初赛）模拟 第 6 题

对于“树”这种数据结构，正确的有： ①一个有 $n$ 个顶点、$n-1$ 条边的图是树 ②一个树中的两个顶点之间有且只有一条简单路径 ③树中一定存在度数不大于 $1$ 的顶点 ④树可能存在环

这题考的是树的定义与性质，别被‘排列组合’那套话带偏了。拿到题先想：树到底长啥样？连通、无环、n个点n-1条边，这三者等价。把四个说法逐条代入这个等价链，就能立刻看出谁对谁错。

最容易掉进两个坑：一是把‘n个点n-1条边’当成树的充分条件，忘了还要连通（比如两个分离的树加起来也满足边数公式）；二是误以为树里不能有度数≤1的点，其实叶子节点度数就是1，根节点度数可以是0。命题人常在这里挖坑，让你选包含①或④的选项。

这道题考查的是图论中‘树’的基本定义与性质，属于数据结构与算法的基础概念，也是 CSP-J/S 等竞赛中高频出现的判断题。命题人专门挑了四个看似合理但细节不同的说法，想看看你是否真正理解树的本质，而不是死记硬背公式。

先说概念：树是一个连通且无环的无向图。对于 n 个顶点的树，它恰好有 n-1 条边，且任意两点之间有且仅有一条简单路径。这三个特征（连通、无环、边数=n-1）在 n≥2 时是等价的，但要注意 n=1 时边数为 0，依然满足。

现在逐条分析： ①‘一个有 n 个顶点、n-1 条边的图是树’——错。缺少‘连通’这个条件。比如两个分离的树，顶点数加起来是 n，边数加起来是 n-1，但整体不连通，显然不是树。命题人常在这里挖坑，让你误以为边数够就是树。 ②‘树中的两个顶点之间有且只有一条简单路径’——对。这是树最核心的性质之一，也是无环的直接体现。如果存在两条不同路径，那就构成了环，与树矛盾。 ③‘树中一定存在度数不大于 1 的顶点’——对。树至少有两个叶子节点（度数=1），除非 n=1 时根节点度数为 0。所以度数≤1 的顶点必然存在。 ④‘树可能存在环’——错。树定义就是无环，一旦有环就不是树了。

因此正确的是②和③，对应选项 C。

避坑指南：审题时要警惕‘充分条件’与‘必要条件’的混淆。①中边数 n-1 是树的必要条件，但不是充分条件；④中‘可能’二字极具迷惑性，树不可能有环，所以④必错。另外，不要受‘排列组合’思维定势影响，这题纯靠概念辨析就能解决，无需计算。

考频与趋势：根据历年真题统计，树的定义与性质（连通、无环、边数关系、叶子节点）在 CSP-J/S 中属于高频考点，近五年在单选题和判断题中平均每年出现 1-2 次，尤其在涉及图遍历（DFS/BFS）或树形 DP 的题目前常作为基础概念题出现。该知识点自 2018 年以来考频稳定，未见明显下降。

预测：基于现有数据与命题风格，未来几年树的基本性质仍将是必考内容，命题人可能会在更复杂的图算法题中隐式考查这些定义，或通过‘非树图’的判定来反向测试。暂无足够依据预测具体题型变化，但建议务必牢固掌握上述四个说法的正误逻辑，这是解题的基石。