简介这份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文件在循环体里加一个计数器跑 n10、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-nextp-next; p-nexts;这是单链表在 p 结点之后插入 s 结点的标准两步。顺序绝对不能反——如果先写p-nexts那 p 原来的后继就丢了s-next 只能指向自己形成自环。这是血泪经验我见过太多人在手写代码时把这两行写反编译能过跑起来死循环。// 单链表在 p 之后插入 s顺序不能反 s-next p-next; // 第一步先让新结点接住后面的链 p-next s; // 第二步再让前驱指向新结点逻辑说明第一步保存了 p 原来的后继地址第二步才断开 p 与后继的连接。如果反过来第一步就把 p-next 改成了 s第二步再执行s-nextp-next时p-next 已经是 s 了等于s-nexts。参数上没什么可调的但要注意 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 是二叉链表根指针递归出口有两个——空指针和叶子。注意答案里叶子单独判断其实可以省略因为叶子走最后一行也是0011结果一样。但单独写出来可读性更好也方便你在调试时打日志。常见误用是把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 抓指针越界链表、树、图这些带指针的代码光看输出正常不代表没越界。我一般编译时加-fsanitizeaddress让运行时直接报出哪一行访问了非法内存。gcc -g -fsanitizeaddress -o list_test list_test.c ./list_test参数说明-g保留调试符号-fsanitizeaddress开启地址检查。如果链表插入顺序写反导致自环程序会在遍历时卡死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]16.10 讲邻接表建图每个顶点挂一个单链表。两者选型理由很直接顶点少边多稠密图用邻接矩阵判断两点是否相邻 O(1)顶点多边少稀疏图用邻接表省空间但判断相邻要遍历链表。对比项邻接矩阵邻接表空间O(n²)O(ne)判断边O(1)O(度)遍历邻居O(n)O(度)适用稠密图稀疏图答案 6.10 的建表代码里有个细节先G-adjlist[m].firstedgeNULL把所有头指针置空再读顶点符号最后读边。顺序不能乱否则头指针是野值插入时直接崩。参数上边数 e 和顶点数 n 都要做非负校验答案里写了if(n0) return -1;这个习惯要保留。4. 避坑与排查五条我实际踩过的记录4.1 现象栈的填空题 (R-FM)%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 i0;i4;i) printf(%d, out[i]); printf(\n); return; } if (pushed 4) { stack[top] in_seq[pushed]; dfs(pushed1); 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 个元素的出栈序列数。从那以后我每次对答案都强制走一遍“自己实现 → 抄输入 → 比中间状态 → 转测试用例”的流程比单纯对最终结果靠谱得多。希望帮到你。本文还有配套的精品资源点击获取
严蔚敏数据结构习题答案：从代码审查清单到测试用例的进阶用法
简介这份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文件在循环体里加一个计数器跑 n10、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-nextp-next; p-nexts;这是单链表在 p 结点之后插入 s 结点的标准两步。顺序绝对不能反——如果先写p-nexts那 p 原来的后继就丢了s-next 只能指向自己形成自环。这是血泪经验我见过太多人在手写代码时把这两行写反编译能过跑起来死循环。// 单链表在 p 之后插入 s顺序不能反 s-next p-next; // 第一步先让新结点接住后面的链 p-next s; // 第二步再让前驱指向新结点逻辑说明第一步保存了 p 原来的后继地址第二步才断开 p 与后继的连接。如果反过来第一步就把 p-next 改成了 s第二步再执行s-nextp-next时p-next 已经是 s 了等于s-nexts。参数上没什么可调的但要注意 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 是二叉链表根指针递归出口有两个——空指针和叶子。注意答案里叶子单独判断其实可以省略因为叶子走最后一行也是0011结果一样。但单独写出来可读性更好也方便你在调试时打日志。常见误用是把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 抓指针越界链表、树、图这些带指针的代码光看输出正常不代表没越界。我一般编译时加-fsanitizeaddress让运行时直接报出哪一行访问了非法内存。gcc -g -fsanitizeaddress -o list_test list_test.c ./list_test参数说明-g保留调试符号-fsanitizeaddress开启地址检查。如果链表插入顺序写反导致自环程序会在遍历时卡死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]16.10 讲邻接表建图每个顶点挂一个单链表。两者选型理由很直接顶点少边多稠密图用邻接矩阵判断两点是否相邻 O(1)顶点多边少稀疏图用邻接表省空间但判断相邻要遍历链表。对比项邻接矩阵邻接表空间O(n²)O(ne)判断边O(1)O(度)遍历邻居O(n)O(度)适用稠密图稀疏图答案 6.10 的建表代码里有个细节先G-adjlist[m].firstedgeNULL把所有头指针置空再读顶点符号最后读边。顺序不能乱否则头指针是野值插入时直接崩。参数上边数 e 和顶点数 n 都要做非负校验答案里写了if(n0) return -1;这个习惯要保留。4. 避坑与排查五条我实际踩过的记录4.1 现象栈的填空题 (R-FM)%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 i0;i4;i) printf(%d, out[i]); printf(\n); return; } if (pushed 4) { stack[top] in_seq[pushed]; dfs(pushed1); 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 个元素的出栈序列数。从那以后我每次对答案都强制走一遍“自己实现 → 抄输入 → 比中间状态 → 转测试用例”的流程比单纯对最终结果靠谱得多。希望帮到你。本文还有配套的精品资源点击获取