简介《Data Structures and Algorithm Analysis in C》第二版的官方配套习题解答手册由原书作者 Mark Allen Weiss 编写适合正在学习数据结构与算法、需要验证练习答案或补充解题思路的计算机专业学生与自学者。手册按原书章节组织内容覆盖算法分析、列表栈与队列、树、哈希表、优先队列、排序、并查集、图算法、算法设计技巧及摊还分析等核心主题多数习题均给出伪 C 代码或推导过程便于对照原书深入理解。资源为 1 个 PDF 文件压缩包大小约 233KB体积小巧便于离线查阅或移动端阅读。目前已有 141 人学习下载。除答案外手册前言还说明了对编程作业及参考文献指向题目有选择地省略并由作者对勘误保持开放态度读者可借此自查学习进度、弥补薄弱环节提升算法实现与复杂度分析能力。1. 答案手册该怎么用从“翻答案”改成“对思路”很多人第一次拿到《数据结构与算法分析C语言描述第2版》答案手册第一反应是翻到自己正在学的那一章看看解答密度。这份PDF把教材第1章到第12章的绝大多数练习都过了一遍大O复杂度排序、PrintLots链表遍历、哈希冲突处理、并查集路径压缩、Dijkstra实现细节每道题都有可参考的推导。它不是“标准答案汇编”更像作者手写的解题示范。适合上课做题卡壳的学生、准备复试想理清复杂度边界的求职者以及像我这样需要回头补算法基础的工程师。它的边界也很明确不能替你写作业也不能替代教材里的代码实现练习。2. 大O推导实战从复杂度排序到六段代码的逐层拆解2.1 复杂度排序题N log N 和 N log(N²) 同阶别被外层写法骗了答案手册第2章开头就是一张经典的增长率排序题2/N、37、√N、N、N log log N、N log N、N log(N²)、N log²N、N^1.5、N²、N² log N、N³、2^(N/2)、2^N。很多人第一遍对答案都栽在N log(N²)上因为它看起来和N²沾边。其实N log(N²) 2N log N和N log N只差一个常数倍大O意义下完全同阶。答案里也明确说了“N log N and N log (N²) grow at the same rate”但如果你只是看一眼结论不去亲手化简下次换一道题照样认不出来。我一般会先抄一张白纸把能化简的全部先化简写不出的再翻答案。比如那个“√N 与 N log N 的增长率对比”答案给了一个很绕的证明先假设N log N更慢推出ε√(log N)慢于log log N再通过换元L log N问题变成ε²L与log²L的比较而log²L o(L)于是反证成立。这个推导思路比结论本身值钱它示范了“取对数比大小”这个在复杂度证明里非常常用的工具。这一节值得抄进笔记的等价关系有三个log(N²) 2logNN log N 慢于 N^1.5log^k N 慢于任意正ε次幂的 N。答案手册第2.4题就是用洛必达把“log^k N / N^ε”的极限逐层消解成0的。我当时把这组式子写在索引卡上每次复习过一遍比反复读正文管用。2.2 六段代码逐段拆循环层数只是起点if执行次数才是关键答案手册第2.6题给了六段小程序的时间复杂度结论分别是O(N)、O(N²)、O(N³)、O(N²)、O(N⁵)、O(N⁴)。前四段很好理解第五段和第六段是两个经典反直觉例子——第五段里三层循环嵌套看似O(N⁶)但每层上界受前一层变量平方影响实际累加是O(N⁵)第六段藏了一个if判断虽然if在外层循环里会判断O(N³)次但真正成立的次数只有O(N²)内部再套一层扫描就把总量控制在O(N⁴)。只看答案结论很难建立直觉。我的做法是自己写一个和第六段模式相同的例子然后手推执行次数。下面这段是教材里经典的最大子序列和算法书上用它演示分治我拿它当练习“逐层拆复杂度”的模板int MaxSubSum( int A[], int Left, int Right ) { int Center, MaxLeftSum, MaxRightSum; int LeftBorderSum, MaxLeftBorderSum; int RightBorderSum, MaxRightBorderSum; int i; if( Left Right ) /* 递归出口单个元素 */ { if( A[ Left ] 0 ) return A[ Left ]; else return 0; } Center ( Left Right ) / 2; MaxLeftSum MaxSubSum( A, Left, Center ); MaxRightSum MaxSubSum( A, Center 1, Right ); MaxLeftBorderSum 0; LeftBorderSum 0; for( i Center; i Left; i-- ) /* 从中间向左扫 */ { LeftBorderSum A[ i ]; if( LeftBorderSum MaxLeftBorderSum ) MaxLeftBorderSum LeftBorderSum; } MaxRightBorderSum 0; RightBorderSum 0; for( i Center 1; i Right; i ) /* 从中间向右扫 */ { RightBorderSum A[ i ]; if( RightBorderSum MaxRightBorderSum ) MaxRightBorderSum RightBorderSum; } return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum MaxRightBorderSum ); }这段代码的复杂度递推式是 T(N) 2T(N/2) O(N)因为每次把数组切成两半递归处理左右各一半最后两个for循环加起来扫一遍全数组所以合并代价是O(N)。解得T(N) O(N log N)。我每次看到这种分治结构都会先问自己一句合并这一步是O(N)还是O(N²)如果答案是O(N²)整体可能退化到O(N² log N)。参数上要注意的是递归出口Left Right时直接返回避免无限递归。第二个for的起始是Center 1而不是Center因为Center已经在左侧扫描里算过了这个边界错误会导致元素被重复累加。这两个地方都是答案手册里明确说的“minor details are left to the reader”的典型——思路框架没错但边界不补齐就跑不对。2.3 随机排列的三种算法期望时间差一个N²规模表一眼看懂内存瓶颈第2.7题对比了三种生成随机排列的算法。算法一是逐个生成随机数并查重已出现就重试算法二给每个位置维护一个可用集合减少无效重试算法三是交换法初始化数组后原地打乱。答案给的时间分别是算法一期望O(N² log N)算法二期望O(N log N)算法三O(N)。很多人不理解为什么算法一多了一个N²因为第i个位置需要从N个数里挑一个没被用过的成功概率是(N-i)/N期望尝试N/(N-i)次把所有位置累加得到N·H_N也就是O(N log N)但每次判重还要花O(i)时间检查总时间就成了O(N² log N)。第2.8题给了一张更扎心的表同一台机器上跑N100,000的排列生成算法一约需3小时算法二也是3小时级别算法三只要1.5分钟到N1,000,000算法二要约两周算法三还是两分钟以内。这个对比说明一件事大O差距在数据规模变大时是碾压性的常数优化救不回来。答案手册还补了一句值得抄下来的话如果机器内存不够算法三“看起来”也不是线性的因为数组访问会触发大量缺页。这句话我在实际项目里反复踩到复杂度漂亮的算法在小数据上反而跑不过带缓存优化的低复杂度算法原因就是内存墙。现在我做选型时习惯先问数据规模再谈复杂度避免被“理论最优”带偏。3. 链表、树与哈希的参考答案用法补齐伪C代码再谈边界条件3.1 PrintLots完整实现P指针只后移L指针做位置推进第3章的PrintLots是很多人第一次接触“链表遍历的协同操作”。题目要求打印链表L中位置由另一个链表P指定的若干元素。比如P里存的值是2和5就打印L的第2个和第5个节点。答案手册给的框架很精简但把else分支留给了读者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 ); } else { Lpos Next( Lpos, L ); /* 不匹配就往下走 */ } } }如果只看答案手册里的原始片段很容易以为if执行完就完了忘了L指针也需要推进。注意我这里的Counter从1开始每轮判断一次就自增Ppos-Element和Counter相等时打印并推进Ppos不相等时只推进Lpos。这样两个指针各走各的路Lpos每轮最多走一步Ppos只有在命中时才走最坏情况下L和P各被完整遍历一遍总时间O(LP)。这里有个容易被忽略的坑如果P里的元素不是严格递增的递增序列这个实现会出问题。比如P里存的是3和1那么当Counter走到3并打印后Ppos指向1但Counter已经4了后面的1永远不可能匹配循环直接跑穿L然后退出。答案手册的前提是P也是递增排列的实际用的时候要对P做预处理或加排序判断。“参考答案只解决理想输入”这件事几乎每个题都会出现这也是为什么你现在看到的所有刷题资源都在强调边界测试。3.2 树的证明题用左右子树两个递归分支控制归纳深度第4章的树主题里最常见的一类练习是用归纳法证明树的节点数与高度关系。教材的标准结论是高度为h的二叉树最多有2^h - 1个节点。答案手册给的证明思路是先对h0和h1验算然后假设所有高度小于h的树都成立把当前树拆成左子树和右子树利用归纳假设得到节点数上界。但这里有个选变量的问题答案手册不会明说归纳变量选高度h而不是节点数n。如果选n做归纳变量树的高度和左右子树的节点数分布没法保证是整齐的递推而选h递推式T(h) 2T(h-1) 1的右边直接对应左右子树的最大高度。这个“选哪个量做归纳”的经验我在看答案时根本没意识到直到自己写证明卡壳才回去对比发现答案每一处归纳变量都选得很有讲究。操作层面我建议自己把递推式展开一遍T(0) 0T(1) 1T(2) 2·1 1 3T(3) 2·3 1 7到第h层能看出规律是2^h - 1。然后写清“完满二叉树满二叉树让等号成立”。这类证明题的验收标准不是看懂而是合上书从“高度为h”出发完整写三行式子推出2^h - 1中间不偷看。3.3 哈希冲突的两种策略链地址与开放寻址的常数差异第5章哈希表的核心是冲突处理。答案手册会把线性探测、平方探测、分离链法的查找期望次数公式摆出来但真正值得记的是它们随装载因子λ变化的拐点。线性探测的平均成功查找次数约(1 1/(1-λ))/2分离链法约1 λ/2。λ0.5时线性探测约1.5次链地址约1.25次差距不明显λ0.8时线性探测直接跳到2.5次链地址才1.4次。我自己的取舍习惯是内存富余且读多写少的场景用链地址实现简单、删除方便对缓存局部性敏感且λ能压在0.5以下的场景用开放寻址。删除操作是另一个关键点开放寻址删元素不能直接置空否则会让探测链断掉正确的做法是打“已删除”标记位。答案手册里对这种边界操作往往只提一句但它恰恰是实战中哈希表翻车率最高的地方。4. 排序、并查集和图算法从答案反推三处最常见的实现取舍4.1 排序算法横向对照复杂度之外还有稳定性和常数因子第7章排序的答案覆盖了插入排序、希尔排序、堆排序、归并排序和快速排序。很多人只背了平均复杂度忽略了几组实战中更关键的性质。下面这张表建议抄下来贴在显示器边上算法最坏平均额外空间稳定性插入排序O(N²)O(N²)O(1)稳定希尔排序取决于步长约O(N^1.3)O(1)不稳定堆排序O(N log N)O(N log N)O(1)不稳定归并排序O(N log N)O(N log N)O(N)稳定快速排序O(N²)O(N log N)O(log N)不稳定堆排序最坏也是O(N log N)且不用额外空间看起来完美但实际常数偏大而且不稳定快速排序平均最快但最坏退化需要随机化选主元或者三数取中法来规避。答案手册在第7.2题里专门分析过这些细节但如果你只对结论不推推导下次选型还是会踩坑。我自己做排序选型的习惯外部排序数据量放不进内存用归并嵌入式环境内存小用堆排序或自实现的快排业务代码求稳妥直接调现成排序函数不再造轮子。4.2 并查集按秩合并与路径压缩为什么复杂度可以当常数看第8章不相交集合ADT是图算法的基石。答案手册会花很大篇幅解释“逆阿克曼函数为什么增长极慢”。我这里直接给可运行的代码配合注释说明关键点typedef int DisjSet[ NumSets 1 ]; typedef int SetType; typedef int ElementType; void Initialize( DisjSet S ) { int i; for( i NumSets; i 0; i-- ) S[ i ] 0; /* 0 表示根节点负数表示高度 */ } void SetUnion( DisjSet S, SetType Root1, SetType Root2 ) /* 按高度合并 */ { if( S[ Root2 ] S[ Root1 ] ) /* Root2 比 Root1 更高 */ S[ Root1 ] Root2; else { if( S[ Root1 ] S[ Root2 ] ) /* 两者一样高合并后高度加一 */ S[ Root1 ]--; S[ Root2 ] Root1; } } int Find( int X, DisjSet S ) /* 路径压缩 */ { if( S[ X ] 0 ) return X; else return S[ X ] Find( S[ X ], S ); }S数组存负数表示当前树的高度正数表示父节点下标。Union时把矮的树挂到高的树上避免树长高Find递归时把路径上每个节点直接指向根节点下一次查找就是O(1)。答案手册第8章证明的是带上这两个优化后m次Union和Find操作的总时间约O(m α(n))其中α是逆阿克曼函数输入规模无论多大它的值都不会超过4或5实践里直接当常数处理。这段代码的边界点在于数组下标从1开始S[0]基本是废弃状态以及S[X] 0判断根节点时要小心X传成0导致越界。答案手册里的写法更精简但省略了这些防御性判断照抄到项目中容易在边界上出事。4.3 图算法的复杂度边界邻接矩阵和邻接表的后果第9章图算法的答案围绕最短路径、最小生成树和拓扑排序展开。第9章最重要的不是某一题的解而是图表征方式对复杂度的决定性影响。Dijkstra算法用邻接矩阵实现是O(V²)用邻接表加二叉堆优化是O(E log V)稠密图里E接近V²堆优化优势并不大朴素O(V²)反而常数更小稀疏图里E接近V邻接表加堆才划算。Prim算法和Dijkstra有完全相同的复杂度形态区别只在更新的是“到树的最短距离”而不是“到源点的最短距离”。Kruskal则需要先对边按权值排序O(E log E)配合并查集处理连通分量。Floyd-Warshall是O(V³)但能处理负权边只要不出现负权环。答案手册反复让读者比较这些边界核心训练点就一个看到题先判断图的稠密度再选算法不要上来就套模板。5. 避坑指南使用答案手册的五个常见翻车点5.1 伪C代码导致编译翻车现象照着答案里的PrintLots敲进编译器printf的格式串是“%?”链表结构体也没有定义第一行就报错。原因答案手册前言写得很清楚代码是pseudo-C作者刻意省略了细节只保留思路骨架。解决把结构体、宏定义补齐把“%?”改成真实的“%d”或“%f”再谈运行。我一般把答案当“伪代码级别的设计草稿”自己重写一遍而不是逐行翻译。5.2 印刷版勘误与题号偏移现象手头教材是第二版第N次印刷答案里的题号对不上比如答案2.7在教材里可能是2.8。原因答案手册对应的是第一版印刷后续印刷修订过习题编号。解决用章节名定位而不是题号。对不上的时候把题干抄到答案旁边标注“本手册版本差异”下次复习能直接对应上。5.3 详答与略答混杂分不清重点现象有的题推导到每一步有的题直接写“See reference”或“一般细节留给读者”。原因作者有意省略了编程作业和带外部引用的题详略分布不等。解决先分清题目考察的是分析能力还是代码能力。核心算法分析题必须亲笔推一遍纯代码填空题按需看不必死磕答案的风格。5.4 证明题只看不推等于白读现象看答案时觉得每一步都顺理成章合上书自己写卡在归纳假设不知道往哪儿套。原因归纳证明的难点在归纳变量选择和归纳假设的组织看懂和默写出来是两回事。解决把答案当成“标准动作拆解”先看结论再合上书自己推推到卡住的位置记下来再对比答案找差异。第3章的树证明和第8章的并查集分析都是这么过的。5.5 直接照抄答案交作业一眼被看穿现象A同学提交的作业和参考答案一模一样变量命名和代码风格都对上了被导师约谈。原因答案手册流行度太高直接把伪C代码交上去等于表态“我没消化”。解决用自己的命名习惯重写把printf格式换成实际要求至少加两行注释说明边界条件。作业是自我验证的素材抄一遍骗过自己考试时就露馅了。6. 验证技巧用两遍法把答案手册变成错题卡6.1 先限时推导再对照标红我的做法分两遍。第一遍限时做算法设计题15分钟证明题20分钟编程题先写伪代码。不会写也要把思路关键词列在纸上比如“尝试归纳法、用高度做变量”或“考虑邻接表加堆”。第二遍对照答案结论一致但推导路径不同的标“思路差异”推一半卡住的标“断点”结论都错的标“理解偏差”。错题卡可以简单设计成四列题号卡点答案关键步复习日期2.7(b)期望次数推导忘了乘判重开销成功概率(N-i)/N判重O(i)当天、三天后3.2忘了else推进Lpos两个链表各遍历一遍当天、两周后8.5(c)路径压缩证明不理解S[X]Find(S[X],S)是关键当天、三天后复习节奏是当天把标红的题重推一遍三天后再推一遍两周后只过错题卡。这个方法帮我治好了“看答案全会上考场全废”的毛病。最早拿到这份手册时我也是直接翻答案一章刷完以为自己很懂模拟考遇到原题变形直接卡死。从那以后凡是教材配套题集我都强制自己先写10分钟思路再翻答案哪怕写的是“不知道从哪里下手”也要落在纸上。希望“两遍法”也能帮到你。本文还有配套的精品资源点击获取
解法)
