简介本资源为Mark Allen Weiss《数据结构与算法分析C语言版》第二版的配套习题解答手册面向系统学习数据结构与算法的计算机专业学生、考研与算法面试备考者。手册以PDF格式提供压缩后约233KB解决了经典教材课后练习缺少标准参考的问题。内容从算法分析与大O表示法、列表/栈/队列到树与平衡树、哈希表与冲突处理、优先队列堆、常用排序算法、不相交集合ADT、图遍历与最短路径、算法设计技术及摊还分析十二章核心模块均有涉及几乎每章习题都给出解题思路提示与伪C代码示例便于读者完成练习后对照自查、排查理解偏差。目前已有141人浏览学习适合验证自学进度、巩固编程实现能力或备战算法类考试的中级读者。1. 习题答案手册数据结构的每个证明和代码都有人替你推了一遍《数据结构与算法分析》的答案手册是我见过最容易被低估的一份资源。它不是网上那种零散题解而是把教材 12 章里绝大多数习题按原始编号逐章排好从归纳证明、复杂度推演到伪 C 代码实现全都有。很多人把它当“抄作业工具”存着其实真正的价值在于它演示了“一道证明题应该写到多细才算完、一个算法题答案该从哪个角度切入”。适合正在啃原版教材的自学者也适合带课的人拿去对答案、拆讲解思路。我拆这份 PDF 时最大的感受是——你不一定需要它的答案但你很需要看它怎么组织答案。2. 算法分析两章增长率排序、证明模板与随机算法的复杂度2.1 增长率排序先看懂 2/N 到 2^N 的这条链答案手册第 2 章开头就是一道经典排序题把一堆常见函数按增长率从慢到快排列。这道题几乎出现在每一版的习题里也是后面所有复杂度分析的地基。很多人背过结论但真到了「NlogN 和 Nlog(N²) 谁快」这种问题上就开始含糊。手册给的答案是把它们排成一条链2/N、37、√N、N、NloglogN、NlogN、Nlog(N²)、Nlog²N、N^1.5、N²、N²logN、N³、2^(N/2)、2^N。你一眼能看出的重点是常数项 37 比 2/N 大但当 N 很小时这类“增速为常数”的函数之间的比较没有实用意义NlogN 和 Nlog(N²) 是同阶因为 log(N²) 2logN差一个常数因子 2。增长速度段典型函数实际含义常数级2/N、37不随输入规模增长工程里基本可以忽略亚线性√N常出现在预处理后查表、分块搜索线性N遍历一次大多数问题的最低期望线性对数NlogN、Nlog(N²)排序和分治的分水岭归并、快排的典型量级多项式N²、N³循环嵌套的产物N 超过一万就要警惕指数2^(N/2)、2^NN 上 30 就基本跑不动只能靠剪枝或近似我建议你把这个表抄下来贴在屏幕上。后续做算法题、看手册里任意一章的答案脑子里始终要有这条链。手册在 2.1 题里特意把 NloglogN 放在 NlogN 前面这个细节经常被忽略loglogN 的增长比 logN 慢太多凡是能把复杂度从 NlogN 压到 NloglogN 的算法比如某些筛法、优先队列优化在大数据量下收益非常明显。还有一个容易记混的点Nlog(N²) 和 Nlog²N 不是一回事。前者是 N 乘 log 的平方不对前者是 N * log(N²)也就是 2NlogN后者是 N * (logN)²。手册的排序链把它俩分得清清楚楚做题时先化简再比较别被表达式表面骗了。2.2 证明题三板斧归纳、反例与 LHospital答案手册前两章最有学习价值的不是代码而是数学证明的“写法”。第 1 章第 5 题让证明 logX X手册用的是一套非常标准的归纳框架先处理 0 X ≤ 1 和 1 X ≤ 2 的边界再假设定理对 p X ≤ 2p 成立推 2p Y ≤ 4p 的情况。拆开看就三步——验证平凡情形、设定归纳假设、利用假设做不等式放缩。这套写法你完全可以抄成自己的证明模板。我在带某同学复习的时候发现他做题最大的问题是“知道结论但不知道第一步写什么”。后来我让他强制按下面这个流程走先写“证明方法归纳法 / 反证法 / 构造法”再写边界N 1、N 2 时结论是否成立设归纳假设明确“假设对 k 成立”用假设推 k1并用题目给出的运算定义比如 Fibonacci 的递推式收尾最后写“由归纳法命题对所有 N ≥ 1 成立”。第 2 章第 2 题是另外一类经典判断题考大 O 关系的反例构造。手册给的答案很巧妙——找两个函数让它们在偶数和奇数上交替“变大”。比如 f(N) 在偶数取 1、奇数取 Ng(N) 反过来那么 f/g 的比值在 0 和无穷之间振荡谁也不是谁的渐进上界。这种反例思路在工作里也常用当你说“这个接口 O(1)”时一定有人在某个边界场景给你构造出一个 O(N) 的反例。至于 LHospital 法则答案是第 4 题的标准解法证明 log^k N o(N^ε) 这类幂指关系时连续用洛必达把分子降阶归纳一直到常数。注意这里有个使用前提——必须先确认两个函数都趋于无穷否则洛必达不适用。我见过有人拿它去证明 1/N 的增长关系结果得出完全错误的结论。2.3 随机排列三算法从 O(N²logN) 到 O(N) 的推演第 2 章第 7 题是一道值得反复咀嚼的题生成 0 到 N-1 的随机排列三种算法复杂度差异巨大。这道题在面试和实际代码里都反复出现答案手册给出了完整的期望复杂度推演。/* 算法 1逐个生成随机数重复就重试 */ for (i 0; i N; i) { do { A[i] RandInt(0, N-1); } while (已经被使用过); } /* 算法 2改进重试检查的查找代价 */ for (i 0; i N; i) { do { A[i] RandInt(0, N-1); } while (在 A[0..i-1] 中能找到 A[i]); } /* 算法 3Floyd 的思路原地交换生成 */ for (i 0; i N; i) A[i] i; /* 先初始化 0..N-1 */ for (i 0; i N; i) Swap(A[i], A[RandInt(0, i)]); /* 关键只和当前前缀交换 */第一个算法的期望复杂度是 O(N²logN)。推导逻辑是放第 i 个数时N 个位置里已有 i 个被占成功概率是 (N-i)/N所以期望尝试次数是 N/(N-i)累加后是 N² 乘调和级数。第二个算法只是把检查已存在元素的代价降下来了期望降到 O(NlogN)。第三个算法是线性的因为每次交换只看 RandInt(0, i)不会出现无限重试。这里有个容易翻车的细节手册特别点了一句如果算法 3 第二行换成 Swap(A[i], A[RandInt(0, N-1)])也就是每次随机到整个数组而不是当前前缀那么 N3 时总共 27 种随机数序列却只有 6 种排列27 不能被 6 整除必然有一些排列出现概率偏高。这个坑在真实代码里非常隐蔽——你写完觉得自己在“均匀洗牌”实际上分布偏了只有跑大量样本做统计才能发现。算法 3 的最坏情况运行时间是线性的因为它根本不依赖随机数序列而算法 1、2 的最坏时间无界因为存在一直随机到重复的有限概率。这个区分是笔试高频考点。3. 线性结构到堆链表、树、哈希与优先队列的答案脉络3.1 链表题答案的样子PrintLots 与 O(LP) 的由来第 3 章开始进入正题答案手册的风格也变了不再是一堆数学符号而是给你一段伪 C 代码加一句复杂度结论。第 3 章第 2 题的 PrintLots 是典型的“链表操作 双指针同步推进”题目给定表 L 和表 P打印 L 中那些位置被 P 里的元素标记的节点。void PrintLots(List L, List P) { int Counter 1; Position Lpos First(L); Position Ppos First(P); while (Lpos ! NULL Ppos ! NULL) { if (Ppos-Element Counter) { printf(%d , Lpos-Element); Ppos Next(Ppos, P); } Lpos Next(Lpos, L); } }关键在 Counter 的用法它不需要单独维护“当前是第几个位置”而是把 P 的元素当“哨兵”Ppos-Element 等于 Counter 时就打印一个节点并移动 P 指针。这个技巧看着简单实际自己写时很容易写成双层循环——外层遍历位置、内层用 Find 查表复杂度就变成 O(L×P) 了。手册给的答案期望的是 O(LP)两个指针各走各的L 指针走完整个表P 指针也最多走完整个表不会回头。我在某次代码评审里就看到类似的反面案例有人写了个“在链表中按位置批量取值”的函数用了嵌套循环。当时链表只有几千个节点感觉没事后来换成几十万节点直接卡死。双指针同步推进这种思路从这道题开始就在数据结构里反复出现后面归并排序合并、链表判环都吃这套。3.2 树与遍历递归证明怎么写不丢分第 4 章是树的天下答案手册在这一章的习题覆盖了二叉查找树、AVL 旋转、遍历递归。前几章算法分析积累的归纳法在这里开始真正发力——树的很多性质天然适合归纳因为树本身就是递归定义的。手册答案对这种题的标准处理方式是证明树的高度、节点数、层数之间的关系时先假设左子树和右子树分别满足性质再证明根节点把这俩合起来依然满足。比如证明一棵高度为 h 的二叉树最多有 2^h - 1 个节点就是先算左子树最多 2^(h-1) - 1、右子树也是再加根节点得到 2^h - 1。这种模式你可以在第 4 章的答案里反复看到。实际做题建议树的代码题先写递归出口空节点、单节点再写递归调用树的证明题先写“对子树用归纳假设”再写“合并到根节点”。AVL 部分重点刷“插入后四种旋转的选择”判断标准只有一个——从失去平衡的节点往下看两步往左再往左是 LL往左再往右是 LR。答案手册里这类题一般只给旋转后的形状和复杂度结论中间画图需要自己对教材。因为 PDF 里的图本来就少纯文字描述旋转方向非常容易看晕我的习惯是拿笔在纸上画一棵 5 层左右的树手动插一个节点再把答案的旋转步骤对着图走一遍。3.3 哈希与堆冲突处理与削堆操作的边界第 5 章哈希和第 6 章优先队列在答案手册里属于“结论驱动”的部分。哈希的核心就两件事哈希函数设计和冲突解决。冲突解决要么开放定址线性探测、平方探测、双散列要么链地址。答案题里问得最多的是给定一个哈希函数和一组插入序列画出最终表的状态再算平均成功查找次数。我建议你把下面这张表当作章末复习卡手册里的答案都是围绕这些参数展开的操作开放定址平均链地址平均备注查找成功约 1/(1-α)1 α/2α 是装载因子开放定址下 α 必须小于 1查找失败约 1/(1-α)²α链地址的失败查找只需要查一个桶插入近似查找失败的代价O(1)链地址插表头最省删除懒删除或特殊标记O(1) 定位后删除节点开放定址删一个元素可能断链第 6 章堆的答案里最核心的是六个操作插入、下滤、上滤、DeleteMin、DecreaseKey、BuildHeap。手册对这些题的标准回答是给伪代码再标注复杂度插入 O(logN)、BuildHeap 是 O(N) 而不是 O(NlogN)——这个反直觉结论是堆章节最常考的题。证明思路是高度为 h 的节点做下滤代价 O(h)把所有节点的代价按层累加求和结果是 O(N)。我当时学到这里也觉得很玄学但后来做外部排序的败者树优化才发现 BuildHeap 线性时间是真能用上的。注意 DecreaseKey 在教材实现的二叉堆里需要额外记录位置数组否则你找不到节点在哪。答案手册里通常默认你已经有 position 数组所以只写“下滤/上滤”的调整逻辑。工程里如果直接用一个裸二叉堆做 Dijkstra 的 decrease-key大概率翻车要么改成配对堆、要么用懒删除。这些都是答案覆盖不到、但实战一定会撞上的边界。4. 排序、并查集与图算法三套高频答案的边界与速查4.1 排序章节下界证明与各算法的适用边界第 7 章排序是整本手册里答案最“杂”的一章有下界证明、有递归复杂度分析、还有大量“什么时候不该用快排”的讨论。手册对比较排序下界的标准证明是决策树N 个元素有 N! 种排列每次比较把可能性分成两半所以最少需要 log(N!) 次也就是 Ω(NlogN)。这个结论的重要性在于它说明在“通用比较模型”下不存在比归并、快排渐进更快的人。真正干活的时候答案手册里那些排序的性质表格比证明更实用算法平均最坏稳定额外空间什么时候选它插入排序O(N²)O(N²)是O(1)N 很小、或基本有序归并排序O(NlogN)O(NlogN)是O(N)需要稳定或外部排序快速排序O(NlogN)O(N²)否O(logN)大部分通用场景注意选好 pivot堆排序O(NlogN)O(NlogN)否O(1)不允许额外空间但接受不稳定希尔排序很难界定取决于增量序列否O(1)教学意义大于工程意义快速排序有个经典边界当 N 很小的时候快排的递归开销和 pivot 选择开销反而比插入排序大。所以工程实现普遍做“快排 插入排序 cutoff”通常 N 小于 10 到 20 就直接插排。答案手册在第 7 章的多道题里其实都在暗示这个方案不是让你抛弃快排是让你承认每道算法都有它的适用半径。我自己的血泪经验是有一回处理一组几乎有序的数据直接裸快排pivot 每次取第一个元素结果递归深度直接崩了。后来改成三数取中才把这事按住。三数取中不是玄学它是快排最便宜的一层保险。4.2 并查集为什么路径压缩能到反阿克曼函数第 8 章只讲一个数据结构不相交集合。答案手册里围绕它的题目基本都是三类模拟 merge/find 过程、证明按高度合并的正确性、分析路径压缩的复杂度。这个 ADT 在教材里看起来轻巧实际是图算法里 Kruskal 最小生成树的底子也是工程里连通性判断的常用工具。/* 按高度合并 路径压缩的并查集 */ typedef int DisjSet[NumSets 1]; void Initialize(DisjSet S) { for (int i NumSets; i 0; i--) S[i] 0; /* 负数表示根绝对值是高度 */ } int Find(int X, DisjSet S) { if (S[X] 0) /* 自己是根 */ return X; else return S[X] Find(S[X], S); /* 路径压缩直接挂到根 */ } void SetUnion(DisjSet S, int Root1, int Root2) { if (S[Root2] S[Root1]) /* Root2 更高 */ S[Root1] Root2; else { if (S[Root1] S[Root2]) S[Root1]--; /* 高度相等根1高度加1 */ S[Root2] Root1; } }上面的实现里S 数组存的是负数-1 表示高度 1 的根-2 表示高度 2 的根。Find 里的路径压缩让沿途所有节点直接指向根下一次查找就是 O(1)。单独按高度合并是 O(logN)加上路径压缩后一组 M 次操作的总代价接近 O(M α(M,N))α 是反阿克曼函数增长速度比 log 还慢在实际数据规模下基本等于常数。这道题的答案价值不在于让你背结论而在于让你看到“两个优化叠在一起会产生质变”。很多开发者工作几年都没写过并查集真到写 Kruskal 或连通性检测的时候才回来翻书。我建议你把这 20 行代码存成你自己的模板片段面试前默写一遍比看十遍答案都管用。4.3 图算法从 DFS 到最短路径的答案细节第 9 章图算法是整本手册篇幅最大的章节之一。DFS、BFS、拓扑排序、Dijkstra、Floyd-Warshall、Prim、Kruskal 全挤在这里。手册答案对图算法的处理特点是先强调图用什么表示再谈复杂度。同一个 Dijkstra用邻接矩阵是 O(V²)用邻接表加二叉堆是 O(ElogV)两者在稀疏图上差距巨大。算法前提复杂度邻接表堆典型应用DFS无特殊要求O(VE)连通分量、拓扑排序、环检测BFS无权图O(VE)最短路径按层Dijkstra非负权边O(ElogV)单源最短路径Floyd-Warshall允许负权但无负环O(V³)全源最短路径Prim无向带权图O(ElogV)最小生成树Kruskal无向带权图O(ElogE)最小生成树有个几乎必考的答案题为什么 Dijkstra 不能处理负权边标准答案是Dijkstra 的贪心性质建立在“已经确定最短路的节点不会再看走回头路得到更短路径”的假设上一旦出现负权边先确定了距离的节点可能因为一条负权边被后来者超越贪心就失效了。答案手册里这道题的解法通常是构造一个三节点反例起点到 A 是 1起点到 B 是 2A 到 B 是 -3你按 Dijkstra 先锁 A结果发现真正的 B 最短路是从 A 绕过去的 -1但 A 已经出队了。这种反例自己画一遍比背十遍结论都扎实。图算法章节的答案还有个特点是“伪代码多、完整实现少”手册默认你自己能把 DFS 的递归栈和邻接表操作补出来。所以拿这份资源复习图算法时别只看答案的复杂度结论一定要自己手写一遍 DFS 和 Dijkstra 的 C 实现。写不出来说明这本书第 9 章还没真正过手。5. 答案手册避坑版本错位、伪代码与五个翻车场景5.1 先别照抄答案里省略了什么这份答案手册的 Prefaces 写得很直白编程类作业题基本都略过任何“答案指向课后文献”的题也不收给出的程序是伪 C 而不是完美代码细节留给读者自己补。这意味着什么意味着你拿它当“标准答案库”会失望拿它当“思路参考答案”才对路。第一个最实际的坑是版本错位。手册对应的是第二版第一刷习题编号和后续的影印版、中文版对不上很正常。我见过一个同学按中文版的习题编号去手册里找答案找了半天没找到跑来问我是不是资料不完整。其实题号差了两位比如中文版第 3 章第 4 题在英文原版里是第 3 章第 2 题。解决办法很简单先用题目关键词在 PDF 里搜别死记题号。第二个坑是伪代码风格。PrintLots 那道题印在手册里就有个很有意思的细节——printf 的格式串直接写成了%? 看起来像印刷错误。因为这是给老师看的答案不是给你编译运行的代码格式符具体是 %d 还是别的作者根本不在乎。你需要自己补全类型。另外像 IntPart、DecPart、PrintDigit 这种函数手册默认你从教材正文里抄它只写主流程。照抄编译必然报错。5.2 五个翻车场景与排查我把实际使用中容易踩的坑整理成五条每条都按“现象 → 原因 → 解决”的顺序说你遇到类似问题直接对号入座。现象一照着手册代码敲进 IDE编译一堆未定义函数报错。 原因手册只给伪 C 主逻辑依赖的教材工具函数如 First、Next、IntPart被省略了。 解决把教材正文里对应的函数实现先抄进来再编译。PrintLots 需要你自己定义 Position、List、First、Next手册默认你手里有前几章的代码。现象二用 PDF 搜索功能找“AVL 旋转”搜出来的文本全是乱码比如 “φ”、“”这类符号。 原因这份 PDF 是扫描件转的公式和希腊字母是 OCR 识别的数学符号全变成杂字符。 解决公式类题目不要用纯文本搜索按“第 4 章 旋转”这种组合关键词定位涉及数学式子的答案直接看页面截图别依赖复制粘贴。现象三对答案时发现自己写的递归思路和手册完全不一样以为自己学错了。 原因分治和递归类题目本身就没有唯一答案手册给的是它觉得“最符合教材前后文”的一种解法。 解决先对比复杂度再对比边界处理。如果你的版本复杂度同阶、空指针和单节点的情况也处理了那你的答案就是有效的不必强行改成和手册一样。现象四第 6 章堆的 DecreaseKey 题按答案写完跑 Dijkstra 时结果不对。 原因裸二叉堆做 DecreaseKey 需要 position 数组定位节点答案手册默认你有这个前置结构很多自己实现的版本没存位置导致 decrease 的节点找错。 解决要么维护元素到堆下标的映射数组要么改用懒删除。这是典型的“答案没写、工程必须处理”的隐藏细节。现象五用大 O 结论直接判断两个算法谁快结果在 1000 条数据上实测完全相反。 原因渐进复杂度描述的是 N 趋向无穷的行为小规模下常数项和初始化开销占主导2.18 题里明确说过最坏情况界不足以判断实际快慢。 解决先算数据规模是否进入渐进区一般 N 小于一万直接做基准测试别拍脑袋。复杂度分析是指方向不是算秒表。6. 从看答案到验思路摊还分析与高级章节的自查法6.1 摊还分析的三种工具怎么选第 11 章摊还分析对自学者是最容易“看一眼答案就觉得懂了、合上书就忘”的部分。手册里反复用到三种方法聚合分析、记账法、势能法。选哪种不是玄学我一般按下面这个方式判断如果所有操作的总代价好直接求和用聚合如果想把“便宜操作和贵操作”之间的预付费关系讲清楚用记账如果脑子里已经有一个“蓄水池”的直觉比如堆里每个节点存了多少势能用势能法。三种方法殊途同归最后得到的摊还界应该一致。对答案时如果三种方法结果对不上推荐优先相信势能法的结果因为它最容易暴露“势能函数定义错了”这类问题。6.2 用答案做验证对答案五步法最后一章我分享一个自己的习惯拿到一份习题答案不是为了把题做对而是为了验证“我的思路链在哪一环断了”。我现在每周固定用答案手册做一次专项训练流程固定五步先不看答案把一章里自己会做的题做完不会的题写下卡点——是不知道用什么数据结构还是复杂度推不下去翻开答案只看“思路第一句”不看完整推导然后回去自己补补完再对完整答案重点看边界条件和复杂度结论是否一致把卡点记在一张索引表里标注是“归纳法不熟”还是“堆操作不熟”下次复习直接查这张表。这套流程用下来最大的收益是答案手册变成了一个“校验器”而不是“拐杖”。那以后我每次啃一章新内容都强制自己先走一遍这五步哪怕时间紧至少也要完成前三步再碰答案。这个习惯让我从“看完答案觉得自己会了”的假象里跳出来——会做和会讲之间隔着一条深沟希望帮到你。本文还有配套的精品资源点击获取