简介：这份 PDF 是 Mark Allen Weiss《Data Structures and Algorithm Analysis in C》第二版的配套习题解答手册，面向学习数据结构与算法分析课程、希望对照课后练习查漏补缺的本科生和自学者。内容按教材章节展开，涵盖算法复杂度与大 O 分析、列表栈队列、树、哈希表、优先队列、排序、不相交集合、图算法、算法设计技巧、摊还分析及高级数据结构等主题；解答多采用伪 C 代码，并有意保留部分细节供读者自行推导，通常省略编程作业和章末引用题。包内仅有 1 个 PDF 文件，大小约 233KB，便于携带和快速检索，目前已有 143 人学习。它适合用来核对练习思路、理解复杂度证明与代码框架，也可按章节编号定位对应知识点，尤其有助于理解递归、搜索、排序与图算法的实现取舍，作为教材阅读、课程复习和自测阶段的辅助材料。

1. 从一本教材的答案册说起：数据结构与算法分析（C 语言第二版）里没讲透的那半块

刷课后题最难受的不是不会，而是不确定自己会。教材把证明留给读者，题目只给结论，你写完第 1 章的归纳法，心里没底；翻遍全书也找不到“这一步为什么可以这样放缩”。这份《数据结构与算法分析：C 语言描述》第二版的解答手册正好补这半块——它覆盖第 1 到第 12 章的大部分习题，从舍入误差处理、递归展开#include，到增长率排序、随机置换算法、快速幂、多数元素线性解法，给的是推导链条和伪 C 代码，不是最终答案。适合两类人：正在跟教材逐章刷题的学生，和想回头复习复杂度分析的从业者。它替代不了教材，是教材的对照物。

2. 手册的骨架：12 章对应关系与「哪些题可以先跳过」

拿到一份 66 页的解答手册，很多人第一反应是从第 1 页开始顺读，读到第 4 章树的部分发现全是跳跃的推导，于是放弃。这份手册不是按“教学顺序”写的，它按“题号顺序”写，密度极不均匀。先把骨架摸清，再决定读哪几段，效率差好几倍。

2.1 用页码范围反推答案密度

手册目录里每章都标了起始页，这组数字本身就是地图。把相邻起始页相减，就能算出每章占多少页，进一步估出“这章值得花多少时间”。我整理成下面这张表，读之前先扫一眼。

页跨度只说明篇幅，不说明难度。第 11 章摊还分析只有 3 页，但它是全书最容易翻车的地方，因为摊还分析要靠“势能”或“记账”两套语言互相印证，答案写得越短，你补的越多。反过来第 5 章哈希 4 页，基本是探测序列和装填因子的结论，自己拿纸算一遍就能对上。

我的一般做法是：先读页跨度大的四章（4、9、10、6），把推导套路吃透；页跨度小的章节只在做题卡住时定向查，不做通读。这样一轮下来花的时间差不多，但拿到的可复用方法多得多。

2.2 两类题注定没有答案，别在这里耗

手册前言里有一句很关键的话，大意是：明显属于编程大作业的题目，以及解答在章末参考文献里被指路的题目，都被省略了。这句话决定了你的检索策略——如果你在某道“请实现一个 XXX”或者“参见某某文献”的题上翻遍手册找不到对应题号，那不是漏印，是设计如此。

常见做法是分两条路补：

第一条，编程实现类题目，回到教材正文找接口签名。教材在讲某个 ADT 时通常已经给了函数原型和关键不变量，你把签名抄下来，先写空实现保证能编译，再逐个填函数体。这类题的价值不在答案，在于你能不能自己设计测试用例，比如对一个栈 ADT，至少要有空栈弹出、连续压弹、容量边界三组用例。

第二条，文献指路类题目，直接放弃“找标准答案”的念头，改成“找结论”。这类题一般是要你验证某个已知定理或者比较两种实现，你只需要把教材正文里对应的结论抄在题号旁边，写一句“此处结论来自正文第 X 节”，就算完成。硬啃参考文献的收益极低，尤其是当你只是想把整本书过一遍的时候。

我自己踩过的坑是：曾经花两个晚上试图给一道“实现优先队列并比较两种建堆方式”的题写出完美答案，最后发现手册里根本没这题，而教材正文的图里已经把两种建堆的代价曲线画出来了。血泪经验是，先花十分钟翻目录和前言确认范围，比闷头写两天划算。

2.3 给题号建一张自己的索引表

手册的题号是跟教材绑定的，但教材不同印次会有题号微调，这一点后面避坑章会细说。所以不要直接在 PDF 上做批注，另开一个表格维护自己的索引，字段至少包含五项。

这张表看起来笨，但它是把“读一遍”变成“能复查”的唯一办法。手册的解答完整度参差不齐，作者在前言里也承认“细节一般留给读者”，所以你的差异栏里出现“我多写了一步放缩”是常态，出现“结论完全不同”才是需要警惕的信号。

2.4 伪代码不是代码，读的时候要“翻译”

手册里的程序明确是伪 C 风格，不是能直接编译的完整代码：缺头文件、缺类型定义、缺边界检查，有些函数名后面还挂着奇怪的字母。正确读法是把它当成“带语法糖的算法描述”，关注三件事：循环不变式是什么、每轮迭代推进了哪个游标、退出条件覆盖了哪些边界。

比如第 3 章那道按位置序列打印链表元素的题，函数体只有几行，但信息量全在“谁每轮只前进一步、谁在命中时才前进”这个细节上。你把这两个游标的推进条件抄在纸上，复杂度 O(L+P) 自然就出来了，不需要背结论。

3. 算法分析这一章最容易被浪费：增长率排序与反例构造怎么用

第 2 章只有 3 页，很多人十分钟扫完就过去了，结果后面每一章的复杂度分析都在靠感觉。这一章其实是整本手册里“单位时间收益”最高的一章，因为它教的是判断方法，不是知识点。下面把它拆成四块，每块都能直接抄去用。

3.1 增长率排序：先把嵌套的对数拆开

题目给出一串函数要排序，形如 2/N、37、含根号的一项、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 无关的项挑出来放最前：常数类（37、含根号的常数项）永远排在最左，2/N 是递减函数，比任何正常数都小，排第一。

第二步，把所有带对数的项做化简。这一步是分水岭：N log(N²) 里的 log(N²) 等于 2 log N，所以 N log(N²) 和 N log N 是同一阶，只是差一个常数因子。很多人在这里把 N log(N²) 排到 N log²N 右边，直接错。

第三步，按“多项式次数”排主体，再插指数。整理后的顺序是：

这张表的价值不在结论，在“化简再比较”这个动作。凡是看到对数套在括号里，先问一句能不能提出来变成系数；凡是有两个项的差别只在一个常数上，它们就不该被排成前后关系。判据统一之后，这一章剩下的题都好办。

3.2 判断题：证伪只需要一个反例

第 2 章还有一类题是给若干命题判真假。手册在这种题上给得非常节省：只标 True / False，再配两三行反例，例如用 T1=2N、T2=N、f(N)=N 这一组去推翻某个命题，又用 T1=N²、T2=N、f(N)=N² 这一组去推翻另外两问。要复现这套思路，关键是把 f(N) 理解成“一把上界尺子”。

具体做法是三步走。第一步，写清定义：T(N)=O(f(N)) 意味着存在常数 c 和 n0，使得 N≥n0 时 T(N)≤c·f(N)。第二步，如果命题说“两个都是 O(f)，则它们的某种组合也是 O(f)”，先想这个组合会不会把 f 的阶放大，比如相加不会、相除会。第三步，如果找不到证明，就去构造两个函数，让它们在 f 这把尺子下都合格，但组合之后超界。

这里有个容易被忽略的点：反例不必复杂。手册用的反例都是最简单的线性或平方函数，因为判断题考的是“你有没有理解上界的宽松性”，不是考你能不能构造精巧的怪函数。我在复习时会强制自己给每个 False 写一句“这个反例利用了 f 的哪条性质”，写不出来就说明我其实没懂，只是记住了结论。

另一道相关题更有意思：给两个函数 f 和 g，f 在 N 为偶数时取 1、奇数时取 N，g 反过来，于是 f/g 的比值在 0 和无穷之间来回振荡。这题的作用是打掉“比值必有极限”的直觉。遇到这类题，我建议直接在纸上列 N=1,2,3,4 四行数值，把 f、g、比值三列填出来，振荡肉眼可见，比看文字推导快得多。

3.3 把归纳证明写成四步模板

第 1 章那道 log X ≤ X 的证明，是全书归纳法的样板题。手册给的推导链不算长，但结构很典型，我把它固化成四步，后面所有同类证明都套这个模板。

第一步，划定基础区间。先验证 0<X≤1：此时 log X ≤0，而 X>0，结论显然成立。再验证 1<X≤2：此时 log X ≤1，而 X>1，也成立。基础区间之所以要分成两段，是因为在对数函数上，小于 1 和大于 1 的行为不一样，一段盖不住。

第二步，设定归纳假设的形式。手册的做法是按“区间加倍”归纳：假设命题在 p<X≤2p 上成立，p 为正整数。注意这里的归纳变量不是 N，而是区间的上界，这是很多人卡住的地方。

第三步，处理翻倍区间。取 2p<Y≤4p，则 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>2）。整条链每一步都只用一个已知条件，没有跳步，这就是“可复现”的标准。

同一章还有一道斐波那契的界证明，用的是 φ+1=φ² 这个恒等式，由此推出 φ⁻¹+φ⁻²=1，再把 F(k+1)=F(k)+F(k−1) 的两项分别用归纳假设放大，最后合并系数。套路和上面完全一致：找恒等式、代假设、合并。我一般会在笔记里把这两道题并排放，标注“同一模板的两个实例”，复习时一眼就能看出共性。

3.4 循环上界相乘会高估：六段程序给出的教训

第 2 章有一组题给了六段嵌套程序让你估复杂度。前四段是常规的 O(N)、O(N²)、O(N³)、O(N²)，第五段因为两层循环的上界互相依赖，算出来是 O(N⁵)。真正有价值的是第六段：一段三层嵌套，最内层看起来很吓人，但中间那层if为真的次数远少于判断次数。

示意结构大致如下：

/* 手册 2.6 第 (VI) 段的等价结构：判断次数远多于命中次数 */ for (i = 1; i <= N; i++) { for (j = 1; j <= i * i; j++) { /* 判断总次数约 N^3/3 */ if (/* 命中条件，每个 i 只成立有限次 */) { for (k = 0; k < j * j; k++) /* 单次命中内部代价 O(N^2) */ work(); } } }

逻辑说明：外层 i 走 N 次，中层 j 的上界是 i²，所以if的判断总次数是 Σi² ≈ N³/3，看着像 O(N³)。但命中次数只有 O(N²)，而每次命中要跑 O(N²) 的内层，乘起来是 O(N⁴)。

参数说明：这里的 N 是输入规模，i² 和 j² 是题目给定的上界表达式，不是随手写的。改动任何一个上界都会改变结论，比如把 j 的上界改成 N，命中次数不变但判断次数降到 O(N²)，总代价就变成 O(N³)。

这段代码给出的教训是：循环层数相乘只是复杂度的上界，真正的界要看“最内层实际执行了多少次”。我后来看任何嵌套循环，都先问一句“最内层被执行了几次”，而不是先数有几层 for。

4. 递归与指针题的手推流程：链表、树、哈希、堆各用一张表

第 3 到第 9 章的题，光看答案没用，必须自己在纸上推一遍。但推也得有章法，漫无目的地画图只会越画越乱。这一章按数据结构类型给出四套手推流程，每套都配一张能直接填的表。

4.1 链表题：先固定游标，再谈推进条件

第 3 章开头那道按位置序列打印链表元素的题，是链表题的典型形态：给两个链表 L 和 P，P 里存的是位置序号，要求按 P 的顺序打印 L 中对应位置的元素。手册给的函数只有十几行，但两个游标的推进节奏是全部考点。

等价结构如下：

/* PrintLots：按 P 中的位置序列打印 L 的对应元素 */ 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++) { /* 位置命中：打印并推进 P */ printf("%d ", Lpos->Element); Ppos = Next(Ppos, P); } Lpos = Next(Lpos, L); /* L 每轮固定走一步 */ } }

逻辑说明：用一个自增计数器模拟“L 当前走到第几个位置”。每轮先比较 P 当前位置的值和计数器，命中就打印并让 P 前进一格；无论是否命中，L 都前进一格。这样 L 只遍历一次，P 也只遍历一次。

参数说明：Counter从 1 开始，对应“第一个元素”的语义；如果题目要求从 0 开始编号，这里要改成 0，否则整体错位一格。循环的退出条件是任一链表走空，这意味着如果 P 中出现了超过 L 长度的位置，函数会静默结束而不报错——这是伪代码的省略，不是设计意图，自己实现时应该补一个越界断言。

复杂度是 O(|L|+|P|)，因为两个链表各走一遍，没有嵌套。这个结论有个隐含前提：P 中的位置序列是递增的。如果 P 无序，这个一趟扫描的写法直接失效，得改成先建索引或者反复扫描。手册没有强调这一点，我第一遍读的时候也没注意，后来自己写测试用例才翻车。

4.2 树与递归题：先写边界，再写递推

第 4 章树的部分占 11 页，是全书最厚的一章，题目形态集中在“给定递归结构，求时间界”和“改造递归，降低空间占用”两类。以第 2 章那道多数元素题为例（它虽然在第 2 章，但解法是标准的递归分治），手册给的思路可以拆成四步。

第一步，写递推式。T(N)=T(N/2)+O(N)，其中 O(N) 是每层扫描的代价。第二步，展开。按主定理，a=1、b=2、f(N)=O(N)，落在 f(N) 大于 N^log_b(a)=N^0 的情形，总量由顶层决定，得 O(N)。第三步，处理奇偶边界：如果 N 是奇数，先忽略最后一个元素再递归，因为最后一个元素不可能单独构成多数。第四步，处理“无多数”的情形：如果递归回来没有得到候选，就把被忽略的那个元素当作候选返回。

这四步里，第三步和第四步是手册点到的细节，也是自己写的时候最容易漏的。我的做法是在纸上画一个 N=5 的小例子，元素为 [3,3,3,1,2]，手动跑一遍“忽略最后一个、递归、回填候选”的流程，跑通了再写代码。

同一章还有一类题是问“递归是否可以避免”“能不能只用两份数组”。手册的答案给的是：原递归策略会用到 O(log N) 份数组副本，改成在原数组上就地放置可以压到两份。这类题的通用推法是把递归树画出来，数一数同时存活的副本数，而不是凭感觉答。

4.3 哈希与堆：用表算，不要用眼看

哈希和堆这两章的题，答案往往是一串数字，看是看不出来的，必须列表。哈希题我一般建三列：插入序列、哈希值、实际落位。以表长 10、除余法为例，依次插入 12、22、32、42，线性探测下的落位是这样的：

这张表能直接回答两类问题：一是平均探测次数，把最后一列求和除以元素个数；二是装填因子对性能的影响，当表里元素继续增加、探测长度开始成串增长时，你会在表上看到连续的非空槽位，这就是“一次聚集”。手册在哈希这章给出的多是结论性说明，你得靠这张表把结论还原成过程。

堆的题同理。建堆的线性时间结论（O(N)）很多人背下来了但不会证，实际推法是：从第 ⌊N/2⌋ 个元素开始向前逐个下滤，每个位置的下滤代价与它的高度成正比，而高度为 h 的节点最多有 ⌊N/2^(h+1)⌋ 个，求和后收敛到 O(N)。手推的时候，我建议拿 7 个元素的小堆画三轮：第一轮处理下标 3，第二轮下标 2，第三轮下标 1，每轮记一次交换次数，加起来的量级和公式对得上，你就真信了。

4.4 图算法题：三张表覆盖绝大多数手算

第 9 章图算法 9 页，题目几乎都能用三张表解决。

第一张是 Dijkstra 的距离表。列是顶点，行是每一轮选中的顶点，格子里填“当前最短距离 / 前驱”。每轮选距离最小的未访问顶点，然后松弛它的邻居。手算时一定要把“已确定”的顶点划掉，否则会在原地打转。

第二张是并查集的父指针表。列是元素，格子填父节点，路径压缩后要把沿途所有节点直接指向根。第 8 章不相交集只有 3 页，但这张表能覆盖它的全部操作题。

第三张是 Kruskal 或 Prim 的边选择表。列是轮次，格子填“选中的边、当前连通分量、是否成环”。成环判断直接查第二张表，两张表配合使用。

这三张表的共同点是：不依赖灵感，只依赖“每轮做一次确定的操作并记录”。我在复习图算法时，会把同一道题用 Dijkstra 和 Floyd 各算一遍，对比两个结果矩阵，如果对不上，说明某一步松弛漏了。这种交叉验证比反复看答案有效得多。

5. 避坑：翻这份手册最容易踩的五个坑

这份手册是从排版文件导出的 PDF，加上它本身是“答案”而非“教材”，读起来有几类固定的坑。下面五条都是实际翻车过的，每条按现象、原因、解决写。

5.1 函数名里挂着孤立的字母 O

现象：函数名写成SeparateO、ProcessFileO，变量写成XO、NO、log XO，读起来像乱码，复制到编辑器里编译不过。

原因：原始文档里斜体、上下标的排版标记在导出时被拍平成字母 O，粘在标识符后面。这类残留遍布全书，尤其是第 1 章和第 2 章的数学推导。

解决：读的时候心里默念“孤立的 O 是空字符”，把ProcessFileO读成ProcessFile、log XO读成log X。如果要复制代码，先用编辑器做一次全局替换，把紧跟在标识符或右括号后的单个大写 O 删掉，替换前务必肉眼抽查十几处，避免误伤正常变量名。

5.2 题号对不上：印次差异

现象：按教材第 5 章的题号去手册里找，找到的答案讲的却是另一个问题。

原因：手册前言里明确说了，这些答案对应的是教材第一印次的状态。教材后续印次修过错误，个别题目被调整或替换，题号就会错位。

解决：不要用题号做主键，用题面关键词做主键。定位时先在教材里抄下题目的核心对象（例如“最小堆”“开放定址”“拓扑排序”），再去手册对应章节里按关键词扫，命中率比按题号高得多。前面 2.3 那张索引表就是为这个准备的。

5.3 答案只给一句“细节留给读者”

现象：一道题你卡了两小时，翻到答案只有两行，最后一句是“其余细节由读者补全”。

原因：手册的定位是答案册而不是讲义，完整度本来就不一致，作者在前言里已经声明“一般性的细节留给读者”。

解决：把这类答案当“方向确认”用，不当“过程参考”用。具体补法有三条：回到教材正文找对应定理；用一个小规模实例手算，反推中间步骤；把答案的那两行当作结论，自己从结论往前倒推需要哪些引理。三条里至少走通一条，再回到题目重写一遍。

5.4 把手册的解当成唯一解

现象：你算出 O(N log N)，手册写 O(N² log N)，于是怀疑自己算错。

原因：同一道题可能问的是不同算法的不同指标。以随机置换那组题为例，三个算法的期望代价分别是 O(N² log N)、O(N log N)、O(N)，差距是数量级的；而最坏情况下的结论又完全不同——前两个算法的最坏运行时间根本无法用一个有限界刻画，因为存在“永远不终止”的非零概率，第三个算法则是严格线性的。

解决：看答案前先确认三件事：问的是期望还是最坏、问的是时间还是空间、问的是哪个算法。这三条确认完，再对数字。对不上时先怀疑问题理解，最后才怀疑自己的推导。

5.5 理论线性、实测不线性

现象：按答案，某个算法是线性的，你跑了一遍发现 N 变大后耗时暴涨。

原因：手册在那一题里补了一句限定——线性结论成立的前提是机器有足够内存。内存不够时，大规模输入会触发频繁换页，曲线立刻翘起来，看起来像超线性。

解决：做实测验证时，把内存占用一起打印出来，和耗时曲线并排放。如果耗时拐点和内存拐点重合，问题在内存不在算法。另外，理论分析里的“单位时间操作”假设和真实机器的缓存行为差得很远，实测只能验证量级趋势，别拿常数因子去对答案。

6. 把答案册变成自测工具：三条我一直在用的验证技巧

答案册最大的风险是“看懂了”和“会做了”之间的错觉。我后来给自己定了个规矩：每读完一章，必须用三种方式各验证一次，全都过才算这章翻篇。

第一种，用脚本验证增长率结论。排序那类题光靠脑补容易出错，直接跑数值对比，几十行就够：

import math # 待排序的函数序列，键是名字，值是可调用对象 seq = [ ("2/N", lambda n: 2 / n), ("37", lambda n: 37), ("N", lambda n: n), ("N loglog N", lambda n: n * math.log2(math.log2(n))), ("N logN", lambda n: n * math.log2(n)), ("N log(N^2)", lambda n: n * math.log2(n * n)), # 应恒等于 2N logN ("N log^2 N", lambda n: n * math.log2(n) ** 2), ("N^1.5", lambda n: n ** 1.5), ("N^2", lambda n: n * n), ] for N in (2 ** 10, 2 ** 16, 2 ** 20): order = sorted(seq, key=lambda kv: kv[1](N)) print(N, [name for name, _ in order])

逻辑说明：对每个 N，按函数值排序，输出名字序列。三个 N 的输出应该基本一致，如果某个位置在 N 变大时发生翻转，说明这两项同阶或者你的化简有问题。

参数说明：N 取 2 的幂是为了让 log 计算落在整数附近，减少浮点噪音；N log(N^2)那一项特意写成原样而不是化简形式，就是为了让你亲眼看到它和N logN永远相邻——它们只差常数 2，排序时随时可能互换位置，这是正常现象。

第二种，用错答清单反向出题。前面那张索引表里的“待复核”列，攒到十几条之后，把它们单独抽出来，遮住答案重做一遍，只做这些。这比从头再刷一遍全书省八成时间，而且专打你的薄弱点。

第三种，给每道手算题配一个可复现的小输入。哈希题用 8 到 10 个元素、表长取质数；堆题用 7 到 15 个元素；图题用 5 到 6 个顶点、边权取个位数。规模必须小到能在纸上完整画完，否则你会在中途放弃，然后回去看答案。

这套流程唯一的成本是前期建表，但建完之后，这份 66 页的手册就变成了一份可查询、可验证、可复现的自测题库。我最早是把它当 PDF 从头翻到尾，翻完什么也没留下；从那以后我每读完一章都强制走一遍“脚本 + 错答清单 + 小输入手算”，宁可慢一点，也要让每一页都留下能复查的痕迹。这份手册在常见的电子书归档和课程资料盘里能搜到，文件名里通常带 solutions manual，下载时注意区分第二版和更早的版本，版本不对题号会整片错位。希望帮到你。

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