《数据结构》第一学期期末试卷A (精选05)
试卷信息：满分 100 分 | 考试时间 120 分钟 | 难度分布：基础 30% · 中等 45% · 提高 25%
一、名词解释（本题满分10分）
1、（4分）逻辑结构和存储结构
查看答案与解析
答案：
- 逻辑结构：指数据元素之间的逻辑关系，与它们在计算机中的存储位置无关。基本的逻辑结构包括集合、线性结构、树形结构和图形结构。
- 存储结构：又称物理结构，是数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系的表示。基本的存储结构有顺序存储、链式存储、索引存储和散列存储。
解析： 数据结构包括三方面内容：逻辑结构、存储结构和数据的运算。
- 第一步：理解逻辑结构：它是面向问题的，独立于计算机。
- 第二步：理解存储结构：它是面向计算机的，是逻辑结构在计算机内存中的具体实现。
难度: ⭐
考点: #数据结构概念 #逻辑结构 #存储结构
💡 学习锦囊
📖 相关公式与知识点:
- 逻辑结构是存储结构的基础，一种逻辑结构可以映射为多种不同的存储结构（如线性表可以采用顺序存储或链式存储）。
思路分析
名词解释要抓住核心定义，对于成对出现的概念（如逻辑/存储、稳定/不稳定），重点说明两者的区别和联系。
🔄 举一反三
- 简述顺序存储结构和链式存储结构的特点。
查看练习答案与解析
答案：
- 顺序存储结构：利用数据元素在计算机逻辑上相邻的存储位置来表示元素之间的逻辑关系。优点是支持随机存取，缺点是插入和删除操作需要移动大量元素。
- 链式存储结构：通过指针（链）来表示元素之间的逻辑关系。优点是插入和删除操作灵活，缺点是不支持随机存取，且指针占用额外的存储空间。
2、（3分）稳定的排序方法和不稳定的排序方法
查看答案与解析
答案：
- 稳定的排序方法：在待排序的记录序列中，如果存在多个具有相同关键字的记录，若经过排序后，这些记录的相对次序保持不变，则称该排序方法是稳定的。
- 不稳定的排序方法：若在排序后的序列中，具有相同关键字的记录的相对次序发生了改变，则称该排序方法是不稳定的。
解析： 排序算法的稳定性是衡量算法优劣的一个重要指标。
- 第一步：理解稳定性定义：关键在于相同关键字元素在排序前后的相对次序。
- 第二步：举例说明：如序列 $\{5, 3_a, 3_b\}$，稳定排序后为 $\{3_a, 3_b, 5\}$，不稳定可能为 $\{3_b, 3_a, 5\}$。
难度: ⭐
考点: #排序算法 #稳定性
💡 学习锦囊
📖 相关公式与知识点:
- 常见的稳定排序算法：直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序。
- 常见的不稳定排序算法：希尔排序、快速排序、简单选择排序、堆排序。
思路分析
回答排序稳定性时，一定要紧扣“相同关键字”和“相对次序”这两个核心词。
🔄 举一反三
- 快速排序为什么是不稳定的？请举例说明。
查看练习答案与解析
答案： 在快速排序的划分过程中，元素会发生跨越式的交换，这很容易破坏相同关键字的相对次序。 示例：序列 $\{3, 2, 2'\}$，以 3 为基准进行划分。右指针从右向左扫描，找到小于 3 的 $2'$ 与 3 交换，序列变为 $\{2', 2, 3\}$。此时原本在后面的 $2'$ 跑到了 2 的前面，相对次序改变，因此不稳定。
3、（3分）完全二叉树
查看答案与解析
答案：完全二叉树：深度为 $k$、有 $n$ 个结点的二叉树，当且仅当其每一个结点都与深度为 $k$ 的满二叉树中编号从 $1$ 至 $n$ 的结点一一对应时，称之为完全二叉树。
解析： 完全二叉树是满二叉树的一部分，它的结点分布是“紧凑”的。
- 第一步：理解特征：叶子结点只可能在层次最大的两层上出现。
- 第二步：度数限制：对于任一结点，若其右子树的最大层次为 $l$，则其左子树的最大层次必为 $l$ 或 $l+1$。
难度: ⭐
考点: #完全二叉树 #树与二叉树
💡 学习锦囊
📖 相关公式与知识点:
- 总结点数 $n$ 与叶子结点数 $n_0$ 的关系：$n_0 = \lceil n / 2 \rceil$。
- 结点的父子下标关系（1-based）：结点 $i$ 的左孩子为 $2i$，右孩子为 $2i+1$，双亲结点为 $\lfloor i / 2 \rfloor$。
易错点
完全二叉树和满二叉树的联系与区别：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
🔄 举一反三
- 一棵完全二叉树有 6 层，它最少有多少个结点？最多有多少个结点？
查看练习答案与解析
答案：最少有 32 个结点；最多有 63 个结点。 解析：
- 完全二叉树的前 5 层必须是满的。前 5 层的结点总数为 $2^5 - 1 = 31$。
- 最少情况：第 6 层只有 1 个结点，总数 = $31 + 1 = 32$。
- 最多情况：第 6 层也是满的，总数 = $2^6 - 1 = 63$。
二、分析计算题（本题满分20分，每小题4分）
作答要求：写出推演依据和计算过程。
1、设有一个二维数组 A[m][n]按行优先顺序存储，假设 A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个字节的空间，问 A[3]3存放在什么位置？脚注(10)表示用10进制表示。
查看答案与解析
答案：$A[3][3]$ 存放在 $692$ 位置。
解析： 本题考查二维数组按行优先存储的地址计算。
- 第一步：列出计算公式：二维数组 $A[m][n]$ 按行优先存储，设首地址为 $Loc(A[0][0])$，每个元素占 $L$ 字节。则元素 $A[i][j]$ 的地址计算公式为：$$Loc(A[i][j]) = Loc(A[0][0]) + (i \times n + j) \times L$$
- 第二步：代入已知条件求解列数 $n$： 已知 $Loc(A[0][0]) = 644$，$Loc(A[2][2]) = 676$，$L = 1$。 将 $A[2][2]$ 代入公式：$$676 = 644 + (2 \times n + 2) \times 1$$$$2n + 2 = 32 \implies 2n = 30 \implies n = 15$$得出数组每行有 $15$ 个元素。
- 第三步：计算 $A[3][3]$ 的位置：$$Loc(A[3][3]) = 644 + (3 \times 15 + 3) \times 1 = 644 + 45 + 3 = 692$$
难度: ⭐⭐
考点: #数组存储 #行优先存储 #地址计算
💡 学习锦囊
📖 相关公式与知识点:
- 行优先存储：先存第一行，再存第二行... $Loc(A[i][j]) = Loc(A[0][0]) + (i \times n + j) \times L$。
- 列优先存储：先存第一列，再存第二列... $Loc(A[i][j]) = Loc(A[0][0]) + (j \times m + i) \times L$。
易错点
注意题目中下标是从 0 开始还是从 1 开始，此处 $A[0][0]$ 明确是起点。
🔄 举一反三
- 设二维数组 $A[10][20]$ 按列优先顺序存储，首地址为 100，每个元素占 2 个字节，求 $A[5][10]$ 的存放位置（下标从 0 开始）。
查看练习答案与解析
答案：310 解析：
- 列优先公式：$Loc(A[i][j]) = Loc(A[0][0]) + (j \times m + i) \times L$
- $m = 10$（行数），$n = 20$（列数），$L = 2$
- $Loc(A[5][10]) = 100 + (10 \times 10 + 5) \times 2 = 100 + 105 \times 2 = 310$
2、 已知广义表 $A=(a,b,(c,d),(e,(f,g)))$，求广义表的长度和函数 $GetHead(GetTail(GetHead(GetTail(GetTail(A)))))$ 的结果。
查看答案与解析
答案：
- 广义表长度：4
- 运算结果：$d$
解析： 本题考查广义表的长度计算及 Head 和 Tail 基础操作。
- 第一步：求表长：最外层括号内逗号分隔的元素有 4 个（原子 $a$、原子 $b$、子表 $(c, d)$、子表 $(e,(f,g))$）。故长度为 $4$。
- 第二步：逐步执行函数运算：
- $GetTail(A) = (b, (c, d), (e, (f, g)))$
- $GetTail(GetTail(A)) = ((c, d), (e, (f, g)))$
- $GetHead(GetTail(GetTail(A))) = (c, d)$
- $GetTail((c, d)) = (d)$
- $GetHead((d)) = d$ 综上，$GetHead(GetTail(GetHead(GetTail(GetTail(A))))) = d$。
难度: ⭐⭐
考点: #广义表 #GetHead #GetTail
💡 学习锦囊
📖 相关公式与知识点:
GetHead(L)：取出列表 $L$ 的第一个元素。GetTail(L)：返回去除首元素后剩余部分组成的列表。
易错点
记住 GetTail 操作的结果永远是一个列表，即使里面只有一个元素，也需要带括号。
🔄 举一反三
- 广义表 $L=((a,b), c, (d,e))$，深度是多少？执行 $GetHead(GetTail(L))$ 的结果是什么？
查看练习答案与解析
答案：深度为 2；结果为 $c$。 解析：
- 深度是括号嵌套的最大层数，此处为 2。
- $GetTail(L) = (c, (d, e))$
- $GetHead(GetTail(L)) = c$
3、 指出下列算法的基本语句，分析基本语句的频度，计算其时间复杂度。
查看答案与解析
答案：
- 基本语句：
k < j（或最内层循环体内的操作） - 频度：$\frac{n(n+1)(n+2)}{6}$
- 时间复杂度：$O(n^3)$
解析： 本题考查三重嵌套循环的频度计算与时间复杂度。
- 第一步：明确基本语句：即执行次数最多的最内层语句。
- 第二步：求内两层循环的总频度： 对于固定的外层循环变量 $i$，$j$ 从 $0$ 变化到 $i$。当 $j$ 确定时，最内层 $k$ 执行 $j$ 次。 对于每个 $i$，内两层循环共执行：$$S(i) = \sum_{j=0}^{i} j = \frac{i(i+1)}{2}$$
- 第三步：累加外层循环： 变量 $i$ 从 $0$ 变化到 $n$，总频度 $T(n)$ 为：$$T(n) = \sum_{i=0}^{n} \frac{i(i+1)}{2} = \frac{1}{2} \sum_{i=0}^{n} (i^2 + i)$$根据级数求和公式 $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ 及 $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$，代入化简得：$$T(n) = \frac{n(n+1)(n+2)}{6}$$
- 第四步：确定时间复杂度：取最高阶项，得到时间复杂度为 $O(n^3)$。
难度: ⭐⭐⭐
考点: #时间复杂度 #循环频度
💡 学习锦囊
📖 相关公式与知识点:
- 等差数列求和公式：$\sum_{i=1}^n i = \frac{n(n+1)}{2}$。
- 平方级数求和公式：$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$。
思路分析
计算三重及以上的循环时间复杂度时，应从内向外逐层列出关于循环变量的求和算式。
🔄 举一反三
- 分析以下代码的时间复杂度：c
for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) for (int k = 1; k <= n; k++) x++;查看练习答案与解析
答案：$O(n^3)$解析：最内层
k独立执行n次。前两层i和j的执行次数总和为 $\frac{n(n+1)}{2}$。总执行次数为 $n \times \frac{n(n+1)}{2}$，最高次项为 $n^3$，复杂度为 $O(n^3)$。
4、一棵完全二叉树上有 1001 个节点，那么叶子节点的个数是多少？
查看答案与解析
答案： 叶子节点个数是 $501$ 个。
解析： 本题考查完全二叉树的基本性质。
方法一（公式法）： 在完全二叉树中，叶子节点数 $n_0$ 可以直接通过总结点数 $n$ 得到：
$$n_0 = \lceil n / 2 \rceil$$将 $n = 1001$ 代入：
$$n_0 = \lceil 1001 / 2 \rceil = \lceil 500.5 \rceil = 501$$方法二（二叉树通式法）： 根据二叉树性质，度为 $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$。 由于是完全二叉树，$n_1$ 只能是 $0$ 或 $1$。 将 $n = 1001$ 代入：
$$1001 = 2n_0 + n_1 - 1 \implies 1002 = 2n_0 + n_1$$因为 $1002$ 是偶数，$n_1$ 必须是偶数，因此 $n_1 = 0$。 所以 $2n_0 = 1002 \implies n_0 = 501$。
难度: ⭐⭐
考点: #完全二叉树 #二叉树性质
💡 学习锦囊
📖 相关公式与知识点:
- 在完全二叉树中，最后一个非叶子节点的编号为 $\lfloor n / 2 \rfloor$（下标从 1 开始）。
思路分析
完全二叉树的叶子节点数量占比基本都在一半左右，记住 $\lceil n / 2 \rceil$ 的快捷技巧可以秒杀此类选择/填空。
易错点
- 混淆完全二叉树和满二叉树的性质
- 忘记完全二叉树中度为1的节点只能有0或1个
🔄 举一反三
- 一棵完全二叉树共有 700 个节点，求其叶子节点个数。
查看练习答案与解析
答案：350 解析：$n_0 = \lceil 700 / 2 \rceil = 350$。
5、G是一个非连通无向图，共有28条边，则该图至少有多少个顶点？为什么？
查看答案与解析
答案： 图 $G$ 至少有 $9$ 个顶点。
解析： 本题考查无向图的边与顶点数的极值关系。
- 第一步：分析题意：图 $G$ 为非连通图，要求顶点数“至少”（最少）。我们可以通过“让部分顶点高度紧密连接，而隔离个别顶点”的方法来实现。
- 第二步：构造极端连通结构： 为了让总顶点数最少，应使其中一个连通分量（子图）包含尽量多的边。 最理想的构造是：图 $G$ 由一个包含 $k$ 个顶点的完全无向图 $K_k$，再加上 $1$ 个孤立顶点组成。此时图必然是非连通的。
- 第三步：代入公式计算： $k$ 个顶点的完全图拥有的边数为 $C_k^2 = \frac{k(k-1)}{2}$。 我们需要边数不少于 28：$$\frac{k(k-1)}{2} \geq 28 \implies k(k-1) \geq 56$$
- 当 $k=7$ 时，$\frac{7 \times 6}{2} = 21 < 28$（不满足）。
- 当 $k=8$ 时，$\frac{8 \times 7}{2} = 28 \geq 28$（刚好满足）。 因此这个极大连通子图至少需要 $8$ 个顶点。
- 第四步：得出最终答案： 连通子图有 $8$ 个顶点，加上那个孤立点，总共至少需要 $8 + 1 = 9$ 个顶点。
难度: ⭐⭐⭐
考点: #图的定义与性质 #无向完全图 #非连通图
💡 学习锦囊
📖 相关公式与知识点:
- $n$ 个顶点的无向完全图共有 $\frac{n(n-1)}{2}$ 条边。
- $n$ 个顶点的有向完全图共有 $n(n-1)$ 条边。
思路分析
解决非连通图顶点数极值问题的关键是构造一个极端情况：一个完全图加上一个孤立顶点。这样可以用最少的顶点数达到要求的边数。
易错点
很容易忘记加上独立于核心子图之外的那个“孤立顶点”，导致漏掉 1。
🔄 举一反三
- 具有 15 条边的非连通无向图至少包含多少个顶点？
查看练习答案与解析
答案：7 个 解析：$\frac{k(k-1)}{2} \geq 15 \implies k(k-1) \geq 30 \implies k=6$。加上孤立点 $6+1=7$。
三、综合应用题（本题满分 50 分）
1、（7分）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树 HT 的存储结构的终态，完成表 1。
表1 哈夫曼树HT的存储结构的终态
| 序号 | weight | parent | lchild | rchild |
|---|---|---|---|---|
| 1 (A) | 3 | 8 | 0 | 0 |
| 2 (B) | 12 | 12 | 0 | 0 |
| 3 (C) | 7 | 10 | 0 | 0 |
| 4 (D) | 4 | 9 | 0 | 0 |
| 5 (E) | 2 | 8 | 0 | 0 |
| 6 (F) | 8 | 10 | 0 | 0 |
| 7 (G) | 11 | 11 | 0 | 0 |
| 8 (N1) | 5 | 9 | 5 | 1 |
| 9 (N2) | 9 | 11 | 4 | 8 |
| 10 (N3) | 15 | 12 | 3 | 6 |
| 11 (N4) | 20 | 13 | 9 | 7 |
| 12 (N5) | 27 | 13 | 2 | 10 |
| 13 (N6) | 47 | 0 | 11 | 12 |
查看答案与解析
答案： 如上述表格所示。
解析： 本题考查哈夫曼树的贪心构建算法和数组存储结构。
- 第一步：叶子节点初始化： 将权值升序排列：$E(2), A(3), D(4), C(7), F(8), G(11), B(12)$。
- 第二步：循环合并最小节点：
- 选出 $E(2), A(3)$ 结合为 $N_1(5)$，父节点存入 8。
- 选出 $D(4), N_1(5)$ 结合为 $N_2(9)$，父节点存入 9。
- 选出 $C(7), F(8)$ 结合为 $N_3(15)$，父节点存入 10。
- 选出 $N_2(9), G(11)$ 结合为 $N_4(20)$，父节点存入 11。
- 选出 $B(12), N_3(15)$ 结合为 $N_5(27)$，父节点存入 12。
- 选出 $N_4(20), N_5(27)$ 结合为根节点 $N_6(47)$，父节点存入 13，其无双亲。
难度: ⭐⭐⭐
考点: #哈夫曼树 #静态链表 #最优二叉树
💡 学习锦囊
📖 相关公式与知识点:
- 哈夫曼树的叶子节点数为 $n$ 时，总结点数为 $2n-1$，非叶子节点为 $n-1$。
思路分析
在合并时，可以规定“左子树权值 $\leq$ 右子树权值”，严格落实静态存储中的左右指针索引。
易错点
- 混淆哈夫曼树的构建顺序，忘记每次都要选择当前权值最小的两个节点
- 存储结构中父节点和左右孩子的索引容易写错，需要仔细核对
🔄 举一反三
- 根据题目中的哈夫曼树，给出字符 A 的哈夫曼编码（约定左 0 右 1）。
查看练习答案与解析
答案：$001$解析：从根节点 13 往下找节点 1： $13 \xrightarrow{左(0)} 11 \xrightarrow{左(0)} 9 \xrightarrow{右(1)} 8 \xrightarrow{右(1)} 1$ （具体编码可能根据左右规定不同而有微调）。
2、（7 分）如下图所示的 AOE-网：
（1） 求这个工程最早可能在什么时间结束；
（2） 求每个活动的最早开始时间和最迟开始时间；
（3） 确定哪些活动是关键活动。
查看答案与解析
答案：
（1）工程最早结束时间： 12（时间单位）。
（2）各活动的最早开始时间 $e(i)$ 和最迟开始时间 $l(i)$：
| 活动 | $e(i)$ | $l(i)$ | 时间余量 $l(i)-e(i)$ |
|---|---|---|---|
| $a_1$ | 0 | 0 | 0 |
| $a_2$ | 0 | 2 | 2 |
| $a_3$ | 3 | 6 | 3 |
| $a_4$ | 2 | 4 | 2 |
| $a_5$ | 3 | 3 | 0 |
| $a_6$ | 2 | 9 | 7 |
| $a_7$ | 6 | 8 | 2 |
| $a_8$ | 9 | 9 | 0 |
（3）关键活动： $a_1, a_5, a_8$（时间余量为 0 的活动）。
求解步骤：
第一步：计算各顶点的最早发生时间 $ve$（正向递推）
- 设源点 $v_1$ 的 $ve(1) = 0$
- 按拓扑序递推：$ve(j) = \max\{ve(i) + w(i,j)\}$，其中 $w(i,j)$ 为有向边 $\langle v_i, v_j \rangle$ 的权值
- 汇点的 $ve$ 值即为工程最早结束时间
第二步：计算各顶点的最迟发生时间 $vl$（反向递推）
- 设汇点 $v_n$ 的 $vl(n) = ve(n)$
- 按逆拓扑序递推：$vl(i) = \min\{vl(j) - w(i,j)\}$
第三步：计算各活动的时间参数
- 活动 $a_k = \langle v_i, v_j \rangle$ 的最早开始时间：$e(k) = ve(i)$
- 活动 $a_k$ 的最迟开始时间：$l(k) = vl(j) - w(i,j)$
- 时间余量：$l(k) - e(k)$
第四步：确定关键活动和关键路径
- 时间余量为 0 的活动即为关键活动
- 关键活动构成的路径即为关键路径
解析： 关键路径是 AOE 网中从源点到汇点的最长路径，其长度决定了工程的最短完成时间。任何关键活动的延误都会导致整个工程延期。本题中关键路径为 $v_1 \to v_2 \to v_4 \to v_6$（对应活动 $a_1, a_5, a_8$），路径长度为 12。
难度: ⭐⭐⭐
考点: #AOE网 #关键路径 #工程管理
💡 学习锦囊
📖 相关公式与知识点:
- 关键路径是从起点到终点的最长路径
- 关键活动是总时差为0的活动
思路分析
解决AOE网问题的步骤：
- 计算每个顶点的最早发生时间ve
- 计算每个顶点的最迟发生时间vl
- 计算每个活动的最早开始时间e和最迟开始时间l
- 找出l-e=0的活动即为关键活动
易错点
- 混淆最早发生时间和最迟发生时间的计算顺序
- 忘记关键路径是最长路径而不是最短路径
🔄 举一反三
- 迪杰斯特拉与关键路径的核心异同点？
查看练习答案与解析
答案：最短路径关注单源点最短距离，基于贪心策略；关键路径求解的是有向无环图的最长路径，通常使用拓扑排序递推求解。
3、（7分）已知图的邻接矩阵如下图。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 6 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 8 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 9 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 10 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
查看答案与解析
答案：
- 深度优先生成树 (DFS Tree) 边集： $(1,7), (7,3), (3,4), (4,5), (5,6), (6,2), (5,10), (4,9), (3,8)$
- 广度优先生成树 (BFS Tree) 边集： $(1,7), (1,9), (7,3), (7,10), (9,5), (3,4), (3,8), (10,6), (6,2)$
解析：
- DFS 从 1 出发： 1 $\rightarrow$ 7 $\rightarrow$ 3 $\rightarrow$ 4 $\rightarrow$ 5 $\rightarrow$ 6 $\rightarrow$ 2（回溯到 5） 5 $\rightarrow$ 10（回溯到 4） 4 $\rightarrow$ 9（回溯到 3） 3 $\rightarrow$ 8。
- BFS 从 1 出发：
- 访问 1 的邻接点：7, 9
- 访问 7 的邻接点：3, 10
- 访问 9 的邻接点：5
- 访问 3 的邻接点：4, 8
- 访问 10 的邻接点：6
- 访问 6 的邻接点：2。
难度: ⭐⭐⭐
考点: #图的遍历 #DFS生成树 #BFS生成树
💡 学习锦囊
📖 相关公式与知识点:
- DFS 生成树：按深度优先遍历的访问顺序，保留首次访问的边
- BFS 生成树：按广度优先遍历的访问顺序，保留首次访问的边
- 生成树边数：$E = V - 1$
- 非连通图：每个连通分量各生成一棵树，构成生成森林
思路分析
从指定顶点出发，分别按 DFS 和 BFS 的访问顺序画出遍历路径，保留的边即构成对应的生成树。
🔄 举一反三
- 生成树的边数 $E$ 与图的顶点数 $V$ 有什么关系？
查看练习答案与解析
答案：$E = V - 1$
4、（7分）设哈希函数 $H(K)=3 K \pmod{11}$，哈希地址空间为 $0 \sim 10$，对关键字序列 $(32，13，49，24，38，21，4，12)$，按链地址法（拉链法）构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度 $ASL_{succ}$ 和 $ASL_{unsucc}$。
查看答案与解析
答案：链地址哈希表结构：
- $0$: 空
- $1$: $4$
- $2$: 空
- $3$: $12$
- $4$: $49 \rightarrow 38$
- $5$: 空
- $6$: $13 \rightarrow 24$
- $7$: 空
- $8$: $32 \rightarrow 21$
- $9$: 空
- $10$: 空
平均查找长度：
- $ASL_{succ} = 1.375$
- $ASL_{unsucc} = \frac{8}{11} \approx 0.727$
解析：
- 第一步：计算哈希地址： $H(32)=8, H(13)=6, H(49)=4, H(24)=6, H(38)=4, H(21)=8, H(4)=1, H(12)=3$。
- 第二步：求 $ASL_{succ}$： 每个链表的第 1 个元素查找需 1 次比较（共 5 个），第 2 个需 2 次比较（共 3 个）。 $ASL_{succ} = (1 \times 5 + 2 \times 3) / 8 = 1.375$。
- 第三步：求 $ASL_{unsucc}$： 失败时需要比较整条链的长度。总长度即元素个数 8，表长 11。 $ASL_{unsucc} = 8 / 11 \approx 0.727$。
难度: ⭐⭐⭐
考点: #散列表 #链地址法 #ASL计算
💡 学习锦囊
📖 相关公式与知识点:
- 链地址法：冲突元素挂在同一链表上，无需探测
- $\text{ASL}_{\text{成功}}$ = $\frac{\sum \text{各元素在链表中的位置}}{\text{元素总数}}$
- $\text{ASL}_{\text{失败}}$ = $\frac{\sum \text{各链表长度}}{\text{表长}}$
- 装填因子：$\alpha = n / m$，影响查找效率
思路分析
先按散列函数计算每个元素的地址，冲突时挂链表；再按链表位置统计比较次数，分别计算成功和失败的 ASL。
🔄 举一反三
- 采用开放定址的线性探测法解决该序列的哈希冲突，$ASL_{succ}$ 是多少？
查看练习答案与解析
答案：$1.375$
5、（7分）设待排序的关键字序列为 $\{12，6，16，30，10，20，2，18\}$，试分别写出使用以下排序方法第一趟排序结束后关键字序列的状态，并写出该算法是稳定的还是不稳定的。
- ① 希尔排序（ $d_1 = 3$ ）
- ② 冒泡排序
- ③ 快速排序
- ④ 二路归并排序
查看答案与解析
答案：
- ① 希尔排序：序列状态为 $\{2, 6, 16, 12, 10, 20, 30, 18\}$；不稳定。
- ② 冒泡排序：序列状态为 $\{6, 12, 16, 10, 20, 2, 18, 30\}$；稳定。
- ③ 快速排序：序列状态为 $\{2, 6, 10, 12, 30, 20, 16, 18\}$；不稳定。
- ④ 二路归并排序：序列状态为 $\{6, 12, 16, 30, 10, 20, 2, 18\}$；稳定。
解析：
- 希尔排序（$d=3$）：子序列为 $\{12,30,2\}$、$\{6,10,18\}$、$\{16,20\}$，分别排序后重组。
- 冒泡排序：最大的 30 沉底。
- 快速排序：以 12 为基准的一趟划分。
- 二路归并：两两归并。
难度: ⭐⭐⭐
考点: #排序算法 #稳定性 #趟次追踪
💡 学习锦囊
📖 相关公式与知识点:
- 直接插入排序：将元素插入已排序区，稳定，最好 $O(n)$
- 冒泡排序：相邻比较交换，稳定，每趟确定一个最值
- 简单选择排序：每趟选最小交换，不稳定
- 2路归并排序：分治合并，稳定，每趟 $O(n)$
- 快速排序：基准划分，不稳定，平均 $O(n\log n)$
思路分析
逐趟模拟各排序过程，注意第 2 趟结束时的序列状态。稳定性判断看相等元素是否保持原相对顺序。
🔄 举一反三
- 简单选择排序第一趟结束后状态是什么？
查看练习答案与解析
答案：$\{2, 6, 16, 30, 10, 20, 12, 18\}$
6、（7 分）设一棵二叉树的先序序列： $A B D F C E G H$ ，中序序列： $B F D A G E H C$
（1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。
（3）将这棵二叉树转换成对应的树（或森林）。
查看答案与解析
答案：(1) 二叉树形态：
- 根为 $A$，左子树根 $B$，右子树根 $C$。
- $B$ 只有右子树 $D$，$D$ 只有左子树 $F$。
- $C$ 只有左子树 $E$，$E$ 有左孩子 $G$，右孩子 $H$。
(2) 后序线索指向： 后序序列为 $F D B G H E C A$。
- $F$ 的左指针为空（指向 NULL），右指针指向 $D$。
- $B$ 的左指针为空，右指针指向 $G$。
- $G$ 的左指针为空，右指针指向 $H$。
- $H$ 的左指针为空，右指针指向 $E$。
(3) 转换后的森林：
- 树 1（根 $A$）：$A$ 的子节点为 $B, D$。$D$ 的子节点为 $F$。
- 树 2（根 $C$）：$C$ 的子节点为 $E$。$E$ 的子节点为 $G, H$。
解析：
- (1)：先序定根，中序定左右。
- (3)：左孩子为长子，右孩子为兄弟。
难度: ⭐⭐⭐
考点: #二叉树还原 #线索二叉树 #森林转换
💡 学习锦囊
📖 相关公式与知识点:
- 二叉树还原：前序+中序或后序+中序可唯一确定二叉树
- 线索二叉树：利用空指针域存储前驱/后继线索
- 森林与二叉树转换：森林中各树根互为右兄弟，左孩子-右兄弟表示法
- 转换规则：森林第一棵树对应二叉树根，其余树挂在右子树
思路分析
先由遍历序列还原二叉树，再画出线索树（空左指针指中序前驱，空右指针指中序后继），最后按左孩子-右兄弟规则将二叉树还原为森林。
🔄 举一反三
- 已知先序 $AB$，后序 $BA$，有多少种可能的二叉树？
查看练习答案与解析
答案：2 种（$B$ 可以是 $A$ 的左孩子或右孩子）
7、（8分）将序列 $(5，26，77，1，61，11)$ 构造成大根堆并实现排序，请画出初始形态和最终的大根堆，并写出第一趟堆排序的结果。
查看答案与解析
答案：
- 初始堆状态：$\{77, 61, 11, 1, 26, 5\}$
- 第一趟排序后：$\{61, 26, 11, 1, 5, 77\}$
解析：
- 建堆：从最后一个非叶子节点开始自底向上筛。
- 一趟排序：交换堆顶 77 与堆尾 5，缩小堆规模至 5，对 5 进行向下筛选调整。
难度: ⭐⭐⭐
考点: #堆排序 #大根堆
💡 学习锦囊
📖 相关公式与知识点:
- 堆：完全二叉树，大根堆中每个结点值 ≥ 其孩子值
- 建堆：从最后一个非叶结点开始，自底向上调整
- 堆排序：建堆后反复将堆顶与末尾交换，再调整堆
- 时间复杂度：建堆 $O(n)$，排序 $O(n\log n)$，不稳定
思路分析
先将序列视为完全二叉树，从最后一个非叶结点起逐个向下调整（sift down），使每个子树满足堆性质，最终建成大根堆。
🔄 举一反三
- 什么是堆排序的最佳时间复杂度？
查看练习答案与解析
答案：$O(n \log n)$
四、算法设计题（本题满分 20 分，每小题 10 分）
1、试写出折半查找的递归算法。
//r 是有序表，查找关键字 k，若查找成功，返回 k 所在位置，查找失败返回 0。int BinSearch（int r[ ]，int k，low，high）
查看答案与解析
答案：
int BinSearch(int r[], int k, int low, int high) {
if (low > high) {
return 0; // 查找失败，返回 0
}
int mid = low + (high - low) / 2; // 防止溢出的求中点方式
if (r[mid] == k) {
return mid; // 查找成功，返回位置
} else if (r[mid] > k) {
return BinSearch(r, k, low, mid - 1); // 在左半区继续查找
} else {
return BinSearch(r, k, mid + 1, high); // 在右半区继续查找
}
}解析： 本题考查折半查找（二分查找）的递归实现。
- 第一步：确定递归出口：当
low > high时，说明当前子表为空，查找失败，返回 0。 - 第二步：计算中点：$mid = (low + high) / 2$。
- 第三步：递归分支判断：
- 若 $r[mid] == k$，查找成功。
- 若 $r[mid] > k$，说明 $k$ 在 $mid$ 的左侧，更新 $high = mid - 1$ 递归。
- 若 $r[mid] < k$，说明 $k$ 在 $mid$ 的右侧，更新 $low = mid + 1$ 递归。
难度: ⭐⭐
考点: #二分查找 #递归算法 #查找算法
💡 学习锦囊
📖 相关公式与知识点:
- 递归折半查找的平均时间复杂度为 $O(\log n)$。
- 前提必须是顺序存储结构且关键字有序。
易错点
递归调用的参数更新一定要写对，左边是 mid - 1，右边是 mid + 1。
🔄 举一反三
- 如何将折半查找改写为非递归算法？
查看练习答案与解析
答案：
cint BinSearch_NonRec(int r[], int k, int n) { int low = 1, high = n, mid; while (low <= high) { mid = (low + high) / 2; if (r[mid] == k) return mid; else if (r[mid] > k) high = mid - 1; else low = mid + 1; } return 0; }
2、 设计算法：统计单链表 HL 中结点的值等于给定值 $\mathbf { X }$ 的结点数。int CountX(LNode* HL,ElemType x)
查看答案与解析
答案：
int CountX(LNode* HL, ElemType x) {
int count = 0;
LNode *p = HL; // 假设 HL 为首元结点指针。如果 HL 是头结点，则应写 p = HL->next。
while (p != NULL) {
if (p->data == x) {
count++;
}
p = p->next; // 移动到下一个结点
}
return count;
}解析： 本题考查单链表的基本遍历操作。
- 第一步：初始化计数器：
count = 0。 - 第二步：指针遍历：使用指针
p从头指针开始顺序访问链表。 - 第三步：条件判断：每访问一个结点，比对数据域，相同则
count自增，直至p为空。
难度: ⭐⭐
考点: #单链表 #算法设计 #链表遍历
💡 学习锦囊
📖 相关公式与知识点:
- 单链表结构：每个结点含
data和next指针 - 链表遍历：从头结点沿
next依次访问 - 删除结点：
pre->next = p->next; free(p); - 时间复杂度：遍历 $O(n)$，删除需找前驱
思路分析
遍历链表，对每个结点判断是否满足删除条件，维护前驱指针 pre 以便删除操作。注意头结点和尾结点的边界处理。
🔄 举一反三
- 设计算法：删除单链表中所有值等于 X 的结点。
查看练习答案与解析
答案：
cvoid DeleteX(LNode* &HL, ElemType x) { LNode *p = HL, *pre = NULL; while (p != NULL) { if (p->data == x) { if (pre == NULL) { // 删除头结点 HL = p->next; free(p); p = HL; } else { pre->next = p->next; free(p); p = pre->next; } } else { pre = p; p = p->next; } } }