目标

• 独立辨析并查集中的核心概念、结构性质与算法关系；
• 对选择题写出排除干扰项的依据，而不只记忆答案字母；
• 对本组已有的综合题完成推导、算法设计或复杂度分析。

前置知识

建议先阅读5.4 并查集，再开始本组练习。

环境、输入与预期输出

• 环境：任意现代浏览器；综合题建议准备纸笔或本地编辑器。
• 输入：9 道四选一选择题，0 道综合题。
• 预期输出：一份独立作答记录，以及每道错题或综合题的完整推理过程。

作答方法

1. 选择题先独立判断并记录依据，再点击“提交答案”；
2. 提交后核对正确答案和解析，做错的题使用“重新作答”；
3. 综合题先完成推导、伪代码或代码，再展开参考答案逐项核对；
4. 对易混概念主动构造反例，说明条件变化后结论是否仍成立。

选择题

答题进度已答 0/9正确 0

第 1 题

难度★★考点并查集、Union、Find、基本操作

关于并查集（Union-Find，又称不相交集合）的基本操作 Find(x) 和 Union(x, y)，下列说法正确的是( )。

请选择一个答案

AFind(x) 返回 x 所在集合的代表元（树的根）；Union(x, y) 合并 x、y 所在的两个集合

BFind(x) 检查元素 x 是否在数据结构中存在；Union(x, y) 把 x 设为 y 的父节点

CFind(x) 返回 x 在数组中的下标值；Union(x, y) 交换 x 与 y 在数组中的存储位置

D并查集所有操作均需 $O(n^2)$ 时间，因实现复杂在工程实践中通常被哈希表替代

第 2 题

难度★★★考点并查集、双亲表示法、实现

用双亲表示法实现并查集，每个元素 $i$ 存父指针 parent[i]，约定 parent[i] == i 表示 $i$ 是某集合的代表元（根）。下列说法正确的是( )。

请选择一个答案

A不需要任何辅助结构，单数组 parent[] 即可——每个 Find 必定 $O(1)$

B双亲表示法实现的并查集中，所有元素构成一棵单一树

CFind(x) 沿父指针上行直到 parent[i] == i，最坏 $O(h)$（$h$ 为树高）

D双亲表示法无法实现"判断两元素是否在同一集合"——必须用其他结构

第 3 题

难度★★★考点并查集、路径压缩、优化

路径压缩是并查集的标准优化。下列对路径压缩的描述正确的是( )。

请选择一个答案

A路径压缩是 Union 操作时进行——把被合并的小树整体高度压扁

B路径压缩是 Find 操作时进行——把从 x 到根的整条路径上所有结点都直接挂到根下

C路径压缩降低了空间使用，从 $O(n)$ 到 $O(\log n)$

D路径压缩使每次 Find 严格变成 $O(1)$ 时间

第 4 题

难度★★★★考点并查集、按秩合并、按高度合并

按秩合并（按高度合并）是并查集的另一种标准优化。下列描述正确的是( )。

请选择一个答案

A按秩合并是 Find 时做的优化，与路径压缩本质相同

B按秩合并要为每个元素额外维护一个"集合大小"字段

C按秩合并是 Union 时做的优化——让矮的树挂到高的树根下，使合并后高度尽量不增加

D按秩合并使所有 Find 操作严格 $O(1)$

第 5 题

难度★★★★考点并查集、连通分量、应用

给定一个无向图 $G=(V,E)$，$|V|=10$、$|E|=7$（边集为 $\{(1,2),(2,3),(4,5),(5,6),(7,8),(8,9),(9,10)\}$）。用并查集计算 $G$ 中连通分量个数。

type: undirected
nodes:
  v1 @ (0, 0)
  v2 @ (1, 0)
  v3 @ (2, 0)
  v4 @ (0, 1)
  v5 @ (1, 1)
  v6 @ (2, 1)
  v7 @ (0, 2)
  v8 @ (1, 2)
  v9 @ (2, 2)
  v10 @ (3, 2)
edges:
  v1 -> v2
  v2 -> v3
  v4 -> v5
  v5 -> v6
  v7 -> v8
  v8 -> v9
  v9 -> v10

注：节点标签 v1 ~ v10 即题面 1 ~ 10；图中只画了 7 条边、3 条互不相连的链状分量。

请选择一个答案

A2

B3

C4

D7

第 6 题

难度★★★★★考点并查集、综合、性质

关于并查集，下列说法正确的是( )。

① 并查集核心采用双亲表示法——每个元素至少维护一个父指针（或父下标）。 ② 未优化的并查集中，最坏情况下 Find 单次操作复杂度 $O(n)$。 ③ 路径压缩在 Find 时做；按秩合并在 Union 时做——两者可独立或合用。 ④ 路径压缩 + 按秩合并后，任何 $m$ 次操作的总复杂度严格为 $O(m)$。

请选择一个答案

A①②

B①②③

C①②③④

D②③④

第 7 题

难度★★★★考点并查集、路径压缩、双亲表示法、手工模拟

有一个并查集，元素编号为 $1\sim 8$。初始时每个元素各自构成一个集合，每个元素的双亲都是自己，即 parent[i] = i。操作规则如下：

• find(x)：查找元素 $x$ 所在集合的根结点，并在查找过程中进行路径压缩（把路径上经过的每个结点直接挂到根下）。
• union(x, y)：先分别用 find 查找 $x$ 和 $y$ 所在集合的根结点，记为 $r_x$ 和 $r_y$。若 $r_x\ne r_y$，则把 $y$ 所在集合的根 $r_y$ 挂到 $x$ 所在集合的根 $r_x$ 下面。

现依次执行操作序列：

$$\mathtt{\text{union(1,2)}},\mathtt{\text{union(3,4)}},\mathtt{\text{union(2,4)}},\mathtt{\text{union(5,6)}},\mathtt{\text{union(7,8)}},\mathtt{\text{union(6,8)}},\mathtt{\text{union(4,8)}}$$

则对该并查集的说法正确的是（ ）。

请选择一个答案

Aparent[8] = 1

Bparent[4] = 3

Cfind(8) = 7

Dfind(6) = 1

第 8 题

难度★★★考点并查集、路径压缩、按规模合并、判环、Find操作

下列关于并查集的说法中，正确的是（ ）。

请选择一个答案

A并查集不能检测图中是否存在环路的问题

B通过路径优化后的并查集在最坏情况下的高度仍是 $O(n)$

CFind 操作返回集合中元素个数的相反数，它用来作为某个集合的标志

DUnion 操作时可根据当前集合的规模，将小集合合并到大集合中

第 9 题

难度★★考点并查集、Kruskal算法、最小生成树、判环、图算法

在以下算法中，需要用到并查集的是（ ）。

请选择一个答案

AKruskal 算法

BPrim 算法

CFloyd 算法

DDijkstra 算法

答案总览（建议完成全部题目后查看）

1. 第 1 题：A
2. 第 2 题：C
3. 第 3 题：B
4. 第 4 题：C
5. 第 5 题：B
6. 第 6 题：B
7. 第 7 题：D
8. 第 8 题：D
9. 第 9 题：A

综合题

本组素材未提供综合题，因此不补造占位题。

完成清单

• 9 道选择题均已独立作答，错题能说明其余选项为何不成立；
• 能把本组题目涉及的关键性质、操作过程或算法复杂度说清楚；
• 已记录仍需回到教材复习的知识点。

复盘

• 哪道题最容易因结构关系、边界口径或算法步骤判断失误？
• 我能否不用背答案，重新画出结构或写出关键操作过程？
• 如果题目改变一个条件，原结论是否仍成立？