简介这份 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 用页码范围反推答案密度手册目录里每章都标了起始页这组数字本身就是地图。把相邻起始页相减就能算出每章占多少页进一步估出“这章值得花多少时间”。我整理成下面这张表读之前先扫一眼。章主题起始页页跨度答案密度判断1引论13低只有零星几题多为数学归纳2算法分析43高一页压好几题增长率与反例集中在这3表、栈、队列77中含完整函数级伪代码4树1411最高递归推导密集最值得精读5哈希254中低多为结论性说明6优先队列堆297中含建堆与操作代价分析7排序366中算法对比与界分析8不相交集 ADT423低快读即可9图算法459高手算流程多10算法设计技巧549高动态规划与贪心的推导11摊还分析633低但难页少不等于简单12高级数据结构661 页起低多为提示性内容页跨度只说明篇幅不说明难度。第 11 章摊还分析只有 3 页但它是全书最容易翻车的地方因为摊还分析要靠“势能”或“记账”两套语言互相印证答案写得越短你补的越多。反过来第 5 章哈希 4 页基本是探测序列和装填因子的结论自己拿纸算一遍就能对上。我的一般做法是先读页跨度大的四章4、9、10、6把推导套路吃透页跨度小的章节只在做题卡住时定向查不做通读。这样一轮下来花的时间差不多但拿到的可复用方法多得多。2.2 两类题注定没有答案别在这里耗手册前言里有一句很关键的话大意是明显属于编程大作业的题目以及解答在章末参考文献里被指路的题目都被省略了。这句话决定了你的检索策略——如果你在某道“请实现一个 XXX”或者“参见某某文献”的题上翻遍手册找不到对应题号那不是漏印是设计如此。常见做法是分两条路补第一条编程实现类题目回到教材正文找接口签名。教材在讲某个 ADT 时通常已经给了函数原型和关键不变量你把签名抄下来先写空实现保证能编译再逐个填函数体。这类题的价值不在答案在于你能不能自己设计测试用例比如对一个栈 ADT至少要有空栈弹出、连续压弹、容量边界三组用例。第二条文献指路类题目直接放弃“找标准答案”的念头改成“找结论”。这类题一般是要你验证某个已知定理或者比较两种实现你只需要把教材正文里对应的结论抄在题号旁边写一句“此处结论来自正文第 X 节”就算完成。硬啃参考文献的收益极低尤其是当你只是想把整本书过一遍的时候。我自己踩过的坑是曾经花两个晚上试图给一道“实现优先队列并比较两种建堆方式”的题写出完美答案最后发现手册里根本没这题而教材正文的图里已经把两种建堆的代价曲线画出来了。血泪经验是先花十分钟翻目录和前言确认范围比闷头写两天划算。2.3 给题号建一张自己的索引表手册的题号是跟教材绑定的但教材不同印次会有题号微调这一点后面避坑章会细说。所以不要直接在 PDF 上做批注另开一个表格维护自己的索引字段至少包含五项。字段填什么为什么需要教材题号例如 2.19与手册对齐的主键题面关键词例如“多数元素 线性时间”题号错位时靠它对齐手册页码例如 5二次查阅时的定位我的答案差异一句话写清哪里不一样复习时只看差异不重读待复核标记是 / 否决定第二轮要不要重做这张表看起来笨但它是把“读一遍”变成“能复查”的唯一办法。手册的解答完整度参差不齐作者在前言里也承认“细节一般留给读者”所以你的差异栏里出现“我多写了一步放缩”是常态出现“结论完全不同”才是需要警惕的信号。2.4 伪代码不是代码读的时候要“翻译”手册里的程序明确是伪 C 风格不是能直接编译的完整代码缺头文件、缺类型定义、缺边界检查有些函数名后面还挂着奇怪的字母。正确读法是把它当成“带语法糖的算法描述”关注三件事循环不变式是什么、每轮迭代推进了哪个游标、退出条件覆盖了哪些边界。比如第 3 章那道按位置序列打印链表元素的题函数体只有几行但信息量全在“谁每轮只前进一步、谁在命中时才前进”这个细节上。你把这两个游标的推进条件抄在纸上复杂度 O(LP) 自然就出来了不需要背结论。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 右边直接错。第三步按“多项式次数”排主体再插指数。整理后的顺序是位置项化简 / 判据12/N递减N 增大时趋零237常数3常数的平方根项与 N 无关4N线性基准5N log log N比线性多一层极慢的对数6N log N与 N log(N²) 同阶7N log(N²)等于 2N log N与上一项并列8N log²N对数被平方压过上一项9N^1.5多项式次数 1.510N²二次11N² log N二次再乘对数12N³三次132^(N/2)指数底数 2 的半步142^N增长最快这张表的价值不在结论在“化简再比较”这个动作。凡是看到对数套在括号里先问一句能不能提出来变成系数凡是有两个项的差别只在一个常数上它们就不该被排成前后关系。判据统一之后这一章剩下的题都好办。3.2 判断题证伪只需要一个反例第 2 章还有一类题是给若干命题判真假。手册在这种题上给得非常节省只标 True / False再配两三行反例例如用 T12N、T2N、f(N)N 这一组去推翻某个命题又用 T1N²、T2N、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 和 gf 在 N 为偶数时取 1、奇数时取 Ng 反过来于是 f/g 的比值在 0 和无穷之间来回振荡。这题的作用是打掉“比值必有极限”的直觉。遇到这类题我建议直接在纸上列 N1,2,3,4 四行数值把 f、g、比值三列填出来振荡肉眼可见比看文字推导快得多。3.3 把归纳证明写成四步模板第 1 章那道 log X ≤ X 的证明是全书归纳法的样板题。手册给的推导链不算长但结构很典型我把它固化成四步后面所有同类证明都套这个模板。第一步划定基础区间。先验证 0X≤1此时 log X ≤0而 X0结论显然成立。再验证 1X≤2此时 log X ≤1而 X1也成立。基础区间之所以要分成两段是因为在对数函数上小于 1 和大于 1 的行为不一样一段盖不住。第二步设定归纳假设的形式。手册的做法是按“区间加倍”归纳假设命题在 pX≤2p 上成立p 为正整数。注意这里的归纳变量不是 N而是区间的上界这是很多人卡住的地方。第三步处理翻倍区间。取 2pY≤4p则 Y/2 落在 pY/2≤2p 里正好命中归纳假设于是 log(Y/2)Y/2。第四步拼放缩链。log Y 1 log(Y/2) 1 Y/2 ≤ Y/2 Y/2 Y最后一步用的是 1≤Y/2因为 Y2。整条链每一步都只用一个已知条件没有跳步这就是“可复现”的标准。同一章还有一道斐波那契的界证明用的是 φ1φ² 这个恒等式由此推出 φ⁻¹φ⁻²1再把 F(k1)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 和 PP 里存的是位置序号要求按 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) 是每层扫描的代价。第二步展开。按主定理a1、b2、f(N)O(N)落在 f(N) 大于 N^log_b(a)N^0 的情形总量由顶层决定得 O(N)。第三步处理奇偶边界如果 N 是奇数先忽略最后一个元素再递归因为最后一个元素不可能单独构成多数。第四步处理“无多数”的情形如果递归回来没有得到候选就把被忽略的那个元素当作候选返回。这四步里第三步和第四步是手册点到的细节也是自己写的时候最容易漏的。我的做法是在纸上画一个 N5 的小例子元素为 [3,3,3,1,2]手动跑一遍“忽略最后一个、递归、回填候选”的流程跑通了再写代码。同一章还有一类题是问“递归是否可以避免”“能不能只用两份数组”。手册的答案给的是原递归策略会用到 O(log N) 份数组副本改成在原数组上就地放置可以压到两份。这类题的通用推法是把递归树画出来数一数同时存活的副本数而不是凭感觉答。4.3 哈希与堆用表算不要用眼看哈希和堆这两章的题答案往往是一串数字看是看不出来的必须列表。哈希题我一般建三列插入序列、哈希值、实际落位。以表长 10、除余法为例依次插入 12、22、32、42线性探测下的落位是这样的插入值h(k)k%10实际落位探测次数12221222323224342254这张表能直接回答两类问题一是平均探测次数把最后一列求和除以元素个数二是装填因子对性能的影响当表里元素继续增加、探测长度开始成串增长时你会在表上看到连续的非空槽位这就是“一次聚集”。手册在哈希这章给出的多是结论性说明你得靠这张表把结论还原成过程。堆的题同理。建堆的线性时间结论O(N)很多人背下来了但不会证实际推法是从第 ⌊N/2⌋ 个元素开始向前逐个下滤每个位置的下滤代价与它的高度成正比而高度为 h 的节点最多有 ⌊N/2^(h1)⌋ 个求和后收敛到 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, keylambda 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 个顶点、边权取个位数。规模必须小到能在纸上完整画完否则你会在中途放弃然后回去看答案。技巧适用章节单次耗时判断通过的标准脚本验证增长率第 1、2 章10 分钟三个 N 的排序结果一致错答清单重做全书30 分钟差异栏清零小输入手算第 3 到 9 章15 分钟手算结果与答案逐项对上这套流程唯一的成本是前期建表但建完之后这份 66 页的手册就变成了一份可查询、可验证、可复现的自测题库。我最早是把它当 PDF 从头翻到尾翻完什么也没留下从那以后我每读完一章都强制走一遍“脚本 错答清单 小输入手算”宁可慢一点也要让每一页都留下能复查的痕迹。这份手册在常见的电子书归档和课程资料盘里能搜到文件名里通常带 solutions manual下载时注意区分第二版和更早的版本版本不对题号会整片错位。希望帮到你。本文还有配套的精品资源点击获取
简介这份 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 用页码范围反推答案密度手册目录里每章都标了起始页这组数字本身就是地图。把相邻起始页相减就能算出每章占多少页进一步估出“这章值得花多少时间”。我整理成下面这张表读之前先扫一眼。章主题起始页页跨度答案密度判断1引论13低只有零星几题多为数学归纳2算法分析43高一页压好几题增长率与反例集中在这3表、栈、队列77中含完整函数级伪代码4树1411最高递归推导密集最值得精读5哈希254中低多为结论性说明6优先队列堆297中含建堆与操作代价分析7排序366中算法对比与界分析8不相交集 ADT423低快读即可9图算法459高手算流程多10算法设计技巧549高动态规划与贪心的推导11摊还分析633低但难页少不等于简单12高级数据结构661 页起低多为提示性内容页跨度只说明篇幅不说明难度。第 11 章摊还分析只有 3 页但它是全书最容易翻车的地方因为摊还分析要靠“势能”或“记账”两套语言互相印证答案写得越短你补的越多。反过来第 5 章哈希 4 页基本是探测序列和装填因子的结论自己拿纸算一遍就能对上。我的一般做法是先读页跨度大的四章4、9、10、6把推导套路吃透页跨度小的章节只在做题卡住时定向查不做通读。这样一轮下来花的时间差不多但拿到的可复用方法多得多。2.2 两类题注定没有答案别在这里耗手册前言里有一句很关键的话大意是明显属于编程大作业的题目以及解答在章末参考文献里被指路的题目都被省略了。这句话决定了你的检索策略——如果你在某道“请实现一个 XXX”或者“参见某某文献”的题上翻遍手册找不到对应题号那不是漏印是设计如此。常见做法是分两条路补第一条编程实现类题目回到教材正文找接口签名。教材在讲某个 ADT 时通常已经给了函数原型和关键不变量你把签名抄下来先写空实现保证能编译再逐个填函数体。这类题的价值不在答案在于你能不能自己设计测试用例比如对一个栈 ADT至少要有空栈弹出、连续压弹、容量边界三组用例。第二条文献指路类题目直接放弃“找标准答案”的念头改成“找结论”。这类题一般是要你验证某个已知定理或者比较两种实现你只需要把教材正文里对应的结论抄在题号旁边写一句“此处结论来自正文第 X 节”就算完成。硬啃参考文献的收益极低尤其是当你只是想把整本书过一遍的时候。我自己踩过的坑是曾经花两个晚上试图给一道“实现优先队列并比较两种建堆方式”的题写出完美答案最后发现手册里根本没这题而教材正文的图里已经把两种建堆的代价曲线画出来了。血泪经验是先花十分钟翻目录和前言确认范围比闷头写两天划算。2.3 给题号建一张自己的索引表手册的题号是跟教材绑定的但教材不同印次会有题号微调这一点后面避坑章会细说。所以不要直接在 PDF 上做批注另开一个表格维护自己的索引字段至少包含五项。字段填什么为什么需要教材题号例如 2.19与手册对齐的主键题面关键词例如“多数元素 线性时间”题号错位时靠它对齐手册页码例如 5二次查阅时的定位我的答案差异一句话写清哪里不一样复习时只看差异不重读待复核标记是 / 否决定第二轮要不要重做这张表看起来笨但它是把“读一遍”变成“能复查”的唯一办法。手册的解答完整度参差不齐作者在前言里也承认“细节一般留给读者”所以你的差异栏里出现“我多写了一步放缩”是常态出现“结论完全不同”才是需要警惕的信号。2.4 伪代码不是代码读的时候要“翻译”手册里的程序明确是伪 C 风格不是能直接编译的完整代码缺头文件、缺类型定义、缺边界检查有些函数名后面还挂着奇怪的字母。正确读法是把它当成“带语法糖的算法描述”关注三件事循环不变式是什么、每轮迭代推进了哪个游标、退出条件覆盖了哪些边界。比如第 3 章那道按位置序列打印链表元素的题函数体只有几行但信息量全在“谁每轮只前进一步、谁在命中时才前进”这个细节上。你把这两个游标的推进条件抄在纸上复杂度 O(LP) 自然就出来了不需要背结论。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 右边直接错。第三步按“多项式次数”排主体再插指数。整理后的顺序是位置项化简 / 判据12/N递减N 增大时趋零237常数3常数的平方根项与 N 无关4N线性基准5N log log N比线性多一层极慢的对数6N log N与 N log(N²) 同阶7N log(N²)等于 2N log N与上一项并列8N log²N对数被平方压过上一项9N^1.5多项式次数 1.510N²二次11N² log N二次再乘对数12N³三次132^(N/2)指数底数 2 的半步142^N增长最快这张表的价值不在结论在“化简再比较”这个动作。凡是看到对数套在括号里先问一句能不能提出来变成系数凡是有两个项的差别只在一个常数上它们就不该被排成前后关系。判据统一之后这一章剩下的题都好办。3.2 判断题证伪只需要一个反例第 2 章还有一类题是给若干命题判真假。手册在这种题上给得非常节省只标 True / False再配两三行反例例如用 T12N、T2N、f(N)N 这一组去推翻某个命题又用 T1N²、T2N、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 和 gf 在 N 为偶数时取 1、奇数时取 Ng 反过来于是 f/g 的比值在 0 和无穷之间来回振荡。这题的作用是打掉“比值必有极限”的直觉。遇到这类题我建议直接在纸上列 N1,2,3,4 四行数值把 f、g、比值三列填出来振荡肉眼可见比看文字推导快得多。3.3 把归纳证明写成四步模板第 1 章那道 log X ≤ X 的证明是全书归纳法的样板题。手册给的推导链不算长但结构很典型我把它固化成四步后面所有同类证明都套这个模板。第一步划定基础区间。先验证 0X≤1此时 log X ≤0而 X0结论显然成立。再验证 1X≤2此时 log X ≤1而 X1也成立。基础区间之所以要分成两段是因为在对数函数上小于 1 和大于 1 的行为不一样一段盖不住。第二步设定归纳假设的形式。手册的做法是按“区间加倍”归纳假设命题在 pX≤2p 上成立p 为正整数。注意这里的归纳变量不是 N而是区间的上界这是很多人卡住的地方。第三步处理翻倍区间。取 2pY≤4p则 Y/2 落在 pY/2≤2p 里正好命中归纳假设于是 log(Y/2)Y/2。第四步拼放缩链。log Y 1 log(Y/2) 1 Y/2 ≤ Y/2 Y/2 Y最后一步用的是 1≤Y/2因为 Y2。整条链每一步都只用一个已知条件没有跳步这就是“可复现”的标准。同一章还有一道斐波那契的界证明用的是 φ1φ² 这个恒等式由此推出 φ⁻¹φ⁻²1再把 F(k1)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 和 PP 里存的是位置序号要求按 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) 是每层扫描的代价。第二步展开。按主定理a1、b2、f(N)O(N)落在 f(N) 大于 N^log_b(a)N^0 的情形总量由顶层决定得 O(N)。第三步处理奇偶边界如果 N 是奇数先忽略最后一个元素再递归因为最后一个元素不可能单独构成多数。第四步处理“无多数”的情形如果递归回来没有得到候选就把被忽略的那个元素当作候选返回。这四步里第三步和第四步是手册点到的细节也是自己写的时候最容易漏的。我的做法是在纸上画一个 N5 的小例子元素为 [3,3,3,1,2]手动跑一遍“忽略最后一个、递归、回填候选”的流程跑通了再写代码。同一章还有一类题是问“递归是否可以避免”“能不能只用两份数组”。手册的答案给的是原递归策略会用到 O(log N) 份数组副本改成在原数组上就地放置可以压到两份。这类题的通用推法是把递归树画出来数一数同时存活的副本数而不是凭感觉答。4.3 哈希与堆用表算不要用眼看哈希和堆这两章的题答案往往是一串数字看是看不出来的必须列表。哈希题我一般建三列插入序列、哈希值、实际落位。以表长 10、除余法为例依次插入 12、22、32、42线性探测下的落位是这样的插入值h(k)k%10实际落位探测次数12221222323224342254这张表能直接回答两类问题一是平均探测次数把最后一列求和除以元素个数二是装填因子对性能的影响当表里元素继续增加、探测长度开始成串增长时你会在表上看到连续的非空槽位这就是“一次聚集”。手册在哈希这章给出的多是结论性说明你得靠这张表把结论还原成过程。堆的题同理。建堆的线性时间结论O(N)很多人背下来了但不会证实际推法是从第 ⌊N/2⌋ 个元素开始向前逐个下滤每个位置的下滤代价与它的高度成正比而高度为 h 的节点最多有 ⌊N/2^(h1)⌋ 个求和后收敛到 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, keylambda 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 个顶点、边权取个位数。规模必须小到能在纸上完整画完否则你会在中途放弃然后回去看答案。技巧适用章节单次耗时判断通过的标准脚本验证增长率第 1、2 章10 分钟三个 N 的排序结果一致错答清单重做全书30 分钟差异栏清零小输入手算第 3 到 9 章15 分钟手算结果与答案逐项对上这套流程唯一的成本是前期建表但建完之后这份 66 页的手册就变成了一份可查询、可验证、可复现的自测题库。我最早是把它当 PDF 从头翻到尾翻完什么也没留下从那以后我每读完一章都强制走一遍“脚本 错答清单 小输入手算”宁可慢一点也要让每一页都留下能复查的痕迹。这份手册在常见的电子书归档和课程资料盘里能搜到文件名里通常带 solutions manual下载时注意区分第二版和更早的版本版本不对题号会整片错位。希望帮到你。本文还有配套的精品资源点击获取
