严蔚敏数据结构习题答案：从代码审查清单到测试用例的进阶用法

简介：这份PDF是清华大学出版社《数据结构（C语言版）第三版》的习题参考答案，面向正在学习数据结构课程的高校学生、考研备考者及相关自学者，用于课后练习核对与知识点查漏补缺。资源包内共1个PDF文件，约445KB，篇幅紧凑便于随时查阅。内容按章节组织，覆盖数据结构基本概念、算法与程序设计、时间复杂度与空间复杂度、顺序与链式等存储实现方式，以及顺序表、链表、树、图等典型应用，并配有选择题、填空题、名词解释与参考程序代码，可帮助读者对照教材逐题复盘解题思路、理解算法实现细节。目前已有2147人学习下载，适合需要系统梳理基础概念、巩固C语言算法实现能力的读者参考使用。

1. 从一份习题答案说起：为什么我建议你把它当“代码审查清单”用

很多人拿到《数据结构(C语言版)第三版》清华大学出版社的习题参考答案 PDF，第一反应是“对答案”。但我拆完这份 100 多页的答案后发现，它真正的价值不在答案本身，而在于它把严蔚敏那套经典教材里最容易翻车的几个环节——时间复杂度推导、栈与队列的边界条件、二叉树递归、图的邻接表建表——全部用可运行的 C 代码摊开了。换句话说，这是一份被低估的“代码审查清单”。适合谁？正在跟严蔚敏教材、准备 408 数据结构、或者用 C 语言手写链表/树/图但总在指针和边界上翻车的人。下面我按“答案里写了什么 → 怎么把它跑起来 → 哪些地方会踩坑”的顺序拆一遍。

2. 答案里的三类硬骨头：时间复杂度、指针操作、递归边界

2.1 时间复杂度不是背出来的，是从语句结构推出来的

答案 1.4 给了五段语句，要求写出时间复杂度，结果分别是 O(n²)、O(n²)、O(n²)、O(n-1)、O(n³)。很多人直接背结论，但这份答案的价值在于它逼你回到语句本身去数循环层数。比如三重循环嵌套且每层都跟 n 相关，基本就是 O(n³)；两层循环但内层跟外层变量挂钩，要具体看是等差数列还是等比数列。

我一般会这样验证：把每段代码抄进一个.c文件，在循环体里加一个计数器，跑 n=10、100、1000 三组，看计数器增长曲线。如果 n 翻 10 倍、计数翻 100 倍，那就是 O(n²)，不用猜。

// 验证 O(n^2) 的典型结构 #include <stdio.h> int main() { int n = 100, count = 0; for (int i = 0; i < n; i++) // 外层 n 次 for (int j = 0; j < n; j++) // 内层 n 次 count++; // 总执行 n*n 次 printf("n=%d, count=%d\n", n, count); return 0; }

这段代码跑出来 count 恒等于 n²，这就是 O(n²) 的物理含义。参数上唯一要改的是 n，建议至少跑三组不同量级，否则单点数据看不出阶数。答案里 1.4 的第 (4) 小题是 O(n-1)，本质还是 O(n)，因为大 O 只保留最高阶、去掉常数系数，这一点在 408 选择题里反复考。

2.2 指针操作：答案 2.2 填空第 (9) 题是链表插入的命门

答案 2.2 第 (9) 题填的是s->next=p->next; p->next=s;，这是单链表在 p 结点之后插入 s 结点的标准两步。顺序绝对不能反——如果先写p->next=s，那 p 原来的后继就丢了，s->next 只能指向自己，形成自环。这是血泪经验，我见过太多人在手写代码时把这两行写反，编译能过，跑起来死循环。

// 单链表在 p 之后插入 s，顺序不能反 s->next = p->next; // 第一步：先让新结点接住后面的链 p->next = s; // 第二步：再让前驱指向新结点

逻辑说明：第一步保存了 p 原来的后继地址，第二步才断开 p 与后继的连接。如果反过来，第一步就把 p->next 改成了 s，第二步再执行s->next=p->next时，p->next 已经是 s 了，等于s->next=s。参数上没什么可调的，但要注意 p 不能是 NULL，否则p->next直接段错误。答案 2.2 第 (10) 题填s->next，考的是删除结点时怎么接链，同理。

2.3 递归边界：二叉树结点计数为什么容易多算一个

答案 5.12 给了计算二叉树结点总数的递归函数，核心是return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;，空树返回 0。这个 +1 就是当前结点本身。很多人写递归时忘了这个 +1，结果算出来永远比真实结点数少一个根。

int NodeCount(BiTree T) { if (T == NULL) return 0; // 空树贡献 0 if (T->lchild == NULL && T->rchild == NULL) return 1; // 叶子结点贡献 1 return NodeCount(T->lchild) + NodeCount(T->rchild) + 1; // 左右子树 + 自己 }

参数说明：T 是二叉链表根指针，递归出口有两个——空指针和叶子。注意答案里叶子单独判断其实可以省略，因为叶子走最后一行也是0+0+1=1，结果一样。但单独写出来可读性更好，也方便你在调试时打日志。常见误用是把+1写成+2或漏掉，跑一棵三结点的小树就能验证：根 + 左 + 右，正确输出 3。

3. 把答案里的代码跑起来：从单文件到可调试工程

3.1 先解决“答案代码跑不通”的编译问题

这份答案里的代码是典型的老式 C 风格，main()不写返回类型、scanf里用%f读 int、数组不声明长度直接float a[]。直接抄进现代编译器（gcc 默认 C17）会报一堆 warning 甚至 error。我的做法是统一加三样东西：#include <stdio.h>、int main(void)、数组给一个足够大的固定长度。

// 答案 2.3 顺序表逆置，改造为可编译版本 #include <stdio.h> #define MAXN 100 int main(void) { int i, n; float t, a[MAXN]; printf("n="); scanf("%d", &n); // 原答案用 %f 读 n，改为 %d for (i = 0; i < n; i++) scanf("%f", &a[i]); for (i = 0; i <= (n - 1) / 2; i++) { t = a[i]; a[i] = a[n - 1 - i]; a[n - 1 - i] = t; } for (i = 0; i < n; i++) printf("%f ", a[i]); return 0; }

逻辑说明：逆置只需要交换前一半和后一半对应位置，循环上界是(n-1)/2。参数上MAXN按你实际数据量调，答案里没给上界是历史遗留问题。注意scanf("%d", &n)这里原答案写的是%f，这是那个年代教材的常见笔误，不改的话 n 会读成一个浮点垃圾值，循环直接失控。

3.2 用 gcc 加 sanitizer 抓指针越界

链表、树、图这些带指针的代码，光看输出正常不代表没越界。我一般编译时加-fsanitize=address，让运行时直接报出哪一行访问了非法内存。

gcc -g -fsanitize=address -o list_test list_test.c ./list_test

参数说明：-g保留调试符号，-fsanitize=address开启地址检查。如果链表插入顺序写反导致自环，程序会在遍历时卡死，sanitizer 不一定报错，但你可以加一个步数上限来兜底。常见做法是在遍历循环里加if (++step > 10000) { printf("possible cycle\n"); break; }，这样自环会立刻暴露而不是等到超时。

3.3 图的邻接矩阵和邻接表：答案 6.9 和 6.10 的建表差异

答案 6.9 讲邻接矩阵建图，无向图对称赋值G->edges[i][j]=G->edges[j][i]=1；6.10 讲邻接表建图，每个顶点挂一个单链表。两者选型理由很直接：顶点少边多（稠密图）用邻接矩阵，判断两点是否相邻 O(1)；顶点多边少（稀疏图）用邻接表，省空间但判断相邻要遍历链表。

答案 6.10 的建表代码里有个细节：先G->adjlist[m].firstedge=NULL把所有头指针置空，再读顶点符号，最后读边。顺序不能乱，否则头指针是野值，插入时直接崩。参数上边数 e 和顶点数 n 都要做非负校验，答案里写了if(n<0) return -1;，这个习惯要保留。

4. 避坑与排查：五条我实际踩过的记录

4.1 现象：栈的填空题 (R-F+M)%M 抄成 (R-F)%M

原因：循环队列求元素个数时，rear 可能小于 front，直接相减为负。解决：加 M 再对 M 取模，保证结果落在 [0, M-1]。答案 3.2 第 (5) 题就是这个公式，考试和实际写环形缓冲区都会用到。

4.2 现象：二叉树先序和中序相同，判断成“只有根结点”

原因：答案 5.7 的结论是“空树或缺左子树的单支树”，漏了单支树这一大类。解决：画一棵只有右孩子的三结点树，先序和中序确实相同，但结点不止一个。判断时要考虑所有结点都没有左子树的情况。

4.3 现象：哈夫曼编码答案 5.20 的 0/1 分配左右搞反

原因：哈夫曼树左右子树谁标 0 谁标 1 没有强制规定，但同一份答案里必须一致。解决：答案里写的是左分支标 1、右分支标 0，你如果按常规左 0 右 1，编码会完全不同但前缀性质不变。对答案时先确认标法，别急着判错。

4.4 现象：图的深度优先遍历序列和答案对不上

原因：答案 6.5 给了多个合法序列，因为邻接表的边插入顺序不同，遍历时选邻居的顺序就不同。解决：DFS 序列不唯一，只要满足“一条路走到黑再回溯”就是对的。对答案时看是否覆盖所有顶点、是否合法，而不是逐位比对。

4.5 现象：Prim 算法 Low/Close 表填到一半就乱了

原因：答案 6.7 的表格每轮要更新所有未加入顶点的 Low 值，漏更新一个就会连锁错。解决：每轮先找当前 Low 最小的未加入顶点，加入集合 U，然后用新加入的顶点去松弛其他顶点的 Low。建议用纸笔逐轮画，别跳步。

5. 进阶用法：把答案当测试用例，反推自己的实现

答案里最值钱的不是最终结果，而是那些中间过程——Low/Close 表的每一轮、DFS 的每一步栈变化、哈夫曼树的每次合并。我现在的习惯是：自己先写一遍链表、树、图的实现，然后把答案里的输入数据抄过来跑，对比中间状态而不是只看最终输出。比如答案 6.7 的最小生成树，我会在代码里每加入一条边就打印当前 U 集合和 T 集合，跟答案表格逐轮对。对不上就停下来查，而不是跑完看结果不对再回头找。

再进一步，可以把答案里的选择题和填空题转成单元测试。比如栈的合法出栈序列，答案 3.5 列了 14 种，我就写一个函数枚举所有 push/pop 组合，看是否正好产出这 14 种。这样既验证了答案，也验证了自己的栈实现。

// 用递归枚举所有合法出栈序列，验证答案 3.5 的 14 种 #include <stdio.h> int stack[10], top = -1, out[10], outn = 0; int in_seq[4] = {1,2,3,4}, inn = 0; void dfs(int pushed) { if (outn == 4) { for (int i=0;i<4;i++) printf("%d", out[i]); printf("\n"); return; } if (pushed < 4) { stack[++top] = in_seq[pushed]; dfs(pushed+1); top--; } if (top >= 0) { int t = stack[top--]; out[outn++] = t; dfs(pushed); outn--; stack[++top] = t; } } int main(void) { dfs(0); return 0; }

这段代码会输出所有合法出栈序列，数量应该正好是卡特兰数 C(4)=14，跟答案 3.5 对得上。参数上把 4 改成 n 就能验证 n 个元素的出栈序列数。从那以后我每次对答案都强制走一遍“自己实现 → 抄输入 → 比中间状态 → 转测试用例”的流程，比单纯对最终结果靠谱得多。希望帮到你。

本文还有配套的精品资源，点击获取