数据结构基础期末复习例题

Min-heap {7, 9, 14, 19, 25, 20, 16, 21}; result after inserting 2. 译 最小堆 {7, 9, 14, 19, 25, 20, 16, 21}，插入 2 后的最小堆？ 解 {2, 7, 14, 9, 25, 20, 16, 21, 19}。2 置于末端后上滤：与 19、9、7 依次交换，2 升至根

这道题考察的是最小堆（Min-heap）的插入操作以及随之而来的上滤（Percolate Up / Bubble Up）过程。

题目：
Min-heap {7, 9, 14, 19, 25, 20, 16, 21}; result after inserting 2.
（最小堆 {7, 9, 14, 19, 25, 20, 16, 21}，插入 2 后的最小堆？）

答案：
{2, 7, 14, 9, 25, 20, 16, 21, 19}

详细解题步骤：

第一步：将新元素插入到堆的末尾
在最小堆中插入新元素时，首先将其放在数组的最后一个位置（即作为完全二叉树的最后一个叶子节点）。

• 原堆有 8 个元素，插入 2 后，2 被放在索引为 8（第 9 个位置）的地方。
• 此时堆的数组状态为：{7, 9, 14, 19, 25, 20, 16, 21, 2}

第二步：执行上滤（Percolate Up）操作
由于新插入的元素 2 可能破坏最小堆的性质（即父节点必须小于或等于子节点），我们需要将它与它的父节点进行比较。如果父节点比它大，则交换位置，直到满足堆的性质或到达根节点。

• 第 1 次比较与交换：

  • 2 所在的位置是索引 8。它的父节点索引是(8-1)/2 = 3。
  • 索引 3 处的元素是19。
  • 因为2 < 19，所以 2 与 19 交换。
  • 当前数组状态：{7, 9, 14, 2, 25, 20, 16, 21, 19}

• 第 2 次比较与交换：

  • 2 现在在索引 3。它的父节点索引是(3-1)/2 = 1。
  • 索引 1 处的元素是9。
  • 因为2 < 9，所以 2 与 9 交换。
  • 当前数组状态：{7, 2, 14, 9, 25, 20, 16, 21, 19}

• 第 3 次比较与交换：

  • 2 现在在索引 1。它的父节点索引是(1-1)/2 = 0。
  • 索引 0 处的元素是7（即根节点）。
  • 因为2 < 7，所以 2 与 7 交换。
  • 当前数组状态：{2, 7, 14, 9, 25, 20, 16, 21, 19}

• 结束条件：

  • 2 现在位于索引 0（根节点），没有父节点了，上滤过程结束。

最终结果：
经过上述步骤，插入 2 并调整后的最小堆为：
{2, 7, 14, 9, 25, 20, 16, 21, 19}

Which statement about d-heaps is True? 译 关于 d-堆，哪项为真？ 解 “父结点可由整除求得”。d-堆中 i 的父为 ⌊(i−2)/d⌋+ 1，用整除即可；其余（完全 d-堆 叶少于内部结点、d-堆用于升序排序、高度正比于 n）均错。

这道题考察的是对d-堆（d-heap）这种数据结构基本性质的理解。我们来逐一分析题目中提到的几个命题，看看为什么只有“父结点可由整除求得”是正确的。

1. “父结点可由整除求得”（True）
在普通的二叉堆（d=2）中，子节点 i 的父节点是 ⌊(i−1)/2⌋。而在 d-堆中，如果根节点从索引 1 开始计算，节点 i 的父节点索引公式为：

Parent(i)=⌊(i−2)/d⌋+1

（注：如果根节点从索引 0 开始，公式则是 ⌊(i−1)/d⌋）
无论是哪种索引方式，这个公式中只包含减法、加法和整数除法（整除）。因此，在计算机底层实现时，确实可以通过简单的整除运算快速定位父节点。这个说法是完全正确的。

2. “d-堆的叶子结点少于内部结点”（False）
对于任何树形结构，叶子结点和内部结点的数量关系取决于树的形状，而不是 d-堆特有的性质。例如，一个只有根节点和几个子节点的 d-堆，叶子结点数量可能等于甚至大于内部结点数量。在完全 d-堆中，叶子结点的数量通常约占总节点数的一半（具体为 ⌈(d−1)n+1d⌉），所以叶子结点往往多于内部结点。

3. “d-堆用于升序排序”（False）
堆排序（Heap Sort）的核心是利用堆的性质，每次提取出最值。

• 如果我们要进行升序排序，我们需要每次取出最小值，因此必须使用最小堆（Min-heap）。
• 如果我们要进行降序排序，我们需要每次取出最大值，因此必须使用最大堆（Max-heap）。
  题目笼统地说“d-堆用于升序排序”是不准确的，因为 d-堆既可以是最大堆也可以是最小堆，它本身并不绑定某种特定的排序方向。

4. “d-堆的高度正比于 n”（False）
这是最容易混淆的一个概念。d-堆是一棵高度平衡的完全树，它的高度 hh 与节点数 nn 的关系是对数级别的：

h≈log⁡d(n)

如果高度正比于 n（即 O(n) ），那它就退化成了链表，失去了堆作为优先队列 O(log⁡n)高效操作的意义。

总结：
在关于 d-堆的诸多性质中，最核心且无争议的数学事实就是其父子节点之间的索引关系可以通过整除运算来高效求得。因此该选项为真。

这是一个非常关键的问题！你问到了堆（Heap）这种数据结构最核心的特性之一。

其实，你不需要额外去“数”或“猜”每一层有多少个元素。因为堆在底层是用一维数组来存储的，而它作为一种完全二叉树（Complete Binary Tree），其层序遍历的数组索引和树的层级结构之间存在着严格的数学对应关系。

只要你知道了数组的长度 n ，每一层的元素个数和节点位置就完全被“锁死”了。

1. 为什么层序遍历能直接反映层级结构？

堆的定义要求它必须是“完全二叉树”。这意味着：

• 除了最底层，其他层的节点都是满的。
• 最底层的节点必须从左到右连续排列，不能有空缺。

因此，当你拿到一个层序遍历的数组时，你只需要知道数组的总长度，就可以像切蛋糕一样，精准地算出每一层有几个元素：

2. 以这道题为例：数组{98, 72, 86, 60, 65, 12, 23, 50}

数组总长度 n=8 。我们来逐层切分：

• 第 0 层（根节点）：只需要 1 个节点。
  • 包含元素：98（索引 0）
  • 剩余元素：8 - 1 = 7
• 第 1 层：最多需要 21=221=2 个节点。
  • 包含元素：72, 86（索引 1, 2）
  • 剩余元素：7 - 2 = 5
• 第 2 层：最多需要 22=422=4 个节点。
  • 包含元素：60, 65, 12, 23（索引 3, 4, 5, 6）
  • 剩余元素：5 - 4 = 1
• 第 3 层：最多需要 23=823=8 个节点。但此时数组里只剩下 1 个元素了。
  • 包含元素：50（索引 7）
  • 剩余元素：1 - 1 = 0，结束！

所以，这棵树的层级结构自然就出来了：

98 (第0层，1个) / \ 72 86 (第1层，2个) / \ / \ 60 65 12 23 (第2层，4个) / 50 (第3层，1个)

3. 通用的计算公式（底层逻辑）

在代码实现中，我们根本不需要去算“每层有几个”，而是直接用数组索引来定位父子节点：

• 父节点：Parent(i) = (i - 1) / 2
• 左孩子：Left(i) = 2 * i + 1
• 右孩子：Right(i) = 2 * i + 2

总结：
做这类题时，不要靠眼睛去画树，要靠数学公式去算。只要把数组按索引 0,1,2,3...依次排开，利用完全二叉树的性质，它的层级结构就是唯一确定的。

详细解析 Keys {92, 81, 58, 21, 57, 45, 161, 38, 117}, h = key%13, double hashing with h2 = (key%11) + 1; average successful search length? 译 双散列（h = key%13、h2 = (key%11) + 1），成功查找平均查找长度？ 解 15/9 ≈ 1.67。各键探测数依次为 1, 1, 1, 1, 1, 3, 2, 1, 4，合计 15，除以 9 得约 1.67。

这道题考察的是双散列（Double Hashing）的插入过程以及成功查找的平均查找长度（ASL）的计算。

在双散列中，如果发生冲突，探测的公式为：

hi(k)=(h1(k)+i⋅h2(k))(modm)

其中：

• m=13m=13 （哈希表大小）
• h1(k)=k(mod13)
• h2(k)=(k(mod11))+1
• ii 是探测次数（从 0 开始）

成功查找的平均查找长度 (ASL)= 所有元素插入时所需的探测次数之和 / 元素总个数。
（因为插入第 nn 个元素时探测了 kk 次，意味着成功查找这个元素也需要 kk 次）

下面我们来逐个计算每个键的探测次数：

1. 插入 92

• h1=92(mod13)=1h1​=92(mod13)=1
• 位置 1 为空，直接放入。
• 探测次数：1
• 当前表：[_, 92, _, _, _, _, _, _, _, _, _, _, _]

2. 插入 81

• h1=81(mod13)=3h1​=81(mod13)=3
• 位置 3 为空，直接放入。
• 探测次数：1
• 当前表：[_, 92, _, 81, _, _, _, _, _, _, _, _, _]

3. 插入 58

• h1=58(mod13)=6h1​=58(mod13)=6
• 位置 6 为空，直接放入。
• 探测次数：1
• 当前表：[_, 92, _, 81, _, _, 58, _, _, _, _, _, _]

4. 插入 21

• h1=21(mod13)=8h1​=21(mod13)=8
• 位置 8 为空，直接放入。
• 探测次数：1
• 当前表：[_, 92, _, 81, _, _, 58, _, 21, _, _, _, _]

5. 插入 57

• h1=57(mod13)=5h1​=57(mod13)=5
• 位置 5 为空，直接放入。
• 探测次数：1
• 当前表：[_, 92, _, 81, _, 57, 58, _, 21, _, _, _, _]

6. 插入 45

• h1=45(mod13)=6h1​=45(mod13)=6 （位置 6 已被 58 占据，冲突！）
• h2=(45(mod11))+1=1+1=2h2​=(45(mod11))+1=1+1=2
• 第 2 次探测： (6+1×2)(mod13)=8(6+1×2)(mod13)=8 （位置 8 已被 21 占据，冲突！）
• 第 3 次探测： (6+2×2)(mod13)=10(6+2×2)(mod13)=10 （位置 10 为空，放入）
• 探测次数：3
• 当前表：[_, 92, _, 81, _, 57, 58, _, 21, _, 45, _, _]

7. 插入 161

• h1=161(mod13)=5h1​=161(mod13)=5 （位置 5 已被 57 占据，冲突！）
• h2=(161(mod11))+1=7+1=8h2​=(161(mod11))+1=7+1=8
• 第 2 次探测： (5+1×8)(mod13)=0(5+1×8)(mod13)=0 （位置 0 为空，放入）
• 探测次数：2
• 当前表：[161, 92, _, 81, _, 57, 58, _, 21, _, 45, _, _]

8. 插入 38

• h1=38(mod13)=12h1​=38(mod13)=12
• 位置 12 为空，直接放入。
• 探测次数：1
• 当前表：[161, 92, _, 81, _, 57, 58, _, 21, _, 45, _, 38]

9. 插入 117

• h1=117(mod13)=0h1​=117(mod13)=0 （位置 0 已被 161 占据，冲突！）
• h2=(117(mod11))+1=7+1=8h2​=(117(mod11))+1=7+1=8
• 第 2 次探测： (0+1×8)(mod13)=8(0+1×8)(mod13)=8 （位置 8 已被 21 占据，冲突！）
• 第 3 次探测： (0+2×8)(mod13)=3(0+2×8)(mod13)=3 （位置 3 已被 81 占据，冲突！）
• 第 4 次探测： (0+3×8)(mod13)=11(0+3×8)(mod13)=11 （位置 11 为空，放入）
• 探测次数：4
• 最终表：[161, 92, _, 81, _, 57, 58, _, 21, _, 45, 117, 38]

计算平均查找长度：

• 各键探测次数分别为：1, 1, 1, 1, 1, 3, 2, 1, 4
• 总探测次数 = 1+1+1+1+1+3+2+1+4=151+1+1+1+1+3+2+1+4=15
• 元素总个数 = 9
• ASL = 15 / 9 ≈ 1.67

与题目给出的答案完全吻合。

4.散列表错题The average search time of searching a hash table with N elements is:

A. O(1) B. O(logN) C. O(N)

D. cannot be determined

5.图相关基础知识点扫盲

1. 第一题

答案：T (正确)

• 题目分析：
  • 已知 bb 到 aa 的最短路径长度 d(b,a)=12d(b,a)=12 。
  • 已知 cc 和 bb 之间有一条边，权重为 2，即 w(c,b)=2w(c,b)=2 。
  • 我们需要判断 cc 到 aa 的最短路径 d(c,a)d(c,a) 是否一定 ≥10≥10 。
• 推理过程：
  根据三角不等式（Triangle Inequality），在最短路径问题中，从点 cc 到点 aa 的距离不可能超过“先从 cc 到 bb ，再从 bb 到 aa ”的距离之和。反之，从 bb 到 aa 的距离也不可能超过“先从 bb 到 cc ，再从 cc 到 aa ”的距离。
  即：

2. 第二题

答案：F (错误)

• 题目分析：
  • 设 PP 是从 SS 到 TT 的最短路径。
  • 如果图中每条边的权重都增加 2，问 PP 是否仍然是最短路径。
• 推理过程：
  最短路径取决于路径上所有边的权重之和。当每条边增加相同的权重时，包含边数更多的路径，其总权重增加的幅度会更大。这可能会导致原本较长的路径（边数少）变得比原本最短的路径（边数多）更短。
• 反例：
  • 路径 1：有 2 条边，每条边权为 5。总权重 = 5+5=105+5=10 。
  • 路径 2：有 1 条边，边权为 11。总权重 = 11。
  • 初始状态：路径 1 (10) < 路径 2 (11)，所以路径 1 是最短路径。
  • 变化后（每边加 2）：
    • 路径 1 新权重： (5+2)+(5+2)=7+7=14(5+2)+(5+2)=7+7=14 。
    • 路径 2 新权重：11+2=1311+2=13 。
  • 结果：14 > 13，路径 2 变成了新的最短路径，原来的最短路径 PP （路径 1）不再是极值。
    因此，该命题是错误的。

3. 第三题

答案：T (正确)

• 题目分析：
  • 询问线段树是否可以用于查找任意索引范围内的最大公约数（GCD）。
• 推理过程：
  线段树是一种高效的数据结构，常用于处理区间查询和更新问题。
  • 原理：GCD 运算满足结合律，即 gcd(gcd(a,b),c)=gcd(a,gcd(b,c))gcd(gcd(a,b),c)=gcd(a,gcd(b,c)) 。这使得我们可以将一个大区间的 GCD 分解为子区间的 GCD 来计算。
  • 实现：线段树的每个节点可以存储对应区间的 GCD 值。构建时，父节点的值为左右子节点值的 GCD。查询时，可以将查询区间分解为线段树上的若干个不重叠区间，计算这些区间 GCD 的 GCD 即可得到结果。
  • 复杂度：这种方法可以在 O(log⁡N)O(logN) 的时间复杂度内完成任意区间的 GCD 查询。
    因此，该命题是正确的。

7-1 File Transfer

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

Input Specification:

Each input file contains one test case. For each test case, the first line contains N (2≤N≤104), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:

I c1 c2

whereIstands for inputting a connection betweenc1andc2; or

C c1 c2

whereCstands for checking if it is possible to transfer files betweenc1andc2; or

S

whereSstands for stopping this case.

Output Specification:

For eachCcase, print in one line the word "yes" or "no" if it is possible or impossible to transfer files betweenc1andc2, respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There arekcomponents." wherekis the number of connected components in this network.

Sample Input 1:

5

C 3 2

I 3 2

C 1 5

I 4 5

I 2 4

C 3 5

S

Sample Output 1:

no

no

yes

There are 2 components.

Sample Input 2:

5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 I 1 3 C 1 5 S

Sample Output 2:

no no yes yes The network is connected.

这道题是典型的并查集（Union-Find）应用。
我们需要支持三种操作：

• I c1 c2：合并 c1 和 c2 所在的集合（建立连接）

• C c1 c2：检查 c1 和 c2 是否在同一个集合中（即是否连通）

• S：结束当前测试案例，输出整个网络的连通情况

N ≤ 10⁴，可以直接用并查集，加上按大小合并 + 路径压缩。

思路

1. 初始化：parent[i] = -1或parent[i] = i表示每个节点独立。

2. Find：路径压缩。

3. Union：按大小（或按秩）合并，小树挂在大树下。

4. 处理每个命令：

   • I：调用Union

   • C：调用Find判断根是否相同

   • S：统计有多少个根（即parent[i] < 0的数量），输出The network is connected.或There are k components.

C 语言实现（按题目的函数原型习惯）

#include <stdio.h> #include <stdlib.h> #define MAXN 10001 int parent[MAXN]; // 初始化 void init(int n) { for (int i = 1; i <= n; i++) { parent[i] = -1; // 负数表示根，绝对值表示集合大小 } } // 带路径压缩的查找 int find(int x) { if (parent[x] < 0) return x; // 根节点 return parent[x] = find(parent[x]); // 路径压缩 } // 按大小合并 void unionSet(int a, int b) { int rootA = find(a); int rootB = find(b); if (rootA == rootB) return; // parent[root] 是负数，值越小表示集合越大 if (parent[rootA] < parent[rootB]) { // rootA 的 size 更大（更负） parent[rootA] += parent[rootB]; parent[rootB] = rootA; } else { parent[rootB] += parent[rootA]; parent[rootA] = rootB; } } int main() { int N; scanf("%d", &N); init(N); char op; int c1, c2; while (1) { scanf(" %c", &op); // 注意空格，跳过换行 if (op == 'S') break; if (op == 'I') { scanf("%d %d", &c1, &c2); unionSet(c1, c2); } else if (op == 'C') { scanf("%d %d", &c1, &c2); if (find(c1) == find(c2)) printf("yes\n"); else printf("no\n"); } } // 统计连通分量个数 int components = 0; for (int i = 1; i <= N; i++) { if (parent[i] < 0) components++; } if (components == 1) printf("The network is connected.\n"); else printf("There are %d components.\n", components); return 0; }

样例验证

样例 1

输入：

text

5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 S

输出：

text

no no yes There are 2 components.

✅ 正确

样例 2

输入：

text

5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 I 1 3 C 1 5 S

输出：

text

no no yes yes The network is connected.

✅ 正确

时间复杂度

• 近似 O(M⋅α(N))，其中 M 是操作次数，α 是反阿克曼函数，几乎常数。

• 完全满足 N≤104 的题目要求。