《数据结构》第一学期期末试卷A (精选04)

试卷信息：满分 100 分 | 考试时间 120 分钟 | 难度分布：基础 40% · 中等 40% · 提高 20%

一、简答题（每小题 5 分，共 15 分）

1. 什么是关键路径？什么是关键活动？

查看答案与解析

答案：

• 关键路径：在 AOE 网（Activity On Edge Network，边表示活动的网）中，从源点到汇点的所有路径中，具有最长路径长度的路径称为关键路径。
• 关键活动：关键路径上的活动称为关键活动。即活动的最早开始时间 $e(i)$ 等于其最迟开始时间 $l(i)$ 的活动（时间余量 $l(i) - e(i) = 0$）。

解析： 本题考查图论中 AOE 网的核心概念。

• 第一步：理解 AOE 网：AOE 网是用边表示活动、顶点表示事件的有向无环图。常用于估算工程完成时间。
• 第二步：分析关键路径：整个工程的完成时间取决于从起点到终点的最长路径长度。如果关键路径上的活动延误，整个工程都会延误。
• 第三步：分析关键活动：关键活动是没有时间余量的活动，其推迟会导致整个工程推迟。

---

难度: ⭐⭐
考点: #图论 #AOE网 #关键路径 #关键活动

💡 学习锦囊

📖 相关公式与知识点:

• 路径长度：路径上各活动持续时间之和。
• 活动 $a_i$ 的最早开始时间 $e(i)$：等于该活动起点事件的最早发生时间。
• 活动 $a_i$ 的最迟开始时间 $l(i)$：等于该活动终点事件的最迟发生时间减去活动持续时间。

思路分析

牢记“最长路径”这一核心特征，区分事件（顶点）和活动（边）的时间概念。

🔄 举一反三

1. 什么是 AOV 网？它与 AOE 网有什么区别？
   查看练习答案与解析

   答案：

   • AOV 网：用顶点表示活动，用有向边表示活动之间优先关系的网。
   • 区别：AOV 网的顶点是活动，边只表示先后顺序；AOE 网的边是活动（有权值/持续时间），顶点表示事件。

2. 什么是前缀编码？哈夫曼编码为什么是前缀编码？

查看答案与解析

答案：

• 前缀编码：在一个编码系统中，任意一个字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。
• 原因：哈夫曼编码是基于哈夫曼树产生的。在哈夫曼树中，每个需要编码的字符都对应树的叶子结点。因为叶子结点不可能成为其他结点的祖先，所以从根到任意叶子的路径（编码）都不会是另一条路径的前缀。

解析：

• 第一步：明确前缀编码定义：前缀编码保证了在解码时不会产生歧义（无剧透解码）。
• 第二步：结合二叉树性质：哈夫曼树构造时，权值作为叶子结点，分支分别标为 0 和 1。叶子结点的特性决定了前缀性质。

---

难度: ⭐⭐
考点: #二叉树 #哈夫曼树 #前缀编码

💡 学习锦囊

📖 相关公式与知识点:

• 哈夫曼树（最优二叉树）：带权路径长度（WPL）最短的二叉树。
• 路径编码：通常左分支为 0，右分支为 1。

易错点

注意区分“前缀”的概念，不是指编码在前面，而是指一个编码不能是另一个的开头部分。

🔄 举一反三

1. 已知字符集 $\{A, B, C, D\}$，其权值分别为 $\{5, 1, 2, 4\}$，求其哈夫曼编码。
   查看练习答案与解析

   答案：$A: 0, B: 100, C: 101, D: 11$（编码不唯一，但长度分布应为 1, 3, 3, 2）。 解析：

   1. 合并最小的 B(1) 和 C(2) 得到 N1(3)。
   2. 合并 N1(3) 和 D(4) 得到 N2(7)。
   3. 合并 N2(7) 和 A(5) 得到根结点(12)。
   4. 分配编码即可。

3. 什么是数据结构？常见的数据结构类型有哪些？

查看答案与解析

答案：

• 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。通常包括逻辑结构、物理（存储）结构和数据的运算。
• 常见类型（按逻辑结构划分）：
  1. 线性结构：线性表、栈、队列、字符串、数组等。
  2. 非线性结构：树形结构（二叉树等）、图形结构（有向图、无向图等）、集合。

解析： 基础概念题。数据结构是计算机存储、组织数据的方式。

---

难度: ⭐
考点: #数据结构定义 #逻辑结构 #物理结构

💡 学习锦囊

📖 相关公式与知识点:

• 逻辑结构：数据元素之间的逻辑关系，与存储无关。
• 存储结构：数据在计算机中的表示，包括顺序存储、链式存储、索引存储、散列存储。

思路分析

回答时要从“元素”和“关系”两个核心点出发。

🔄 举一反三

1. 数据的逻辑结构和存储结构有什么关系？
   查看练习答案与解析

   答案：存储结构是逻辑结构在计算机中的映射 and 实现。一种逻辑结构可以采用多种存储结构来实现，但数据的运算在不同存储结构上的实现效率不同。

二、填空题（每小题 7 分，共 35 分）

1. 循环队列存储在数组 A[0…m-1] 中，队头指针为 f，队尾指针为 r，该队列采用少利用一个元素空间的方式判断队满 and 队空，请回答： (1) 队满的条件：
   (2) 队列不满时，入队操作的相关下标如何调整：
   (3) 如何求队列长度：

查看答案与解析

答案：

• (1) 队满的条件：(r + 1) % m == f
• (2) 入队下标调整：r = (r + 1) % m
• (3) 队列长度：(r - f + m) % m

解析： 本题考查循环队列的边界条件处理。

• 第一步：分析模运算的作用：利用 % m 实现下标在 0 到 m-1 之间循环。
• 第二步：少用一个空间的策略：
  • 队空时：f == r。
  • 队满时：如果再存一个元素 r 就会追上 f，故条件为 (r + 1) % m == f。
• 第三步：计算长度：正常情况下长度为 r - f，若跨越边界则为 r - f + m，统一公式为 (r - f + m) % m。

---

难度: ⭐⭐
考点: #队列 #循环队列 #边界条件

💡 学习锦囊

📖 相关公式与知识点:

• 队空：f == r
• 队满：(r + 1) % m == f
• 出队下标调整：f = (f + 1) % m

易错点

求长度时一定要加 m 再取模，防止 r - f 为负数。

🔄 举一反三

1. 若循环队列 A[0…m-1] 采用一个计数变量 size 来记录元素个数，队头指针为 f，队尾指针为 r。请问此时的队满条件是什么？
   查看练习答案与解析

   答案：size == m解析：引入 size 后，队满直接看个数是否达到上限 m 即可，此时可以使用全部 m 个存储空间。

2. 试分析下面两段程序的时间复杂度：

代码一：

x = 0;
for (i = 1; i < n; i++)
    for (j = 1; j <= n - i; j++)
        x++;

代码二：

i = 1;
for (j = 1; j <= n; j++)
    while (i <= n)
        i = i * 2;

查看答案与解析

答案：

• 代码一时间复杂度：$O(n^2)$
• 代码二时间复杂度：$O(n)$

解析：

• 代码一分析：
  • 外层循环 i 从 1 到 n-1。
  • 内层循环 j 执行次数与 i 相关：当 i=1 时执行 n-1 次，当 i=n-1 时执行 1 次。
  • 总执行次数为等差数列求和：$(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$。
  • 故时间复杂度为 $O(n^2)$。
• 代码二分析（陷阱题）：
  • 变量 i 在最外层初始化为 1。
  • 外层 for 循环 j 从 1 到 n 执行 n 次。
  • 当 j=1 时，进入 while 循环，i 每次翻倍直至大于 n，执行 $\log_2 n$ 次。
  • 当 j=2 及以后，i 的值已经大于 n，无法再满足 while (i <= n) 的条件。
  • 因此，while 循环体在整个程序运行期间仅在 $j=1$ 时执行了一次。
  • 总复杂度为外层循环本身的开销 $O(n)$ 加上 while 循环的 $O(\log n)$，最终为 $O(n)$。

---

难度: ⭐⭐⭐
考点: #时间复杂度 #循环分析

💡 学习锦囊

📖 相关公式与知识点:

• 等差数列求和公式：$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

易错点

对于嵌套循环，不要盲目地将内外层复杂度相乘，必须仔细观察变量在内外层之间是否会被重置或持续累加。

🔄 举一反三

1. 分析以下代码的时间复杂度：

   for (i = 1; i <= n; i *= 2)
       for (j = 1; j <= i; j++)
           x++;

   查看练习答案与解析

   答案：$O(n)$解析：外层 i 取值为 $1, 2, 4, \dots, 2^k \le n$。内层循环次数为当前 i 的值。总次数为 $1 + 2 + 4 + \dots + n \approx 2n$，故复杂度为 $O(n)$。

3. 折半查找过程可以利用一棵称之为“判定树”的二叉树来描述。序列长度为 12 (第 1 个元素在序列中的位置是 1)，则在序列中进行折半查找时对应判定树的根结点右孩子的值是多少?

查看答案与解析

答案： 9

解析： 本题考查折半查找判定树的构造。

• 第一步：确定查找区间：初始区间为 $[low, high] = [1, 12]$。
• 第二步：计算根结点：根结点位置为 $mid = \lfloor(1 + 12) / 2\rfloor = 6$。
• 第三步：确定右子树区间：根结点的右孩子对应的是右半部分区间 $[mid+1, high] = [7, 12]$。
• 第四步：计算右孩子的值：右孩子的位置为 $mid_{right} = \lfloor(7 + 12) / 2\rfloor = 9$。

---

难度: ⭐⭐
考点: #折半查找 #判定树

💡 学习锦囊

📖 相关公式与知识点:

• 折半查找中点计算：$mid = \lfloor(low + high) / 2\rfloor$

思路分析

判定树的每个结点代表当前区间的 $mid$。求左/右孩子即求左/右子区间的中点。

🔄 举一反三

1. 序列长度为 10，在进行折半查找时，对应判定树的根结点左孩子的值是多少？
   查看练习答案与解析

   答案：2 解析：$[1, 10]$ 根结点为 $\lfloor(1+10)/2\rfloor = 5$。左子区间为 $[1, 4]$，其左孩子为 $\lfloor(1+4)/2\rfloor = 2$。

4. 已知广义表 $LS=((a, b, c), (d, e, f))$ 该广义表的表长是多少： 对 LS 做 head(tail(tail(head(LS)))) 操作的结果是什么： 写出运用 head 和 tail 函数取出 LS 中原子 e 的操作：

查看答案与解析

答案：

• 表长：2
• head(tail(tail(head(LS)))) 结果：c
• 取出原子 e 的操作：head(tail(head(tail(LS))))

解析：

• 广义表长度：看最外层括号内逗号分隔的元素个数。$LS$ 包含两个子表，故表长为 2。
• 操作一分析：
  1. head(LS) $\rightarrow$ 取出第一个元素，结果为 (a, b, c)。
  2. tail((a, b, c)) $\rightarrow$ 去掉表头后剩余的部分组成的表，结果为 (b, c)。
  3. tail((b, c)) $\rightarrow$ 再次去掉表头，结果为 (c)。
  4. head((c)) $\rightarrow$ 取出单元素表中的第一个元素，结果为原子 c。
• 取出原子 e 分析：
  1. tail(LS) $\rightarrow$ 得到 ((d, e, f))。
  2. head(tail(LS)) $\rightarrow$ 得到 (d, e, f)。
  3. tail(head(tail(LS))) $\rightarrow$ 得到 (e, f)。
  4. head(tail(head(tail(LS)))) $\rightarrow$ 得到原子 e。

---

难度: ⭐⭐
考点: #广义表 #head操作 #tail操作

💡 学习锦囊

📖 相关公式与知识点:

• head(L)：返回列表的第一个元素（可以是原子或子表）。
• tail(L)：返回除去第一个元素后，剩余元素组成的列表。

易错点

tail 操作返回的结果必定是一个表，哪怕原表只有一个元素，tail 也会返回空表 ()。

🔄 举一反三

1. 已知 $LS=(a, (b, c), d)$，求 head(tail(LS))。
   查看练习答案与解析

   答案：(b, c)解析：tail(LS) = ((b, c), d)，取出表头即为 (b, c)。

5. 一棵完全二叉树上有 1001 个结点，问: (1) 叶子结点的个数是多少：
   (2) 树的深度是多少：

查看答案与解析

答案：

• (1) 叶子结点个数：501
• (2) 树的深度：10

解析：

• 第一步：求叶子结点个数：
  • 对于任意二叉树，度为 0 的结点数 $n_0$ 和度为 2 的结点数 $n_2$ 满足关系：$n_0 = n_2 + 1$。
  • 总结点数 $n = n_0 + n_1 + n_2$（$n_1$ 为度为 1 的结点数）。
  • 代入得 $n = 2n_0 + n_1 - 1 \implies n + 1 = 2n_0 + n_1$。
  • 结合完全二叉树性质，$n_1$ 只能是 0 或 1。
  • 将 $1001$ 代入：$1002 = 2n_0 + n_1$。
  • 由于 $1002$ 是偶数，$n_1$ 只能为 $0$，故 $2n_0 = 1002 \implies n_0 = 501$。
• 第二步：求树的深度：
  • 深度公式：$k = \lfloor\log_2 n\rfloor + 1$。
  • $\log_2 1001 \approx 9.96$。
  • $k = \lfloor 9.96 \rfloor + 1 = 9 + 1 = 10$。

---

难度: ⭐⭐
考点: #树与二叉树 #完全二叉树性质

💡 学习锦囊

📖 相关公式与知识点:

• $n_0 = \lceil n / 2 \rceil$（针对完全二叉树叶子结点的快捷求法）
• $k = \lfloor\log_2 n\rfloor + 1$

思路分析

直接套用完全二叉树的叶子结点与总结点数的比例公式 $n_0 = \lceil n / 2 \rceil$ 最为快捷。

🔄 举一反三

1. 一棵完全二叉树有 500 个结点，求其叶子结点的个数。
   查看练习答案与解析

   答案：250 解析：$n_0 = \lceil 500 / 2 \rceil = 250$。

三、综合应用分析题（每小题 15 分，共 30 分）

1. 设哈希函数 $H(K) = 3K \pmod{11}$，哈希地址空间为 $0 \sim 10$。对关键字序列 $(32，13，49，24，38，21，4，12)$，按线性探测法解决冲突画出哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度 ASLsucc 和 ASLunsucc。

查看答案与解析

答案：

哈希表状态：

地址	0	1	2	3	4	5	6	7	8	9	10
关键字		4		12	49	38	13	24	32	21
探测次数		1		1	1	2	1	2	1	2

• 查找成功时的 ASL：$ASL_{succ} = \frac{1+1+1+2+1+2+1+2}{8} = \frac{11}{8} = 1.375$
• 查找失败时的 ASL：$ASL_{unsucc} = \frac{1+2+1+8+7+6+5+4+3+2+1}{11} = \frac{40}{11} \approx 3.64$

解析：

• 第一步：计算初始哈希值及线性探测：
  • $H(32) = 3 \times 32 \pmod{11} = 96 \pmod{11} = 8$（存入 8，比较 1 次）
  • $H(13) = 3 \times 13 \pmod{11} = 39 \pmod{11} = 6$（存入 6，比较 1 次）
  • $H(49) = 3 \times 49 \pmod{11} = 147 \pmod{11} = 4$（存入 4，比较 1 次）
  • $H(24) = 3 \times 24 \pmod{11} = 72 \pmod{11} = 6$（冲突，探测 7 空，存入 7，比较 2 次）
  • $H(38) = 3 \times 38 \pmod{11} = 114 \pmod{11} = 4$（冲突，探测 5 空，存入 5，比较 2 次）
  • $H(21) = 3 \times 21 \pmod{11} = 63 \pmod{11} = 8$（冲突，探测 9 空，存入 9，比较 2 次）
  • $H(4) = 3 \times 4 \pmod{11} = 12 \pmod{11} = 1$（存入 1，比较 1 次）
  • $H(12) = 3 \times 12 \pmod{11} = 36 \pmod{11} = 3$（存入 3，比较 1 次）
• 第二步：计算 $ASL_{unsucc}$：
  • 查找失败时，需要从计算出的哈希地址向后探测，直到遇到空位置。
  • 假设哈希地址落入 $0 \sim 10$ 的概率均等。
  • 映射到 0：探测 0（空），探测 1 次。
  • 映射到 1：探测 1, 2（空），探测 2 次。
  • 映射到 2：探测 2（空），探测 1 次。
  • 映射到 3：探测 3,4,5,6,7,8,9,10（空），探测 8 次。
  • ...
  • 总探测次数之和为 40。

---

难度: ⭐⭐⭐
考点: #散列表 #哈希表 #线性探测法 #ASL

💡 学习锦囊

📖 相关公式与知识点:

• $ASL_{succ} = \frac{\sum 成功探测次数}{元素个数}$
• $ASL_{unsucc} = \frac{\sum 从对应地址探测至空的次数}{表长/模数}$

易错点

计算查找失败的 ASL 时，除数是模数（此处为 11），而不是元素个数。

🔄 举一反三

1. 对于上述同样的序列和哈希函数，若采用链地址法解决冲突，查找成功时的 ASL 是多少？
   查看练习答案与解析

   答案：$ASL_{succ} = (1 \times 6 + 2 \times 2) / 8 = 1.25$解析：在 6 和 8 地址上有链表。1 次比较的元素有 6 个，2 次的有 2 个。

2. 已知下列字符 A、B、C、D、E 的权值分别为 3、12、7、4、2。 (1) 画出对应的哈夫曼树 (保证每个结点的左子树权值小于右子树权值)。
   (2) 给出每个字符的哈夫曼编码。
   (3) 填写出其对应哈夫曼树 HT 的存储结构的终态(如下表)。

	weight	parent	lchild	rchild
1	3
2	12
3	7
4	4
5	2
6
7
8
9

查看答案与解析

答案：

(1) 哈夫曼树结构：

• $N_1$: $E(2)$ 和 $A(3)$ 结合为 $5$（左 $E$ 右 $A$）
• $N_2$: $D(4)$ 和 $N_1(5)$ 结合为 $9$（左 $D$ 右 $N_1$）
• $N_3$: $C(7)$ 和 $N_2(9)$ 结合为 $16$（左 $C$ 右 $N_2$）
• $N_4$: $B(12)$ 和 $N_3(16)$ 结合为 $28$（左 $B$ 右 $N_3$）

(2) 哈夫曼编码（约定左 0 右 1）：

• $B: 0$
• $C: 10$
• $D: 110$
• $E: 1110$
• $A: 1111$

(3) 存储结构终态表：

结点序号	weight	parent	lchild	rchild
1 (A)	3	6	0	0
2 (B)	12	9	0	0
3 (C)	7	8	0	0
4 (D)	4	7	0	0
5 (E)	2	6	0	0
6 (N1)	5	7	5	1
7 (N2)	9	8	4	6
8 (N3)	16	9	3	7
9 (N4)	28	0	2	8

解析：

• 第一步：贪心构建哈夫曼树：每次挑选权值最小的两个结点结合。
• 第二步：填表：序号 $1 \sim 5$ 为叶子。每次新生成的结点分配给序号 $6 \sim 9$。

---

难度: ⭐⭐⭐
考点: #哈夫曼树 #哈夫曼编码 #树的存储结构

💡 学习锦囊

📖 相关公式与知识点:

• 哈夫曼树总结点数：对于 $n$ 个叶子结点，非叶子结点数为 $n-1$，总结点数为 $2n-1$。

思路分析

严格按照题目要求“左子树权值小于右子树权值”进行树的搭建，不要随意放置左右位置。

🔄 举一反三

1. 求该哈夫曼树的带权路径长度 WPL。
   查看练习答案与解析

   答案：$WPL = 12 \times 1 + 7 \times 2 + 4 \times 3 + 2 \times 4 + 3 \times 4 = 58$

3. 设待排序的关键字序列为 $\{16, 12, 30, 2, 28, 10, 20\}$ 试分别写出使用以下 5 种排序方法进行升序排序，只写出第 2 趟排序结束后关键字序列的状态，并写出其稳定性。 (1) 直接插入排序
   (2) 2 路归并排序
   (3) 冒泡排序
   (4) 快速排序
   (5) 简单选择排序

查看答案与解析

答案：

• (1) 直接插入排序：序列为 $\{12, 16, 30, 2, 28, 10, 20\}$；稳定性：稳定。
• (2) 2路归并排序：序列为 $\{2, 12, 16, 30, 10, 20, 28\}$；稳定性：稳定。
• (3) 冒泡排序（大数下沉）：序列为 $\{12, 2, 16, 10, 20, 28, 30\}$；稳定性：稳定。
• (4) 快速排序（首元素为枢轴）：序列为 $\{2, 10, 12, 16, 28, 30, 20\}$；稳定性：不稳定。
• (5) 简单选择排序：序列为 $\{2, 10, 30, 16, 28, 12, 20\}$；稳定性：不稳定。

解析：

• 直接插入：第 2 趟插入第 3 个元素 30，因 $30 > 16$，保持原位。
• 归并排序：第 1 趟划分粒度为 2，第 2 趟粒度为 4，$[12, 16, 30, 2] \rightarrow [2, 12, 16, 30]$。
• 冒泡排序：每趟将最大元素沉底，第 1 趟 30 沉底，第 2 趟 28 沉底。

---

难度: ⭐⭐⭐
考点: #排序算法 #时间复杂度 #稳定性

💡 学习锦囊

📖 相关公式与知识点:

• 直接插入排序：将待排元素插入已排序序列，最好 $O(n)$，最坏 $O(n^2)$，稳定
• 2路归并排序：分治合并，每趟 $O(n)$，共 $\lceil\log n\rceil$ 趟，稳定
• 冒泡排序：相邻比较交换，每趟确定一个最值，稳定
• 简单选择排序：每趟选最小元素交换，不稳定
• 快速排序：基准划分递归，平均 $O(n\log n)$，不稳定

思路分析

逐趟模拟各排序算法的执行过程，注意第 2 趟结束时的中间状态，同时关注稳定性（相等元素是否保持原相对顺序）。

🔄 举一反三

1. 堆排序建立大根堆时，初始的堆结构状态是什么？
   查看练习答案与解析

   答案：$\{30, 28, 20, 2, 16, 10, 12\}$

4. 已知一棵二叉树的先序、中序 and 后序序列如下，其中有一些看不清的字母用 * 表示: 前序序列: *BC***G* 中序序列: CB*EAGH* 后序序列: *EDB**FA (1) 画出这棵二叉树，写出树的中序序列
   (2) 画出这棵二叉树的中序线索树。

查看答案与解析

答案：(1) 补全后的序列与树结构：

• 前序序列：A B C D E F G H
• 中序序列：C B D E A G H F
• 后序序列：C E D B H G F A

二叉树结构描述：

• 根结点为 $A$。
• $A$ 的左子树根为 $B$。$B$ 的左孩子为 $C$，右孩子为 $D$。$D$ 的右孩子为 $E$。
• $A$ 的右子树根为 $F$。$F$ 的左孩子为 $G$。$G$ 的右孩子为 $H$。

(2) 中序线索树（文字描述线索指向）：

• 中序序列：$C - B - D - E - A - G - H - F$
• 前驱 and 后继线索：
  • $C$：左指针悬空（线索指向 NULL），右指针线索指向 $B$。
  • $E$：左指针线索指向 $D$，右指针线索指向 $A$。
  • $H$：左指针线索指向 $G$，右指针线索指向 $F$。

解析：

• 核心突破口：后序末尾一定是根。后序最后是 $A$，所以 $A$ 是根。
• 将 $A$ 代入中序 CB*E A GH*，划分左右子树。

---

难度: ⭐⭐⭐
考点: #二叉树还原 #中序线索树

💡 学习锦囊

📖 相关公式与知识点:

• 二叉树还原：由前序+中序或后序+中序可唯一确定二叉树
• 前序定根：前序/后序序列确定根结点，中序序列划分左右子树
• 线索树：利用空指针域存储前驱/后继线索，左线索指前驱，右线索指后继
• 中序线索化：按中序遍历顺序建立线索

思路分析

先根据前序和中序序列递归还原二叉树，再按中序遍历顺序将空指针改为线索，指向中序前驱和后继。

🔄 举一反三

1. 已知中序为 BACD，后序为 B DCA，求前序。
   查看练习答案与解析

   答案：A B C D

5. 有向网如下图所示，试用迪杰斯特拉算法求出从顶点 1 到其他各顶点间的最短路径，完成下表。

查看答案与解析

答案：

终点\D	初始	i=1	i=2	i=3	i=4
2	10(1,2)	10(1,2)	10(1,2)	10(1,2)	10(1,2)
3	$\infty$	60(1,2,3)	50(1,4,3)	50(1,4,3)	50(1,4,3)
4	30(1,4)	30(1,4)	30(1,4)	30(1,4)	30(1,4)
5	100(1,5)	100(1,5)	90(1,4,5)	60(1,4,3,5)	60(1,4,3,5)
S	$\{1\}$	$\{1,2\}$	$\{1,2,4\}$	$\{1,2,4,3\}$	$\{1,2,4,3,5\}$

解析：

• 初始：S 包含 $\{1\}$，直接连接的距离已知。
• $i=1$：选中距离最短的结点 2，考察 2 出发的路径更新。
• $i=2$：选中距离最短的结点 4，更新距离。

---

难度: ⭐⭐⭐
考点: #图论 #最短路径 #迪杰斯特拉算法

💡 学习锦囊

📖 相关公式与知识点:

• 贪心策略：每次选择当前距离源点最近的未访问顶点。
• 松弛操作：$D[j] = \min(D[j], D[u] + w(u, j))$。

思路分析

重点在于每一步都要更新从新加入顶点出发可达的邻接顶点的距离。

易错点

注意路径的记录，更新距离时要同时更新前驱结点。

🔄 举一反三

1. 迪杰斯特拉算法是否适用于包含负权边的图？
   查看练习答案与解析

   答案：不适用。 解析：迪杰斯特拉算法基于贪心策略，认为一旦确定了最短路径的顶点就不会再更改。如果存在负权边，可能会导致先确定的路径被后遍历到的负权边“推翻”，从而得到错误结果。

6. 已知一个无向图如下图所示，请写出该图的邻接矩阵，并用 Prim 算法生成最小树(设以 $1$ 为起点)，并画出每一步构造过程。

查看答案与解析

答案：

邻接矩阵：

$$\begin{pmatrix} 0 & 20 & \infty & \infty & 13 & 9 \\ 20 & 0 & 5 & 6 & \infty & 11 \\ \infty & 5 & 0 & 7 & \infty & \infty \\ \infty & 6 & 7 & 0 & 18 & 14 \\ 13 & \infty & \infty & 18 & 0 & 10 \\ 9 & 11 & \infty & 14 & 10 & 0 \end{pmatrix}$$

Prim 构造过程：

1. 初始选 $1$，连接边为 $(1,6):9$。
2. 加入 $6$，连接边为 $(6,5):10$。
3. 加入 $5$，连接边为 $(6,2):11$。
4. 加入 $2$，连接边为 $(2,3):5$。
5. 加入 $3$，连接边为 $(2,4):6$。

---

难度: ⭐⭐⭐
考点: #邻接矩阵 #Prim算法 #最小生成树

💡 学习锦囊

📖 相关公式与知识点:

• 最小生成树性质（MST 性质）。
• Prim 算法时间复杂度：$O(|V|^2)$，适合稠密图。

思路分析

Prim 算法是从顶点的角度出发，每次选择连接已选顶点集与未选顶点集的权值最小的边。

🔄 举一反三

1. 简述 Kruskal 算法的基本思想。
   查看练习答案与解析

   答案：Kruskal 算法从边的角度出发。首先将所有边按权值从小到大排序，然后依次选择权值最小的边加入集合，若加入后不构成回路则保留，否则舍弃，直到选出 $n-1$ 条边。

四、算法设计题（每小题 10 分，共 20 分）

1. 试写出折半查找的非递归算法。

查看答案与解析

答案：

int Search_Bin(SSTable ST, KeyType key) {
    int low = 1;
    int high = ST.length;
    int mid;
    
    while (low <= high) {
        mid = (low + high) / 2;
        if (ST.R[mid].key == key) {
            return mid; // 查找成功
        } else if (ST.R[mid].key > key) {
            high = mid - 1; // 在左半区
        } else {
            low = mid + 1; // 在右半区
        }
    }
    return 0; // 查找失败
}

解析： 标准的二分查找非递归实现。需要维护 low 和 high 指针。

---

难度: ⭐⭐
考点: #查找算法 #二分查找 #算法设计

💡 学习锦囊

📖 相关公式与知识点:

• 前提条件：顺序存储结构且关键字有序。
• 时间复杂度：$O(\log_2 n)$。

易错点

循环条件是 low <= high，注意 = 号不能漏掉。

🔄 举一反三

1. 请编写折半查找的递归算法。
   查看练习答案与解析

   答案：

   int BinSearch_Rec(SSTable ST, KeyType key, int low, int high) {
       if (low > high) return 0;
       int mid = (low + high) / 2;
       if (ST.R[mid].key == key) return mid;
       else if (ST.R[mid].key > key) 
           return BinSearch_Rec(ST, key, low, mid - 1);
       else 
           return BinSearch_Rec(ST, key, mid + 1, high);
   }

2. 单链表结点定义如下，设计算法求带头节点的单链表中最大的节点值。

查看答案与解析

答案：

ElemType Max(LinkList L) {
    if (L == NULL || L->next == NULL) {
        return MM; // 链表为空返回定义的极小值
    }
    
    LNode *p = L->next;
    ElemType max_val = p->data;
    
    while (p != NULL) {
        if (p->data > max_val) {
            max_val = p->data;
        }
        p = p->next;
    }
    return max_val;
}

解析： 通过一次遍历，维护一个 max_val 即可。

---

难度: ⭐⭐
考点: #链表 #算法设计

💡 学习锦囊

📖 相关公式与知识点:

• 单链表指针移动：p = p->next。

思路分析

链表无法随机访问，必须从头结点开始逐个遍历，用一个临时变量记录当前最大值。

🔄 举一反三

1. 设计算法求带头结点的单链表的结点个数。
   查看练习答案与解析

   答案：

   int CountNodes(LinkList L) {
       int count = 0;
       LNode *p = L->next;
       while (p != NULL) {
           count++;
           p = p->next;
       }
       return count;
   }