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

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

一、应用题 (本大题共 7 小题，每小题 10 分，共 70 分)

1. 已知一棵二叉树的中根序列和后根序列分别为 B、D、C、E、A、F、H、G 和 D、E、C、B、H、G、F、A。 要求： (1) 画出二叉树形状示意图； (2) 分别求先根序列、层次遍历序列。

查看答案与解析

答案：

(1) 二叉树形状示意图如下：

      A
     / \
    B   F
     \   \
      C   G
     / \   /
    D   E H

(2)

• 先根序列：A, B, C, D, E, F, G, H
• 层次遍历序列：A, B, F, C, G, D, E, H

解析：

第一步：由后根序列确定根结点 后根序列的最后一个元素一定是二叉树的根结点。在 D, E, C, B, H, G, F, A 中，最后一个元素是 A。

第二步：在中根序列中划分左右子树 在中根序列 B, D, C, E, A, F, H, G 中找到根结点 A：

• A 左边的序列 {B, D, C, E} 为左子树的中根序列。
• A 右边的序列 {F, H, G} 为右子树的中根序列。

第三步：递归构建左子树

• 左子树的中根序列为 {B, D, C, E}，对应的后根序列为 {D, E, C, B}。根为 B。
• 在中根序列中，B 无左子树，{D, C, E} 为 B 的右子树的中根序列。
• 处理 {D, C, E}（后根 {D, E, C}）：根为 C，左为 D，右为 E。

第四步：递归构建右子树

• 右子树的中根序列为 {F, H, G}，对应的后根序列为 {H, G, F}。根为 F。
• 在中根序列中，F 无左子树，{H, G} 为 F 的右子树的中根序列。
• 处理 {H, G}（后根 {H, G}）：根为 G，左为 H，右为空。

---

难度: ⭐⭐
考点: #二叉树重建 #遍历序列 #树的性质

💡 学习锦囊

📖 相关公式与知识点:

• 先根遍历：根 -> 左 -> 右
• 中根遍历：左 -> 根 -> 右
• 后根遍历：左 -> 右 -> 根

思路分析

利用后根序列定位“根”，再利用中根序列划分“左右”，递归执行。

🔄 举一反三

1. 已知二叉树先序序列为 A, B, D, E, C, F，中序序列为 D, B, E, A, C, F，求其后序序列。
   查看练习答案与解析

   答案：D, E, B, F, C, A
   解析：

   • 先序确定根为 A。中序划分出左 {D, B, E}，右 {C, F}。
   • 左子树先序 {B, D, E}，根为 B；中序 {D, B, E} 划分出左 D，右 E。
   • 右子树先序 {C, F}，根为 C；中序 {C, F} 划分出右 F。
   • 后序遍历结果为 D, E, B, F, C, A。

---

2. 设通信电文使用的字符集为 $\{ \mathbf { a } , \mathbf { b } , \mathbf { c } , \mathbf { d } , \mathbf { e } , \mathbf { f } , \mathbf { g } \}$，字符的哈夫曼编码依次为：0110，10，110，111，00，0111 和 010。 要求： (1) 请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符； (2) 若字符在电文中出现的频度分别为：3，35，13，15，20，5 和 9，求该哈夫曼树的带权路径长度（WPL）。

查看答案与解析

答案：

(1) 根据编码规则（左 0 右 1），哈夫曼树结构如下：

          [ ]
        /     \
      0        1
    /   \     /  \
   0     1   b    [ ]
  /     / \      /   \
 e     g   [ ]  c     d
          /   \
         a     f

叶子结点对应关系：

• a: 0110, b: 10, c: 110, d: 111, e: 00, f: 0111, g: 010

(2) WPL 计算： $\text{WPL} = 3\times4 + 35\times2 + 13\times3 + 15\times3 + 20\times2 + 5\times4 + 9\times3 = \mathbf{253}$

---

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

💡 学习锦囊

📖 相关公式与知识点:

• $\text{WPL} = \sum (W_i \times L_i)$

思路分析

从根出发，遇到 0 走左，遇到 1 走右，复原树形。

🔄 举一反三

1. 给定权值 $\{5, 29, 7, 8, 14, 23, 3, 11\}$，构造哈夫曼树并求 WPL。
   查看练习答案与解析

   答案：$\text{WPL} = 271$
   解析：

   • 每次选最小的两个合并：
     • {3, 5} -> 8
     • {7, 8} -> 15
     • {8, 11} -> 19
     • {14, 15} -> 29
     • {19, 23} -> 42
     • {29, 29} -> 58
     • {42, 58} -> 100
   • 计算各叶子深度的乘积和即为 271。

---

3. 已知某带权图如题 3 图所示。按照普里姆（Prim）算法原理从顶点 A 开始求最小生成树。在算法执行之初，顶点的集合 $U = \{A, B\}$，边的集合 $TE = \{(A, B)\}$。 要求：按照最小生成树的生成过程，分步给出加入顶点和边以后的集合。

查看答案与解析

答案：

• 初始：$U = \{A, B\}$, $TE = \{(A, B)\}$
• 步骤 1：加入顶点 G，边 (A, G)。$U = \{A, B, G\}$, $TE = \{(A, B), (A, G)\}$
• 步骤 2：加入顶点 I，边 (G, I)。$U = \{A, B, G, I\}$, $TE = \{(A, B), (A, G), (G, I)\}$
• 步骤 3：加入顶点 E，边 (I, E)。$U = \{A, B, G, I, E\}$, $TE = \{(A, B), (A, G), (G, I), (I, E)\}$
• 步骤 4：加入顶点 D，边 (E, D)。$U = \{A, B, G, I, E, D\}$, $TE = \{(A, B), (A, G), (G, I), (I, E), (E, D)\}$
• 步骤 5：加入顶点 C，边 (D, C)。$U = \{A, B, G, I, E, D, C\}$, $TE = \{(A, B), (A, G), (G, I), (I, E), (E, D), (D, C)\}$
• 步骤 6：加入顶点 H，边 (C, H)。$U = \{A, B, G, I, E, D, C, H\}$, $TE = \dots \cup \{(C, H)\}$
• 步骤 7：加入顶点 F，边 (I, F)。$U = \{A, B, G, I, E, D, C, H, F\}$, $TE = \dots \cup \{(I, F)\}$

---

难度: ⭐⭐⭐
考点: #Prim算法 #最小生成树

💡 学习锦囊

易错点

必须实时更新候选边集，且只选连接 $U$ 与 $V-U$ 的最短边。

🔄 举一反三

1. 使用 Kruskal 算法求解上述图的最小生成树边顺序。
   查看练习答案与解析

   答案：(G, I)[1], (E, D)[1], (I, E)[2], (A, B)[2], (C, D)[2], (C, H)[2], (A, G)[3], (I, F)[5]（部分权值相等边顺序可微调）。 解析：按权值从小到大选边，避免成环。

---

4. 已知某带权图如题 4 图所示，按照迪杰斯特拉（Dijkstra）算法原理求该图中从顶点 a 到其余各顶点的最短路径。 要求：按算法求解过程依次写出各条最短路径及其长度。

查看答案与解析

答案：

步骤	$S$	$dist[b]$	$dist[c]$	$dist[d]$	$dist[e]$	$dist[f]$	选点
初始	$\{a\}$	20	60	$\infty$	10	65	e
1	$\{a, e\}$	20	60	$\infty$	-	30	b
2	$\{a, e, b\}$	-	50	$\infty$	-	30	f
3	$\{a, e, b, f\}$	-	45	110	-	-	c
4	$\{a, e, b, f, c\}$	-	-	85	-	-	d

结果：

• a -> e: 10, a -> e
• a -> b: 20, a -> b
• a -> f: 30, a -> e -> f
• a -> c: 45, a -> e -> f -> c
• a -> d: 85, a -> e -> f -> c -> d

---

难度: ⭐⭐⭐
考点: #Dijkstra算法 #最短路径

💡 学习锦囊

📖 相关公式与知识点:

• Dijkstra 算法：贪心策略，每次从未确定最短路径的顶点中选取距离最小的顶点加入集合 S
• 松弛操作：若 dist[v] > dist[u] + w(u,v)，则更新 dist[v]
• 不适用含负权边的图

思路分析

逐步扩展已确定最短路径的顶点集合 S，每步选最小 dist 的未访问顶点，再对其邻接点做松弛更新。

🔄 举一反三

1. 若将边 e -> f 的权值改为 60，求 a 到 f 的最短路径。
   查看练习答案与解析

   答案：长度 65，路径为 a -> f 或 a -> e -> f。 解析：通过 e 中转代价为 10+60=70，大于直连的 65。

---

5. 已知带权图如题 5 图所示，求该图的一棵最小生成树。

查看答案与解析

答案：

边集：{(B, F), (D, K), (F, H), (A, C), (E, K), (B, C), (C, D)} 总权值：26

---

难度: ⭐⭐
考点: #最小生成树

💡 学习锦囊

📖 相关公式与知识点:

• Prim 算法：从某一顶点出发，每次选代价最小的边连接新顶点，时间复杂度 $O(|V|^2)$
• Kruskal 算法：按边权从小到大选边，用并查集判环，时间复杂度 $O(|E|\log|E|)$
• MST 性质：n 个顶点的连通图最小生成树有 n-1 条边

思路分析

Prim 适合稠密图，Kruskal 适合稀疏图。本题顶点少、边较多，两种方法均可。

🔄 举一反三

1. 简述 Prim 与 Kruskal 算法的时间复杂度及适用场景。
   查看练习答案与解析

   答案：

   • Prim: $O(|V|^2)$，适合稠密图。
   • Kruskal: $O(|E|\log|E|)$，适合稀疏图。

---

6. 已知散列函数为 $H(key) = key \% 11$，散列表长度为 11 (散列地址空间为 0..10)，待散列序列为：(25，48，32，50，68，34，56，77，98)。 要求： (1) 根据以上条件构造散列表，并用线性探测法解决地址冲突； (2) 计算平均查找长度 ASL（包括成功和失败）； (3) 若要用该散列表查找元素 48 和 66，分别给出所需的比较次数。

查看答案与解析

答案：

(1) 散列表：[0]:77, [1]:34, [2]:68, [3]:25, [4]:48, [5]:56, [6]:50, [7]:98, [10]:32

(2)

• $\text{ASL}_{\text{成功}}$ = $21 / 9 \approx \mathbf{2.33}$
• $\text{ASL}_{\text{失败}}$ = $56 / 11 \approx \mathbf{5.09}$

(3)

• 48：1 次
• 66：9 次

---

难度: ⭐⭐⭐
考点: #散列表 #线性探测

💡 学习锦囊

📖 相关公式与知识点:

• 散列函数：$H(key) = key \% m$，m 为表长
• 线性探测：冲突时依次探测 $H(key)+1, H(key)+2, \ldots$
• $\text{ASL}_{\text{成功}}$ = $\frac{\sum \text{各元素比较次数}}{\text{元素个数}}$
• $\text{ASL}_{\text{失败}}$ = $\frac{\sum \text{各位置到第一个空位的比较次数}}{\text{表长}}$

思路分析

先逐个插入元素并记录探测次数，再分别按成功/失败的定义计算 ASL。失败 ASL 需对每个散列地址算到空位的距离。

🔄 举一反三

1. 若改用链地址法解决冲突，求成功查找的 ASL。
   查看练习答案与解析

   答案：$\text{ASL}_{\text{成功}} = (1\times7 + 2\times2) / 9 = 11/9 \approx 1.22$。 解析：冲突的 56 和 98 挂在相应链表第二位。

---

7. 已知序列 {15, 18, 60, 41, 6, 32, 83, 75, 95}。请给出按照快速排序算法原理对该序列作排序时的每一趟的结果。

查看答案与解析

答案：

• 初始：[15], 18, 60, 41, 6, 32, 83, 75, 95
• 第一趟：{6}, 15, {60, 41, 18, 32, 83, 75, 95}
• 第二趟：{6}, 15, {32, 41, 18}, 60, {83, 75, 95}
• 第三趟：{6}, 15, {18}, 32, {41}, 60, {75}, 83, {95}

---

难度: ⭐⭐
考点: #快速排序

💡 学习锦囊

📖 相关公式与知识点:

• 快速排序：选基准（pivot），将序列分为小于基准和大于基准两部分，递归排序
• 最好/平均时间复杂度：$O(n\log n)$
• 最坏时间复杂度：$O(n^2)$（序列已有序时）
• 空间复杂度：$O(\log n)$（递归栈深度）

思路分析

每趟以第一个元素为基准，从两端向中间扫描并交换，最终基准归位，左右子序列递归处理。

🔄 举一反三

1. 快速排序在最坏情况下的时间复杂度是多少？如何避免？
   查看练习答案与解析

   答案：$O(n^2)$。可通过“三数取中法”或随机选择基准来避免。

---

二、 分析题 (本大题共 2 小题，共 15 分)

1. （8 分）设栈 $S = (1, 2, 3, 4, 5, 6, 7)$，其中 7 为栈顶元素。 （1）写出调用 AlgorithmA(&S) 后的 S； （2）简述函数 AlgorithmA 中第 1 个循环语句的功能。

void AlgorithmA (Stack *S) {
    Queue Q;
    Stack T;
    int i = 0;
    InitQueue(&Q);
    InitStack(&T);
    while(!StackEmpty(S)) {
        if (i++ % 2 == 0) Push(&T, Pop(S));
        else EnQueue(&Q, Pop(S));
    }
    while(!StackEmpty(&T))
        Push(S, Pop(&T));
    while(!QueueEmpty(&Q))
        Push(S, DeQueue(&Q));
}

查看答案与解析

答案：

(1) $S = \mathbf{(1, 3, 5, 7, 6, 4, 2)}$，栈顶为 2。 (2) 功能：按出栈顺序的奇偶位置，将栈 S 分流至栈 T 和队列 Q。

---

难度: ⭐⭐⭐
考点: #栈与队列

💡 学习锦囊

📖 相关公式与知识点:

• 栈：后进先出（LIFO），只能从栈顶操作
• 队列：先进先出（FIFO），从队尾入、队头出
• 栈与队列混合：常用于分流、逆序、缓冲等场景

思路分析

跟踪每个元素出栈后进入 T 还是 Q，再按 T→S、Q→S 的顺序回压，即可得到最终栈状态。

🔄 举一反三

1. 如何仅用一个辅助队列实现栈的逆置？
   查看练习答案与解析

   答案：将栈中所有元素依次出栈并入队，再将队列中所有元素依次出队并压回栈。

---

2. （7 分）已知二叉树的存储结构为二叉链表，其类型定义如下：

typedef struct NodeType {
    DataType data;
    struct NodeType *lchild, *rchild;
} BinTNode, *BinTree;

阅读算法 AlgorithmB，并回答下列问题： (1) 对于如图所示的二叉树，画出执行算法 AlgorithmB 的结果； (2) 简述算法 AlgorithmB 的功能。

查看答案与解析

答案：

(1) 结构：

        H
      /   \
     G     D
    /     / \
   F     C   B
    \       /
     E     A

(2) 功能：递归实现二叉树左右子树的镜像互换。

---

难度: ⭐⭐
考点: #递归算法 #二叉树

💡 学习锦囊

📖 相关公式与知识点:

• 二叉树镜像：交换每个结点的左右子树
• 递归三要素：终止条件、递归体、返回值
• 二叉链表：每个结点含 lchild 和 rchild 指针

思路分析

递归交换左右子树：先递归处理左右子树，再交换当前结点的左右指针，即可实现镜像。

🔄 举一反三

1. 编写递归算法计算二叉树的叶子结点个数。
   查看练习答案与解析

   答案： if(bt==NULL) return 0;if(bt->lchild==NULL && bt->rchild==NULL) return 1;return CountLeaf(bt->lchild) + CountLeaf(bt->rchild);

---

三、 设计题 (本大题共 2 小题，共 15 分)

1. （8 分）试设计一个算法 void DeleteRepuNode (SingLinkedList *head) 删除该单链表中数据域(data)重复的结点。

查看答案与解析

答案：

void DeleteRepuNode (SingLinkedList *head) {
    if (head == NULL || head->next == NULL) return;
    SingLinkedList *p = head->next;
    while (p != NULL) {
        SingLinkedList *pre = p;
        SingLinkedList *q = p->next;
        while (q != NULL) {
            if (q->data == p->data) {
                pre->next = q->next;
                free(q);
                q = pre->next;
            } else {
                pre = q;
                q = q->next;
            }
        }
        p = p->next;
    }
}

---

难度: ⭐⭐⭐
考点: #链表去重

💡 学习锦囊

📖 相关公式与知识点:

• 单链表遍历：从头结点依次沿 next 指针访问
• 删除结点：pre->next = q->next; free(q);
• 去重策略：对外层每个结点，内层遍历其后所有结点，删除数据域相同的结点

思路分析

双重循环：外层遍历每个结点作为"基准"，内层扫描其后的所有结点，遇到重复则删除。时间复杂度 $O(n^2)$。

🔄 举一反三

1. 试设计一个算法，逆置一个带头结点的单链表。
   查看练习答案与解析

   答案： p = head->next; head->next = NULL;while(p) { q = p->next; p->next = head->next; head->next = p; p = q; }

---

2. （7 分）试设计一个算法 int CountBinTreeNodebyData (BinTree BT, DataType X)，计算该二叉树数据域(data)为 X 的结点个数。

查看答案与解析

答案：

int CountBinTreeNodebyData (BinTree BT, DataType X) {
    if (BT == NULL) return 0;
    int count = 0;
    if (BT->data == X) count = 1;
    return count + CountBinTreeNodebyData(BT->lchild, X) + CountBinTreeNodebyData(BT->rchild, X);
}

---

难度: ⭐⭐
考点: #二叉树遍历

💡 学习锦囊

📖 相关公式与知识点:

• 二叉树递归遍历：先序（根左右）、中序（左根右）、后序（左右根）
• 递归统计：当前结点满足条件则 count+1，再递归左右子树
• 终止条件：BT == NULL 时返回 0

思路分析

递归遍历整棵树，对每个结点判断 data == X，满足则计数加 1，最终累加左右子树的结果。

🔄 举一反三

1. 试设计一个算法，求解二叉树的深度。
   查看练习答案与解析

   答案： if(BT==NULL) return 0;int ld = GetDepth(BT->lchild);int rd = GetDepth(BT->rchild);return (ld > rd ? ld : rd) + 1;