第 29 章 并查集与字典树 · 知识细节练习

并查集（Union-Find / 不相交集）主要解决？

并查集的两个基本操作是？

并查集的常见实现是？

带路径压缩与按秩合并的并查集，单次操作复杂度是？

并查集的典型应用是？

判断题：并查集与线段树/树状数组解决的问题完全不同——并查集管"集合关系"、后两者管"区间信息"。

find(x) 的作用是？

判断题：朴素 find 沿父链一路向上——若树退化成链（1→2→3→…→n），find(1) 要 $O(n)$ 步。

路径压缩的递归版 find 是？

判断题：路径压缩也可写成迭代——先找到根、再让沿途节点全部指向根（两次遍历）。

判断题：路径压缩把树压扁——find 一次后，路径上所有节点的父都直接是根，后续 find 接近 $O(1)$。

判断题：路径压缩递归版的关键细节是赋值——fa[x] = find(fa[x]) 把返回的根写回 fa[x]。

判断题：find 的返回值恒是"代表元"——同一集合内所有元素 find 结果相同。

union(x, y) 的作用是？

union 的标准写法是？

按秩合并（union by rank）是？

按大小合并（union by size）是？

判断题：按秩/按大小合并保证树高 $O(\log n)$——每次挂接后树高至多加 1，且小树挂大树不增加大树的秩。

判断题：路径压缩 + 按秩合并双优化后，$m$ 次操作总复杂度 $O(m \cdot \alpha(n))$——反阿克曼函数增长极慢，实际视为常数。

判断题：union 前先 find 两元素——已在同一集合则无需合并（也防止自环）。

用并查集判定两节点是否连通，做法是？

判断题：连通块数 = 合并完成后"根是自身"的节点数——每次有效 union 使块数减 1。

无向图判环的并查集做法是？

Kruskal 最小生成树中并查集的作用是？

判断题：Kruskal = 边排序 + 并查集判环——并查集是 Kruskal 正确性的关键组件。

判断题：并查集还用于——亲戚关系、等价类合并、区间染色（反向并查集）、食物链（带权并查集）。

判断题：并查集的核心价值 = 高效维护"同一组"关系——一切"合并+查同组"的问题都适用。

字典树（Trie）的定义是？

Trie 主要解决？

Trie 的节点通常包含？

Trie 插入/查询长度为 $L$ 的字符串的复杂度是？

Trie 与哈希表的正确对比是？

Trie 的典型应用是？

Trie 插入字符串的过程是？

判断题：查询完整单词 = 逐字符走边，全部走通且末节点有结束标记才算存在。

判断题：前缀查询 = 逐字符走边，全部走通即"存在以该前缀开头的单词"（不需要结束标记）。

判断题：Trie 删除单词 = 找到末节点去掉结束标记；若整条路径无其他单词可回收节点。

判断题：Trie 节点存"经过次数"计数——插入时路径上所有节点计数 +1，可统计"以某前缀开头的单词数"。

判断题：Trie 三大操作 = 插入、查询、前缀统计——都沿"逐字符走边"的同一框架。

判断题：并查集与线段树/树状数组/Trie 解决的问题正交——按"集合关系/区间信息/字符串前缀"三分类选结构。

需要"统计以 'ab' 为前缀的单词数"，选？

判断题：选择矩阵——同组关系用并查集、前缀查询用 Trie、精确查找用哈希、区间信息用线段树系。

判断题：复杂度总表——并查集近 $O(1)$、Trie $O(L)$（L 为串长）、哈希平均 $O(1)$——各擅胜场。

判断题：并查集空间 $O(n)$、Trie 空间 $O(总字符数 \times 字符集)$——Trie 空间消耗大是其主要缺点。

需要"动态合并集合 + 查询同组"，选？

判断题：只写 return fa[x] 的 find（无压缩）在链状退化时单次 $O(n)$——大量操作会超时。

判断题：union 不做按秩合并，最坏树高可达 $O(n)$——即使有路径压缩也不如双优化稳定。

判断题：Trie 用"子节点下标 0 表示空"时，节点编号从 1 开始——0 号留作空标志，混用会误判。

判断题：并查集使用前必须初始化 fa[i] = i——忘初始化导致所有 find 结果错乱。

判断题：以下结论全部正确——"find 带路径压缩；union 按秩合并防退化；并查集初始化 fa[i]=i；Trie 逐字符走边、0 下标作空标志；前缀查询不需结束标记"。

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6] = {0, 2, 3, 4, 5, 5};   // 链：1→2→3→4→5
04int find(int x) {
05    while (fa[x] != x) x = fa[x];  // 朴素 find（无压缩）
06    return x;
07}
08int main() {
09    cout << find(1);
10    return 0;
11}

单选题：程序输出是？（元素 1 所在集合的根）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6] = {0, 2, 3, 4, 5, 5};
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);   // 路径压缩
06}
07int main() {
08    find(1);
09    cout << fa[1] << " " << fa[2] << " " << fa[3] << " " << fa[4];
10    return 0;
11}

单选题：程序输出是？（find(1) 后沿途节点的父节点——全部被压到根）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6] = {0, 2, 3, 4, 5, 5};
04int find(int x) {
05    int steps = 0;
06    while (fa[x] != x) { x = fa[x]; steps++; }
07    return steps;
08}
09int main() {
10    cout << find(1);
11    return 0;
12}

单选题：程序输出是？（链 1→2→3→4→5 中 find(1) 的步数）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6] = {0, 2, 3, 4, 5, 5};
04int find(int x) {
05    return ______;               // 路径压缩递归版
06}
07int main() {
08    find(1);
09    cout << fa[1];
10    return 0;
11}

单选题：横线处应填入？（使输出为 5）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6] = {0, 2, 3, 4, 5, 5};
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    find(1);
09    int steps = 0, x = 1;
10    while (fa[x] != x) { x = fa[x]; steps++; }   // 压缩后再次 find(1) 的步数
11    cout << steps;
12    return 0;
13}

单选题：程序输出是？（路径压缩后 find(1) 只需 1 步）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[7] = {0, 1, 1, 2, 3, 4, 6};   // 1←2←3←4←5、6 独立
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    find(5);
09    cout << find(1) << " " << find(5) << " " << find(6);
10    return 0;
11}

单选题：程序输出是？（三个集合的代表元）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) fa[i] = i;
09    fa[find(1)] = find(2);     // union(1,2)
10    fa[find(2)] = find(3);     // union(2,3)
11    cout << find(1) << " " << find(3);
12    return 0;
13}

单选题：程序输出是？（合并后 1 与 3 是否同集合）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6], rk[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07void uni(int x, int y) {
08    int rx = find(x), ry = find(y);
09    if (rx == ry) return;
10    if (rk[rx] < rk[ry]) fa[rx] = ry;      // 矮挂高
11    else if (rk[rx] > rk[ry]) fa[ry] = rx;
12    else { fa[rx] = ry; rk[ry]++; }        // 等高时挂后秩 +1
13}
14int main() {
15    for (int i = 1; i <= 4; i++) { fa[i] = i; rk[i] = 0; }
16    uni(1, 2); uni(3, 4); uni(1, 3);
17    cout << find(1) << " " << find(4);
18    return 0;
19}

单选题：程序输出是？（按秩合并：uni(1,2) 后 1 挂 2；uni(3,4) 后 3 挂 4；uni(1,3) 时两树等高 → 2 挂 4）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6], sz[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07void uni(int x, int y) {
08    int rx = find(x), ry = find(y);
09    if (rx == ry) return;
10    if (sz[rx] < sz[ry]) swap(rx, ry);     // 小挂大
11    fa[ry] = rx; sz[rx] += sz[ry];
12}
13int main() {
14    for (int i = 1; i <= 5; i++) { fa[i] = i; sz[i] = 1; }
15    uni(1, 2); uni(3, 4); uni(1, 3);
16    cout << sz[find(1)];
17    return 0;
18}

单选题：程序输出是？（合并后集合 {1,2,3,4} 的大小）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) fa[i] = i;
09    ______;                     // union(1, 3)：把 1 的根挂到 3 的根
10    cout << find(1) << " " << find(3);
11    return 0;
12}

单选题：横线处应填入？（使输出为 3 3）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) fa[i] = i;
09    fa[find(2)] = find(1);     // 2 挂到 1
10    fa[find(3)] = find(1);     // 3 挂到 1
11    fa[find(4)] = find(2);     // 4 挂到 2
12    cout << fa[2] << " " << fa[3] << " " << fa[4];
13    return 0;
14}

单选题：程序输出是？（2、3 挂 1；4 挂到 find(2)——此时 2 已挂 1，故 4 也挂 1）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) fa[i] = i;
09    fa[find(1)] = find(2);
10    fa[find(2)] = find(3);
11    fa[find(4)] = find(5);
12    fa[find(5)] = find(3);     // 合并两个集合
13    int cnt = 0;
14    for (int i = 1; i <= 5; i++) if (find(i) == i) cnt++;
15    cout << cnt;
16    return 0;
17}

单选题：程序输出是？（最终连通块数）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) fa[i] = i;
09    fa[find(1)] = find(2);
10    fa[find(3)] = find(4);
11    cout << (find(1) == find(3) ? "CONNECTED" : "NOT-CONNECTED");
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int fa[7];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 6; i++) fa[i] = i;
09    fa[find(1)] = find(2);    // {1,2}
10    fa[find(3)] = find(4);    // {3,4}
11    fa[find(5)] = find(6);    // {5,6}
12    int cnt = 0;
13    for (int i = 1; i <= 6; i++) if (find(i) == i) cnt++;
14    cout << cnt;
15    return 0;
16}

单选题：程序输出是？（6 个元素分成 3 组后的连通块数）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[4];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 3; i++) fa[i] = i;
09    bool cycle = false;
10    int e[3][2] = {{1, 2}, {2, 3}, {1, 3}};   // 三条边
11    for (int i = 0; i < 3; i++) {
12        int x = e[i][0], y = e[i][1];
13        if (find(x) == find(y)) cycle = true;
14        else fa[find(x)] = find(y);
15    }
16    cout << (cycle ? "CYCLE" : "NO-CYCLE");
17    return 0;
18}

单选题：程序输出是？（三角形三边成环）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) fa[i] = i;
09    // 亲戚关系：1 与 2、2 与 3、4 与 5 是亲戚
10    fa[find(1)] = find(2);
11    fa[find(2)] = find(3);
12    fa[find(4)] = find(5);
13    cout << (find(1) == find(3) ? "YES" : "NO") << " "
14         << (find(3) == find(5) ? "YES" : "NO");
15    return 0;
16}

单选题：程序输出是？（1 与 3 是亲戚、3 与 5 不是）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[5];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 4; i++) fa[i] = i;
09    // 边按权升序：(1,2,1) (3,4,1) (2,3,2) (1,3,5)
10    int edges[4][3] = {{1, 2, 1}, {3, 4, 1}, {2, 3, 2}, {1, 3, 5}};
11    int cost = 0, taken = 0;
12    for (int i = 0; i < 4; i++) {
13        int x = edges[i][0], y = edges[i][1], w = edges[i][2];
14        if (find(x) != find(y)) {
15            fa[find(x)] = find(y);
16            cost += w; taken++;
17        }
18    }
19    cout << cost << " " << taken;
20    return 0;
21}

单选题：程序输出是？（Kruskal 最小生成树的总权与边数）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) fa[i] = i;
09    fa[find(1)] = find(2);
10    cout << (______ ? "SAME" : "DIFF");   // 判 1、2 同集合
11    return 0;
12}

单选题：横线处应填入？（使输出为 SAME）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[7];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 6; i++) fa[i] = i;
09    // 边：(1,2) (2,3) (4,5) —— 3 个连通块 {1,2,3}、{4,5}、{6}
10    fa[find(1)] = find(2);
11    fa[find(2)] = find(3);
12    fa[find(4)] = find(5);
13    int blocks = 0;
14    for (int i = 1; i <= 6; i++) if (find(i) == i) blocks++;
15    cout << blocks;
16    return 0;
17}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];    // 子节点（0 = 空）
04int cnt[100];       // 经过次数
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;   // 新建节点
11        p = ch[p][t];
12        cnt[p]++;
13    }
14}
15int main() {
16    ins("cat"); ins("car"); ins("dog");
17    cout << tot;
18    return 0;
19}

单选题：程序输出是？（cat 新建 3 节点、car 新建 1 节点（r）、dog 新建 3 节点）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04int cnt[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12        cnt[p]++;
13    }
14}
15int main() {
16    ins("cat"); ins("car");
17    cout << cnt[ch[0]['c' - 'a']];   // 根下 'c' 节点的经过次数
18    return 0;
19}

单选题：程序输出是？（以 'c' 开头的单词数）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04bool isEnd[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12    }
13    isEnd[p] = true;
14}
15bool query(string s) {
16    int p = 0;
17    for (char c : s) {
18        int t = c - 'a';
19        if (!ch[p][t]) return false;
20        p = ch[p][t];
21    }
22    return isEnd[p];
23}
24int main() {
25    ins("cat"); ins("car"); ins("dog");
26    cout << (query("cat") ? "Y" : "N") << (query("ca") ? "Y" : "N")
27         << (query("cow") ? "Y" : "N");
28    return 0;
29}

单选题：程序输出是？（cat 存在、ca 不是完整单词、cow 不存在）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04int cnt[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12        cnt[p]++;
13    }
14}
15int pref(string s) {
16    int p = 0;
17    for (char c : s) {
18        int t = c - 'a';
19        if (!ch[p][t]) return 0;
20        p = ch[p][t];
21    }
22    return cnt[p];
23}
24int main() {
25    ins("cat"); ins("car"); ins("dog"); ins("do");
26    cout << pref("do");
27    return 0;
28}

单选题：程序输出是？（以 "do" 为前缀的单词数：dog、do 共 2 个）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04int cnt[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        ______;                  // 移动到子节点
12        cnt[p]++;
13    }
14}
15int main() {
16    ins("ab");
17    cout << tot;
18    return 0;
19}

单选题：横线处应填入？（使输出为 2）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04bool isEnd[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12    }
13    isEnd[p] = true;
14}
15bool query(string s) {
16    int p = 0;
17    for (char c : s) {
18        int t = c - 'a';
19        if (!ch[p][t]) return false;
20        p = ch[p][t];
21    }
22    return isEnd[p];
23}
24int main() {
25    ins("a"); ins("ab"); ins("abc");
26    cout << (query("a") ? "Y" : "N") << (query("ab") ? "Y" : "N")
27         << (query("abc") ? "Y" : "N") << (query("abcd") ? "Y" : "N");
28    return 0;
29}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04bool isEnd[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12    }
13    isEnd[p] = true;
14}
15bool query(string s) {
16    int p = 0;
17    for (char c : s) {
18        int t = c - 'a';
19        if (!ch[p][t]) return false;
20        p = ch[p][t];
21    }
22    return isEnd[p];
23}
24int main() {
25    string words[4] = {"the", "a", "there", "answer"};
26    for (string w : words) ins(w);
27    cout << (query("there") ? "FOUND" : "NOT-FOUND");
28    return 0;
29}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04int cnt[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12        cnt[p]++;
13    }
14}
15int pref(string s) {
16    int p = 0;
17    for (char c : s) {
18        int t = c - 'a';
19        if (!ch[p][t]) return 0;
20        p = ch[p][t];
21    }
22    return cnt[p];
23}
24int main() {
25    string words[5] = {"app", "apple", "apply", "banana", "apex"};
26    for (string w : words) ins(w);
27    cout << pref("app");
28    return 0;
29}

单选题：程序输出是？（以 "app" 为前缀的单词数：app、apple、apply 共 3 个）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 最大异或对：对每个数在 01-Trie 上贪心走"相反位"路径
05    int a[3] = {3, 5, 6};
06    int mx = 0;
07    for (int i = 0; i < 3; i++)
08        for (int j = i + 1; j < 3; j++)
09            mx = max(mx, a[i] ^ a[j]);
10    cout << mx;
11    return 0;
12}

单选题：程序输出是？（3^5=6、3^6=5、5^6=3，最大 6）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string words[3] = {"banana", "apple", "apricot"};
05    sort(words, words + 3);
06    for (string w : words) cout << w << " ";
07    return 0;
08}

单选题：程序输出是？（字典序——Trie 深度优先遍历天然得到此序）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04bool isEnd[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12    }
13    ______;                  // 标记单词结束
14}
15int main() {
16    ins("hi");
17    cout << isEnd[2];
18    return 0;
19}

单选题：横线处应填入？（使输出为 1）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04int cnt[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12        cnt[p]++;
13    }
14}
15int main() {
16    string words[4] = {"ab", "abc", "abd", "ac"};
17    for (string w : words) ins(w);
18    // 统计以 'a' 开头的单词数 = 根下 'a' 节点的 cnt
19    cout << cnt[ch[0]['a' - 'a']];
20    return 0;
21}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int fa[5];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 4; i++) fa[i] = i;
09    // 四边形加一条对角线：(1,2) (2,3) (3,4) (4,1) —— 第 4 条边成环
10    int e[4][2] = {{1, 2}, {2, 3}, {3, 4}, {4, 1}};
11    int cycleAt = 0;
12    for (int i = 0; i < 4; i++) {
13        int x = e[i][0], y = e[i][1];
14        if (find(x) == find(y)) { cycleAt = i + 1; break; }
15        fa[find(x)] = find(y);
16    }
17    cout << cycleAt;
18    return 0;
19}

单选题：程序输出是？（第几条边发现成环）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04int cnt[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12        cnt[p]++;
13    }
14}
15int main() {
16    ins("abc"); ins("abc"); ins("abd");
17    cout << cnt[ch[ch[ch[0]['a' - 'a']]['b' - 'a']]['c' - 'a']];
18    return 0;
19}

单选题：程序输出是？（"abc" 路径末端节点的经过次数）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[9];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 8; i++) fa[i] = i;
09    // 4 条边连成两个块：{1,2,3,4} 与 {5,6,7,8}
10    int e[4][2] = {{1, 2}, {2, 3}, {3, 4}, {5, 6}};
11    for (int i = 0; i < 4; i++) fa[find(e[i][0])] = find(e[i][1]);
12    int blocks = 0;
13    for (int i = 1; i <= 8; i++) if (find(i) == i) blocks++;
14    cout << blocks;
15    return 0;
16}

单选题：程序输出是？（{1,2,3,4}、{5,6}、{7}、{8} 共 4 块）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) fa[i] = i;
09    // 朋友关系：1-2、3-4、4-5
10    fa[find(1)] = find(2);
11    fa[find(3)] = find(4);
12    fa[find(4)] = find(5);
13    cout << (find(2) == find(5) ? "CONNECTED" : "NOT-CONNECTED");
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) ______;   // 初始化
09    cout << find(5);
10    return 0;
11}

单选题：横线处应填入？（使输出为 5）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[7], rk[7];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07void uni(int x, int y) {
08    int rx = find(x), ry = find(y);
09    if (rx == ry) return;
10    if (rk[rx] < rk[ry]) fa[rx] = ry;
11    else if (rk[rx] > rk[ry]) fa[ry] = rx;
12    else { fa[rx] = ry; rk[ry]++; }
13}
14int main() {
15    for (int i = 1; i <= 6; i++) { fa[i] = i; rk[i] = 0; }
16    uni(1, 2); uni(3, 4); uni(5, 6);   // 3 块
17    uni(2, 4);                          // 合并两块 → 2 块
18    cout << (find(1) == find(3) ? "S" : "D") << " ";
19    int blocks = 0;
20    for (int i = 1; i <= 6; i++) if (find(i) == i) blocks++;
21    cout << blocks;
22    return 0;
23}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6] = {0, 2, 3, 4, 5, 5};
04int find(int x) {
05    if (______) return x;             // x 是根
06    return fa[x] = find(fa[x]);
07}
08int main() {
09    find(1);
10    cout << fa[1];
11    return 0;
12}

单选题：横线处应填入？（使输出为 5）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07int main() {
08    for (int i = 1; i <= 5; i++) fa[i] = i;
09    ______;                      // union(2, 5)
10    cout << find(2) << " " << find(5);
11    return 0;
12}

单选题：横线处应填入？（使输出为 5 5）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6] = {0, 2, 3, 4, 5, 5};
04int find(int x) {
05    if (fa[x] == x) return x;
06    return fa[x] = ______;        // 递归找根并压缩
07}
08int main() {
09    find(1);
10    cout << fa[1] << " " << fa[2];
11    return 0;
12}

单选题：横线处应填入？（使输出为 5 5）

01#include <bits/stdc++.h>
02using namespace std;
03int fa[6], rk[6];
04int find(int x) {
05    return fa[x] == x ? x : fa[x] = find(fa[x]);
06}
07void uni(int x, int y) {
08    int rx = find(x), ry = find(y);
09    if (rx == ry) return;
10    if (rk[rx] < rk[ry]) fa[rx] = ry;
11    else {
12        fa[ry] = rx;
13        if (______) rk[rx]++;       // 秩相等时根秩 +1
14    }
15}
16int main() {
17    for (int i = 1; i <= 4; i++) { fa[i] = i; rk[i] = 0; }
18    uni(1, 2); uni(3, 4); uni(1, 3);
19    cout << find(1);
20    return 0;
21}

单选题：横线处应填入？（使输出为 4——两树等高时合并、根的秩 +1）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04bool isEnd[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (______) ch[p][t] = ++tot;    // 边不存在则新建
11        p = ch[p][t];
12    }
13    isEnd[p] = true;
14}
15int main() {
16    ins("ab"); ins("ac");
17    cout << tot;
18    return 0;
19}

单选题：横线处应填入？（使输出为 3——a、b、c 三个节点）

01#include <bits/stdc++.h>
02using namespace std;
03int ch[100][26];
04bool isEnd[100];
05int tot = 0;
06void ins(string s) {
07    int p = 0;
08    for (char c : s) {
09        int t = c - 'a';
10        if (!ch[p][t]) ch[p][t] = ++tot;
11        p = ch[p][t];
12    }
13    isEnd[p] = true;
14}
15bool query(string s) {
16    int p = 0;
17    for (char c : s) {
18        int t = c - 'a';
19        if (!ch[p][t]) return false;
20        p = ch[p][t];
21    }
22    return ______;               // 完整单词需结束标记
23}
24int main() {
25    ins("ab");
26    cout << (query("ab") ? "Y" : "N") << (query("a") ? "Y" : "N");
27    return 0;
28}