简介这份PDF是Mark Allen Weiss《Data Structures and Algorithm Analysis in C》第二版配套习题解答手册面向正在学习数据结构与算法分析、需要核对课后练习思路的高校学生与自学者也可供讲授C语言算法课程的教师参考。文件为单一PDF约233KB内容按教材章节组织覆盖算法分析、表栈与队列、树、哈希、优先队列堆、排序、不相交集合ADT、图算法、算法设计技巧、摊还分析及高级数据结构与实现等主题。解答以伪C代码和要点推导为主对部分习题给出较完整过程次要细节留给读者补充便于在独立完成练习后对照检查理解大O分析、平衡树、哈希冲突处理、堆操作、各类排序与图遍历、最短路径和最小生成树等知识点的解题路径。已有143人学习适合作为教材配套的查漏补缺材料。1. 答案手册不是答案算法分析为什么要从数学证明讲起翻开这份手册第一页不是链表节点的插入代码而是 RoundUp 函数和一道归纳法证明。这个开场本身就挺反直觉一份“答案手册”最先给人的不是答案而是推导过程。它其实在说明一件事——数据结构与算法的门槛不在“记住怎么写”而在“能不能用数学语言说清一个算法在 n 增长时到底花多少时间”。大 O 表示法不是背出来的是从增长率排序和归纳法证明里推出来的。手册第 2 章把 2/N、37、√log 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 log(N²) 增速相同这个细节不是常识需要证明。这条线一旦理解清楚后面所有递归式分析才有参照系。这份资源真正解决的是把教材里“结论”和“证明”之间那段空白填上让读者从“会用”走到“知道为什么能 work”。2. 增长率排序与归纳法O(f(n)) 的证明链条怎么搭2.1 从 2/N 到 2^N增长率排序的完整谱系手册 2.1 题给出了一条完整的增长率序列2/N 37 √log 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这条线里有几个容易看走眼的锚点。第一个是2/N排在常数37前面当 N 增大时2/N 趋近 0而 37 纹丝不动所以 2/N 的增速更慢。注意这里的“增长”说的是 N 变大时函数值的变化趋势不是函数值本身的大小。第二个是N log N和N log(N²)同阶。因为log(N²) 2 log N所以N log(N²) 2N log N和N log N只差一个常数因子 2。大 O 记法里常数因子不改变量级这两个就是同一档。第三个是N log²N和N log(N²)的区别。前者是N * (log N)²后者是N * log(N²) 2N log N。这俩在教材里经常被排版混淆一旦在分析里把log²N写成log(N²)整条排序就会错位。这也是为什么手册会把它们分两行列出来。把这条线和具体算法对上归并排序是 N log N快速排序平均是 N log N最坏是 N²堆排序是 N log N二分查找是 log N矩阵乘法朴素实现是 N³子集枚举是 2^N。分析出一个表达式之后先放进这条线里定位再谈常数优化才有意义。2.2 归纳法怎么“锁住”边界从斐波那契到对数不等式手册 1.5 题是一个用归纳法证明对数不等式的典型例子。要证的是当 X 0 时log X X。证明分三段基础段覆盖0 X ≤ 1和1 X ≤ 2。前一段里 log X 为负显然小于 X后一段里 log X ≤ 1 X也成立。归纳段假设结论对p X ≤ 2p成立考虑2p Y ≤ 4p。把 Y 拆成Y 2 * (Y/2)其中Y/2落在p Y/2 ≤ 2p区间于是log(Y/2) Y/2。再展开log Y 1 log(Y/2) 1 Y/2 Y/2 Y/2 Y第一处不等号用的是归纳假设第二处用的是1 Y/2因为 Y 2p ≥ 2。整个链条就闭合了。1.9 题的斐波那契不等式更能体现“锁边界”的含义。要证F_k φ^k其中 φ (1√5)/2。关键恒等式是φ 1 φ²由此推出φ^(-1) φ^(-2) 1。归纳步骤里F_(k1) F_k F_(k-1) φ^k φ^(k-1) φ^(k1) * (φ^(-1) φ^(-2)) φ^(k1)这里的精妙点不在“代入”而在把右边凑成φ^(k1)的形式后系数恰好为 1。很多读者卡在这一步是因为没往φ 1 φ²上想。归纳法之所以能工作是因为它把“无限多个 N”压缩成“两个基础情况 一次不依赖具体数值的递推”。只要递推这一步只引用归纳假设不引用具体值就能一路推下去。2.3 常见问题排查证明里最容易翻车的四个地方第一个坑是归纳假设用错。证F_(k1) φ^(k1)时F_(k-1)要用假设F_(k-1) φ^(k-1)不能偷懒写成F_(k-1) F_k。一旦把归纳假设换成具体不等式链条就断了。第二个坑是常数因子被随意丢弃。在证明“是 O(N log N)”时常数 2 可以丢但在证明“增速严格更快”或“严格更慢”时常数不能丢。比如N log(N²)和N log N同阶是因为常数 2 恰好在大 O 里可以忽略而不是因为log(N²)就是log N。第三个坑是边界情况漏写。手册 2.22 和 2.24 题专门给了反面案例二分查找里如果Low1, High2则Mid1递归调用后区间没有缩小会无限循环。写递归式时觉得“每次减半”很自然但边界条件一旦写错减半就不成立。第四个坑是把平均情况和最坏情况混为一谈。手册 2.7 题指出随机化算法存在一个极小的概率永远不终止所以它的“最坏运行时间”不能用某个确定的界锁住只能说“以概率 1 终止”。这两个概念在分析里必须分开写。3. 列表、栈、队列与哈希O(LP) 与平均 O(1) 的代价结构3.1 PrintLots 的 O(LP)双指针归并扫描手册 3.2 题给出一段PrintLots的实现。它的目标是从列表 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 ); // 命中位置打印 L 当前元素 Ppos Next( Ppos, P ); // 位置指针前进 } Counter; // 计数器单调递增 Lpos Next( Lpos, L ); // L 指针每轮都推进 } }时间账很简单Lpos从 L 的头走到尾一遍Ppos从 P 的头走到尾一遍Counter单调递增两把指针各自只前进不后退。总迭代次数不超过 L 的长度加 P 的长度所以是 O(LP)。常见误写是“对 P 里每个位置都从头扫一遍 L”那就是 O(L×P)。这段代码之所以快是因为它把“按位置查找”变成了“边走边比对”用 Counter 记住当前在 L 的哪个位置用 Ppos 记住下一个要打印的位置两边同步推进。本质上是一次归并扫描而不是多次随机访问。这里还有一个细节Counter 从 1 开始而不是 0因为位置列表的编号习惯从 1 起。如果从 0 起第一个元素就会永远对不上这是个典型的偏移错误。3.2 哈希表装载因子 λ 如何决定平均探测次数手册第 5 章把哈希冲突处理分成两大类分离链接法和开放定址法。分离链接法的结构是每个槽挂一条链表。查找代价由两部分组成计算哈希值的 O(1)以及遍历链表的 O(1 λ)其中 λ N/M 是装载因子元素数除以表大小。这个式子里“1”是空槽检查“λ”是平均链长。λ 越小链表越短。开放定址法把所有元素都存在表内冲突时按某个探测序列找下一个空槽。手册里讨论了线性探测、平方探测和双散列。线性探测在 λ 接近 1 时会出现“一次聚集”连续被占用的槽连成一片插入和查找的探测次数会急剧上升。按教材给出的结论线性探测在 λ 0.5 时平均成功查找探测次数约为 1.5 次λ 0.9 时会涨到约 5.5 次而失败查找的探测次数增长更快。这个差距说明开放定址法的性能高度依赖装载因子工程上一般把 λ 控制在 0.5 以下超过就触发再散列rehash。再散列的做法是开一张大约两倍大的新表把所有元素重新插入。这一步是 O(N)但摊还到每次插入上是 O(1)。3.3 常见问题排查链表与哈希最容易翻车的几个地方第一个坑是删除链表节点时忘了更新前驱的 next。只free了当前节点却没有把前一个节点的next指向后一个节点链表中间就断了一截后续遍历会读到已释放内存。第二个坑是哈希函数选择导致聚集。如果表大小取 2 的幂而输入数据全是偶数那么所有元素都会落到偶数槽位等于表只用了一半。常见做法是表大小取素数配合取模运算打散分布。第三个坑是开放定址法直接删除元素。线性探测的查找依赖探测链的连续性如果把某个槽直接置空后续元素的查找就会在这条“断链”处提前终止。正确做法是用“懒惰删除”标记tombstone查找时跳过标记插入时可以复用标记位。第四个坑是再散列时机判断错误。装载因子到达阈值后不扩容线性探测的探测次数会指数级上升扩容太早又会浪费空间、增加不必要的重哈希开销。工程上通常在 λ 到 0.5 到 0.75 之间触发取决于探测方式和内存预算。4. 树、堆与排序递归式 T(n)T(n/2)O(n) 怎么收敛4.1 AVL 树的旋转记账高度差锁在 1 的代价AVL 树的定义是任意节点的左右子树高度差不超过 1。这个约束带来的直接好处是树高被锁在 O(log N)查找、插入、删除都是 O(log N)。为什么高度差限制在 1 就能得到 O(log N)设高度为 h 的 AVL 树最少节点数为 S(h)。最稀疏的情况是根节点左右子树高度差恰好为 1于是S(h) S(h-1) S(h-2) 1。这个递推式和斐波那契数列同构解出来S(h)随 h 指数增长反过来 h 就是 O(log N)。插入破坏平衡时靠四种旋转修复LL、RR、LR、RL。以 LL 为例在左子树的左子树插入导致失衡做一次右旋即可。旋转本身是 O(1) 的指针调整但它改变了树的结构所以插入的总代价是 O(log N) 的查找加 O(1) 的旋转。这里的设计取舍很清楚用严格的高度约束换取确定的 O(log N) 上界。代价是插入删除时旋转更频繁写操作比普通二叉搜索树更重。红黑树把约束放松到“最长路径不超过最短路径的两倍”旋转次数减少但树高上界变成 2log N。一个是上界更紧一个是写操作更轻选择取决于读多写少还是写多读少。4.2 堆序维护与堆排序O(N log N) 是怎么推出来的二叉堆的结构性质是“完全二叉树”堆序性质是“每个节点不大于或不小于它的子节点”。这两条性质一起保证了根节点是最小或最大元素。插入操作是“上滤”把新元素放到数组末尾然后不断和父节点比较比父节点小就交换。树高是 O(log N)所以插入是 O(log N)。删除最小元是“下滤”把最后一个元素移到根然后不断和较小的子节点交换路径长度也是 O(log N)。建堆有一个不太直觉的结论从空堆逐个插入是 O(N log N)但把数组原地调整成堆只需要 O(N)。原因是下滤的代价和节点所在高度成正比而大部分节点都在底层高度很小。总代价是Σ (每层节点数 × 该层高度)这个和收敛到 O(N)。这是“下滤建堆”比“逐个插入”快的原因。堆排序的思路是先 O(N) 建最大堆然后反复把堆顶和末尾交换、缩小堆范围、对新堆顶下滤。每次下滤 O(log N)共 N 次总代价 O(N log N)。堆排序的好处是原地、最坏也是 O(N log N)缺点是缓存不友好因为下滤的访问模式是跳跃的实际跑起来常常比快速排序慢。4.3 快速排序的基准选择与最坏 O(N²) 的规避快速排序的平均递归式是T(N) 2T(N/2) O(N)解出来 O(N log N)。最坏情况是每次划分都极不平衡退化成T(N) T(N-1) O(N)解出来 O(N²)。触发最坏情况的典型场景是输入已经有序而基准又固定取第一个元素。此时每次划分一边为空另一边是 N-1 个元素递归深度变成 N。规避手段有三类随机选基准、三数取中、以及“小数组切换插入排序”的阈值优化。随机化的作用是让“坏输入”不再是确定性的对手无法构造出必然触发最坏情况的用例。三数取中则是从首、中、尾三个位置取中位数当基准对已经部分有序的输入更稳健。还有一个工程细节递归到小数组比如长度小于 10时切换成插入排序。插入排序在小数组上的常数因子比快排小而且能减少递归调用层数。这个优化不改变渐进复杂度但对实际运行时间影响明显。4.4 常见问题排查树与排序中的递归边界第一个坑是AVL 旋转后忘记更新高度。旋转只调整了指针节点高度需要沿路径从下往上重新计算。漏更新会导致后续平衡判断基于错误高度树慢慢退化成链表。第二个坑是建堆时从错误的位置开始下滤。正确的起点是最后一个非叶节点下标为N/2 - 10 基。从N-1开始是多余的从 0 开始则会漏掉大量子树。第三个坑是快速排序的划分边界写错。Hoare 划分和 Lomuto 划分的边界条件不同混用会导致死循环或漏元素。写完划分逻辑后用长度为 0、1、2 的数组各跑一遍能挡住大部分边界错误。第四个坑是递归深度没有上限保护。快排最坏递归深度是 N对超大数组可能爆栈。工程实现里要么改成显式栈要么在递归深度超过2 log N时切换到堆排序introsort 的思路。5. 图算法与并查集松弛、路径压缩与摊还代价5.1 Dijkstra 的贪心松弛为什么负权会失效Dijkstra 的核心是一个贪心选择每次从“未确定集合”里取出当前距离最小的节点把它标记为已确定然后用它去松弛邻居。正确性依赖一个前提所有边权非负。为什么负权会破坏这个前提考虑三个节点 A、B、C边 A→B 权为 2A→C 权为 5C→B 权为 -10。从 A 出发先确定 B距离 2再确定 C距离 5然后用 C 松弛 B 得到5 (-10) -5比已确定的 2 更小。但 B 已经被标记为“最终距离”不会再更新结果就错了。根因是贪心选择依赖“当前最小距离不会再变小”这个单调性假设。负权边让这个假设失效所以 Dijkstra 不能处理负权。能处理负权的是 Bellman-Ford它放弃贪心改为对所有边做 V-1 轮松弛代价是 O(VE)。5.2 并查集路径压缩与按秩合并怎么做到近乎 O(1)并查集要支持两个操作Find查根Union合并两个集合。朴素实现的树可能退化成链Find变成 O(N)。第一个优化是按秩合并合并时把矮树挂到高树下避免树高失控。单用这一个优化Find的代价是 O(log N)。第二个优化是路径压缩Find过程中把路径上所有节点直接挂到根上。单用这一个优化摊还代价是 O(log N) 量级。两个优化一起用摊还代价降到 O(α(N))其中 α 是反阿克曼函数增长极慢对任何实际输入都不超过 4。这就是“近乎 O(1)”的来源。这里有一个常见误解路径压缩之后“秩”不再是精确的树高只是高度的一个上界。所以按秩合并里的“秩”比较的是上界而不是真实高度。这不影响正确性因为上界比较仍然能控制树高。5.3 摊还分析二项队列的记账法摊还分析解决的是“单次操作可能很贵但一串操作平均下来很便宜”这类问题。手册第 11 章用二项队列做例子。二项队列由一组二项树组成每棵树的阶数对应二进制位。插入操作相当于“二进制加一”如果最低位为空直接放一棵 0 阶树如果已有 0 阶树就合并成 1 阶树再检查 1 阶位依此类推。单次插入最坏要合并 O(log N) 次看起来是 O(log N)。但用记账法分析每次合并会让树的数量减少一棵而每次插入最多增加一棵树。把“插入一棵树”记 1 个信用合并时消耗一个信用则总信用非负。摊还下来每次插入是 O(1)。这个分析的要点是不能用单次最坏情况代表整体要看操作序列里“贵操作”被“便宜操作”补贴的关系。二项队列的插入就是典型的“便宜操作攒信用、贵操作花信用”。5.4 常见问题排查图算法与摊还分析里的坑第一个坑是Dijkstra 用错数据结构。用邻接矩阵加线性扫描找最小距离复杂度是 O(V²)用邻接表加优先队列复杂度是 O((VE) log V)。稀疏图上前者会慢一个量级。第二个坑是并查集只做路径压缩、不做按秩合并。单用路径压缩摊还代价是 O(log N) 而非 O(α(N))。两个优化要一起用才能拿到最好的界。第三个坑是摊还分析的信用体系不自洽。分析二项队列时如果只给插入记信用、忘了给合并后的树也记信用总信用会算成负数结论就错了。记账法的前提是“任意前缀的信用非负”。第四个坑是把摊还代价当成单次最坏代价。摊还 O(1) 不意味着每次操作都是 O(1)它只保证一串操作的平均值。对延迟敏感的场景单次最坏 O(log N) 可能仍然不可接受需要换成最坏情况也有界的结构。6. 设计取舍从答案手册里读到的工程判据这份手册最容易被低估的地方是它把“结论”和“证明”之间的推导全部摊开了。看完第 2 章的增长率排序再回头看第 4 章的 AVL 旋转和第 5 章的摊还分析会发现它们共享同一个思维框架先确定一个可验证的界再讨论怎么在界内做取舍。几个贯穿全书的取舍模式值得单独拎出来。第一是严格约束换确定上界AVL 把高度差锁在 1拿到严格 O(log N)代价是旋转更频繁红黑树放松约束写操作更轻但上界变成 2log N。第二是摊还换单次最坏二项队列的插入摊还 O(1)但单次可能 O(log N)并查集的路径压缩摊还 O(α(N))但单次 Find 仍可能走一条长链。第三是空间换时间哈希表用额外空间把查找压到平均 O(1)分离链接法用链表换冲突容忍度开放定址法用探测换空间紧凑。验证这些取舍是否选对我的习惯是三步先写出渐进表达式把它放进第 2 章那条增长率序列里定位再找最坏输入看表达式会不会退化最后用摊还分析的记账法检查“一串操作”的总代价是否和单次最坏一致。三步走完一个结构在该场景下值不值得用基本就有答案了。手册里那些被省略的“细节留给读者”的部分恰恰是这套判据最需要练手的地方。照着它的证明链条自己推一遍比对着答案点头有用得多。从那以后我每次评估一个数据结构选型都强制自己先写出递推式、再跑一遍最坏输入、最后算一次摊还账三步缺一不可。希望帮到你。本文还有配套的精品资源点击获取