🏷️ 知识点：Ds.05.05.02
并查集的结构是一种（ ）。
A. 二叉链表存储的二叉树 B. 双亲表示法存储的树 C. 顺序存储的二叉树 D. 孩子表示法存储的树
[tag_link]
正确答案：B
推导
并查集用一组双亲指针树表示互不相交的集合；每棵树的根是集合代表，故选 B。
易错点
数组是存储载体，数组元素表达的是双亲关系；不能因此误选‘顺序存储的二叉树’。
初始有 10 个单元素集合（0～9），依次对 1-2、3-4、5-6、7-8、8-9、1-8、0-5、1-9 执行查找与合并，最终并查集中有多少个集合？
A. 1 B. 2 C. 3 D. 4
[tag_link]
正确答案：C
推导
有效合并后得到 {0,5,6}、{1,2,7,8,9}、{3,4} 三个集合；最后一次 1-9 的两元素已同集，不再减少集合数，故选 C。
易错点
只有两个根不同时 Union 才使集合数减 1；不能把每条操作都机械计为一次有效合并。
下列关于并查集的说法中，正确的是（ ）（注：本题涉及图的考点）。
A. 并查集不能检测图中是否存在环路 B. 通过路径优化后的并查集在最坏情况下的高度仍是 O(n) C. Find 操作返回集合中元素个数的相反数，它用来作为某个集合的标志 D. Union 操作时可根据当前集合的规模，将小集合合并到大集合中
[tag_link]
正确答案：D
推导
D 是按规模合并：把较小树的根挂到较大树的根下。A 错在并查集可判无向图加边是否成环；B 忽略路径压缩；C 错在 Find 返回代表元（根），根位置的负值才可记录规模。
易错点
要区分 Find 的返回值与 parent[root] 的负值语义；二者不是同一概念。
下列关于并查集的叙述中，错误的是（ ）（注：本题涉及图的考点）。
A. 并查集是用双亲表示法存储的树 B. 并查集可用于实现克鲁斯卡尔算法 C. 并查集可用于判断无向图的连通性 D. 在长度为 n 的并查集中进行查找操作的时间复杂度为 O(log₂n)
[tag_link]
正确答案：D
推导
A、B、C 均正确。D 把实现无条件写成 O(log n)：朴素 Find 最坏可为 O(n)，按规模并配合路径压缩时均摊为 O(α(n))，故选 D。
易错点
复杂度必须绑定实现策略；不能把按规模合并的树高上界直接当作所有 Find 的固定复杂度。