简介：这份由 Mark Allen Weiss 编写的《Data Structures and Algorithm Analysis in C（第二版）Solutions Manual》面向正在学习数据结构与算法分析课程、需要对照课后习题思路的本科生和自学者。内容按教材章节组织，覆盖算法复杂度与大O分析、表栈队列、树、哈希、优先队列、排序、不相交集合、图算法、算法设计技巧、摊还分析及高级数据结构等主题，解答以伪C代码和思路说明为主，对多数练习给出参考答案，部分编程题与延伸题只提供提示，便于核对理解、查漏补缺，并保留独立思考空间。资源包仅含1个PDF文件，约233KB，轻量便于本地阅读和检索，适合按章查阅对应习题。目前已有143人学习下载，可作为课程复习、习题订正和考研或面试前梳理知识点的辅助材料，帮助读者理解常见数据结构操作、算法效率比较与图算法实现要点。

1. 一份"答案册"到底是什么：先给它一句话的定义

很多人第一次看到"数据结构与算法分析的习题解答手册"，会以为它是另一本教材，或者是一份能直接粘进作业里的代码合集。其实它更接近一本"参考答案加解题旁白"：教材把概念铺开讲，它把课后那些证明题、复杂度推导题、伪代码设计题一条条写下来，告诉你每一步是怎么想出来的。打个比方，教材是菜谱，它像厨师站在旁边，专门解释"为什么这一步要先放盐"。搞懂它的定位，你就能跨过"书看得懂、题做不对"那道坎——这也是后面几章要一层层拆开的东西。

2. 为什么"答案"本身不是重点：算法分析这一章最有代表性

整本手册里，最能体现"答案只是副产品"的，是紧跟在引言后面的算法分析部分。这一章在教材里是全书的地基：后面讲链表也好、讲图也好，判断"这个做法行不行"的尺子都是在这里立起来的。手册对这一章的处理方式，恰好暴露了它的真实用法——它给的不是结论，而是"结论是怎么被推出来的"。

举个最常见的困惑：不少人把复杂度当成一种背诵条目，记住了"快排平均 N log N""冒泡 N 方"，遇到新题照样不会估。原因在于，他们背的是结果，没拿到那把尺子。手册在这一章反复做的，就是把尺子递到你手里：先看一个操作被执行的次数随规模怎么变，再看这个变化趋势能不能被一个更简单的函数"罩住"。这一步做完，你才有资格谈优化。

2.1 大 O 说的不是"跑得快"，而是"变慢的速度"

大 O 记号最容易被读成"耗时"。它其实描述的是增长率：当输入规模 N 变大时，工作量按什么形状往上走。手册里有一道估算题把这件事摊得很开——同样是解决一个问题，某个 N 方的做法在一万条数据上要花几天，十万条要花十四年多，一百万条要花一百多个世纪；而另一个做法在一百万条上只要几秒。数据量只涨了一百倍，时间涨了几十万倍，这就是增长率的威力。

这也解释了大 O 为什么可以"狠心"扔掉常数和低阶项。2N 和 100N 在记号上都是 N，因为当 N 大到一定程度，那个系数就不再决定形状了。但请注意，这个"扔掉"是有前提的：它服务于比较趋势，不服务于预测具体毫秒数。一段跑了三遍才热起来的代码，一个常数因子为 0.001 的 N 方，在小数据上完全可能打赢一个常数因子为 50 的 N log N。手册不会替你做这个工程判断，它只负责告诉你趋势长什么样。

提示：看到 O(N) 先别急着说"这个快"，先问一句"N 大概多大"。N 只有几十的时候，复杂度几乎不构成选型理由。

2.2 排序那道教具题：为什么 N log N 和 N log(N²) 是同一档

手册开篇就有一道"把一串函数按增长速度排序"的题，里面摆着根号 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²) 当成两个不同档位排开——其实 log(N²) 就是 2·log N，差一个常数因子，两者完全同阶。

这道题真正的教学价值不在答案的顺序，而在于它逼你动一次对数运算。你会因此记住几件事：对数里的指数可以提到前面当系数；N 的 1.5 次方卡在 N log²N 和 N 平方之间；指数级的东西一旦出现，前面所有多项式都得往后站。这种"手感"没法靠背，只能靠亲手排一遍。手册把它放在第一章之后，意思很明确：先把这个手感练出来，后面所有章节的取舍才有依据。

2.3 从"伪 C"看手册的定位：逻辑对优先于工程完备

手册在前言里就把话说明白了：里面的程序是"伪 C"，不是可以直接编译运行的完整代码，细节一般留给读者自己补。这句话是理解整本书的钥匙。它意味着你在里面看到的函数，通常只保留跟算法逻辑相关的那几行，输入校验、内存分配失败、边界处理这些工程上的琐事被有意省略了。

/* 按指定小数位做四舍五入：先造出进位偏置，再统一加上去 */ double RoundUp(double value, int decPlaces) { int i; double amountToAdd = 0.5; for (i = 0; i < decPlaces; i++) amountToAdd /= 10; /* 0.5 -> 0.05 -> 0.005 ... 逐位缩小 */ return value + amountToAdd; /* 只负责"偏置"，不负责截断输出 */ }

这段代码里，value是待处理的实数，decPlaces是希望保留的小数位数，返回值是加上偏置后的数，真正的小数截断由另一个打印函数完成。手册把它拆成两步，是因为浮点数直接四舍五入会因为二进制表示的误差出现"看起来很奇怪"的结果。代码本身没考虑decPlaces为负数、value为无穷大这些情况——那不是它要教的东西。

明白这一点，你就不会拿着手册里的片段去质问"这代码跑不起来"。它跑不起来是设计如此，就像草图上不会画螺丝的螺纹。真正要拿走的是那个"先加偏置再截断"的思路。

2.4 证明题为什么占了半壁江山

翻几页就会发现，手册里大段大段的内容是归纳法、反例和极限推导，而不是代码。比如判断某个命题真假时，它给的往往不是长篇论证，而是一组具体的反例：取两个函数，一个增长快一个增长慢，代进去立刻就能看出原命题不成立。这种做法看着"偷懒"，其实是算法分析里最实用的技能——想推翻一个断言，构造反例比正面硬刚有效得多。

归纳法出现得更频繁。证明一个求和公式、证明斐波那契数列的某个界、证明某个递归式的解，套路都是先验证最小规模，再假设前 k 项成立、推到第 k+1 项。手册在这一步通常写得很简，因为它默认你已经在教材里看过完整推导。初学者读到"由归纳假设可得"就卡住，多半不是手册的问题，是教材那一页没吃透。

这也顺带说清了手册的阅读顺序：先读教材对应章节，再回来对答案。反过来做，你会觉得每一行都像跳步。

3. 十二个章节在解决什么问题：一张从"存"到"算"的地图

整本手册跟着教材走，一共十二个部分，从引言的数学复习一路排到高级数据结构。如果只按目录顺序读，很容易读成十二章互不相干的知识点。换个视角看，它其实是一条主线：先把数据"放好"，再把数据"算快"。前半程解决"东西放哪、怎么取最快"，后半程解决"多条路里走哪条、代价怎么摊平"。

3.1 前半程：先解决"东西放哪"

列表、栈、队列这一组，是最朴素的容器。链表的特点是插入删除不用搬动别人，但想找第 k 个元素得从头数；数组正好相反。栈和队列则是加了规则的容器：栈只允许在顶端进出，后进先出；队列只允许一头进一头出，先进先出。手册在这一章的解答里，有个打印指定位置元素的例子，用两个游标在两条链表上同步前进，时间复杂度是两条表长之和。这类题目练的是"指针怎么走"，不是"代码怎么写"。

树这一章往上走一层。二叉树把"一对一"变成"一对多"，查找路径从一条线变成一条分叉的路。平衡树的意义在于，不让这棵树长成一根斜棍子，否则查找退化成链表。堆则是另一种约束：它不追求全局有序，只保证"顶上那个最大或最小"。这个弱化非常划算，因为插入和取顶都只要对数时间，优先队列才有了落地的可能。

哈希这一章干脆放弃顺序，直接用函数把键映射到位置，理想情况下一次就命中。代价是冲突——两个键算到同一个格子，必须有一套兜底规则。手册在这里既讲开放地址法，也讲链地址法，两种兜底各有脾气：前者在同一片数组里另找空位，后者在每个格子上挂一条链。选哪种，取决于你更怕"装得太满"还是更怕"链拉太长"。

3.2 后半程：排序、并查集、图、设计技巧

排序这一章是全书最"接地气"的部分，也是最容易背成口诀的部分。冒泡、选择、插入这类简单排序，代码短、思路直白，代价是平方级的比较次数，适合小规模或者近乎有序的数据。快速排序靠划分把问题对半砍，平均能到 N log N，但遇到极端划分会退化；归并排序稳定、界漂亮，代价是要额外空间；堆排序原地完成，代价是常数偏大且不稳定。

稳定性这个概念，初学者常常记混。它说的不是"跑得稳不稳"，而是相等的两个元素在排序后是否保持原来的相对次序。按分数排序时，同分的同学如果还要保持录入顺序，就得用稳定排序。这条性质在实际业务里经常是硬要求，一旦踩坑，表现出来就是"每次跑出来的名单顺序都不一样"，很难查。

并查集解决的是另一类问题：一堆元素不断被合并成组，还要随时回答"这两个是不是同一组"。它的实现朴素到近乎简陋——每个元素记住自己的上级，一路往上找就能找到组代表；合并时把一棵树的根挂到另一棵的根下面。真正让它变快的是两个小动作：查找时把路径上的节点直接挂到根上，合并时把矮树挂到高树下。这两个动作加起来，摊到每次操作上的代价几乎是常数。

图算法是整本书的高潮。深度优先和广度优先是两种探路方式：一个往死里钻再回头，一个像水波一样一圈圈扩散。最短路径里，从一个源点出发算到所有点的，用的是"每次挑当前最近的"这种贪心；算任意两点之间的，则靠不断用中间点做中转来松弛。最小生成树关心的是用最低总代价把所有点连起来，一种做法从点出发不断吸纳最近的邻居，另一种从边出发按代价从小到大挑、挑之前先判断会不会成环。判断成环，正好又回到并查集。

设计技巧这一章把前面用过的招式命名：贪心、分治、动态规划、回溯。命名之后你会发现，前面那些算法并不是各自独立的奇技淫巧，而是这几种套路在不同问题上的具体形态。

3.3 容易被跳过的两章：摊还分析与高级数据结构

摊还分析这一章的名字听起来很唬人，讲的事情其实很日常。有些操作偶尔特别贵，但贵完之后很长一段时间都很便宜，于是把总代价摊到每一次操作上，单次平均下来就很低。打个比方：一张地铁月票，单看某一次乘车好像不划算，但一个月坐满之后，每次的成本被摊得很薄。摊还分析干的就是这个"摊薄"的账。

这一章的价值在于，它纠正了一种直觉偏差：不能因为某个操作最坏很慢，就否定了整个结构。判断一个结构好不好，要看一长串操作的总体代价，而不是盯着最坏那一次。

最后的高级数据结构与实现，通常讲的是前面内容的组合与工程落地：更复杂的外存结构、更精细的平衡策略、更贴近真实系统的实现取舍。这一部分对手写代码的要求最高，也最容易被初学者跳过。跳过不丢人，但如果你打算把前面的知识真正用起来，这一章值得回头补。

4. 五个最容易搞混的地方：答案手册不是"抄答案的作业本"

围绕这类手册，误解往往不是因为难，而是因为一开始的预期就偏了。下面几条是初学者最常撞上的混淆点，每条都按"混在哪、为什么混、怎么分清"说清楚。

4.1 误区一：以为每道题都有标准答案

易混点：把手册当成"课后题全解"，翻不到答案就以为书有问题。

为什么混：书名里带着"解答"，天然给人一种"全覆盖"的暗示。

怎么区分：手册在前言里就交代了边界——它收录的是大部分练习题的答案，而那些接近课程大作业的编程题、以及教材章末明确指向参考文献的题目，是有意不收的；即便是收了的题，解答的完整程度也参差不齐，细枝末节通常留给读者自己补。这个设计不是偷工减料，而是留白：大作业本来就是让你自己从零搭起来的，给了答案反而失去意义。所以翻不到某道题时，先确认它是不是落在这两类里，再决定要不要自己啃。

4.2 误区二：把伪 C 代码直接搬进工程

易混点：看到完整函数签名，就以为能编译能上线。

为什么混：手册里的代码有类型、有循环、有返回值，形式上跟真代码没差别。

怎么区分：看它有没有做那些"跟算法无关"的事。真实的工程代码要处理空指针、要检查分配是否成功、要考虑整数溢出、要给出错误码；手册里的片段通常把这些全省了，只留下表达逻辑的主干。判断方法很简单：如果一个函数里没有任何一处失败分支，它就大概率是示意性的。拿走思路，代码自己重写，这是它期望的用法。

4.3 误区三：把大 O 当成实测耗时

易混点：看到 O(N log N) 就认定它一定比 O(N²) 快。

为什么混：两者都叫"复杂度"，读起来像是同一维度的度量。

怎么区分：大 O 描述的是规模变大时的趋势，它主动丢掉了常数和低阶项。真实耗时还受常数因子、缓存命中、内存分配、编译器优化影响。小规模数据下，常数小的平方级算法打赢常数大的对数级算法是常态。正确的读法是：先用大 O 排除掉量级上明显不合适的方案，再用实测在小范围内挑。反过来用，就是拿地图当尺子量桌子。

4.4 误区四：把最坏情况和平均情况混着说

易混点：一句"哈希查找是 O(1)"就概括完了。

为什么混：教材和手册在叙述时经常省略"平均"两个字。

怎么区分：哈希表的常数级查找是平均情况下的结论，前提是哈希函数散得开、装填因子可控；一旦所有键都撞到同一个格子里，查找就退化成遍历一条链，最坏是线性的。快速排序同理，平均 N log N，最坏退化成平方。看到复杂度结论时，习惯性问一句"这是在什么前提下"，能省掉大量事后返工。

4.5 误区五：把数据结构里的"堆"当成内存里的"堆"

易混点：两个词长得一模一样，初学者常以为是同一个东西。

为什么混：中文都叫"堆"，英文也都写作 heap。

怎么区分：数据结构里的堆是一种满足"父节点不小于（或不大于）子节点"的完全二叉树，用来做优先队列，取顶只要常数时间；内存管理里的堆是程序运行时动态分配的那片区域，跟malloc和free打交道。两者除了名字撞车，没有关系。读到一个"堆"字，先看上下文是在讲取最值，还是在讲分配内存，一秒就能分辨。

5. 它和教材、题解网站、开源实现的分工：别把三种东西当成一种

同样一道课后题，你手里可能同时握着四样东西：教材、这本手册、网上零散题解、现成的开源实现。它们看着都在回答同一个问题，实际上各自负责的段落完全不同。分不清分工，最典型的后果就是拿手册去补教材该干的活，或者拿开源库去替代自己该动的那部分脑子。

5.1 教材负责"为什么这样设计"，手册负责"这道题怎么收尾"

教材的叙事是连续的：先抛出问题，再讨论几种可能的解法，比较完复杂度，最后给出结论。它的重点在论证链条，很多推导会写成"不难看出""留作练习"。手册正好接在这句话后面——它把那句"留作练习"展开成具体步骤。

举个具体的：教材讲哈希冲突时，会解释为什么装填因子不能太高，会给出几种探测策略的直觉。手册则在对应练习里让你实际算一算，在给定的一组键和给定的表长下，线性探测要比较多少次、链地址法要比较多少次。前者给你判断力，后者给你手感。缺了教材，手册像天书；缺了手册，教材读完仍然不知道自己对没对。

这也解释了为什么手册的解答常常写得那么"简"。它默认你已经走过教材那一遍，所以跳过铺垫，直接从关键那一步开始。你读着跳，多半是前面那一遍没走完。

5.2 手册、在线题解、开源库三者的对照

在线题解的特点是针对性强：一道题一个解法，代码完整可跑，还带讨论。它的短板是碎片化——你拿到了这一题的答案，但拿不到这一类问题的框架。手册正好相反，覆盖面广、按知识脉络组织，但每道题的细节写得克制。

开源库则是另一个层级：它已经在工程里被磨过，考虑了并发、内存、异常，但恰恰因为要考虑的东西太多，算法本身被埋在一层层封装底下，读起来比手册费劲得多。想搞清楚一个结构的原理，读开源实现是最绕的路；想验证自己的实现够不够健壮，读开源实现是最直接的路。

看清这张表，你就明白为什么"手册里的代码跑不起来"根本不是问题。它的产出物是思路和判断，代码只是承载思路的载体。真正需要可运行代码的时候，去开源实现里找，或者干脆自己写。

6. 什么时候该翻它、什么时候别翻：一个具体的使用场景

先说该翻的时候。第一种情况是你刚读完教材某一章，题也做了，但不确定自己的推导方向对不对——这时候对照手册是最省时间的，它不会替你写作业，但会告诉你"这一步该往哪拐"。第二种情况是卡在某道题上超过半小时，思路完全没有起点，这时候看手册的第一行解答，往往就够你继续往下走了。第三种是复习阶段，你想快速过一遍某章的知识密度，手册的解答顺序本身就是一条浓缩的复习路径。

再说别翻的时候。第一，题还没做就翻——这是最常见也最亏的用法，你以为自己看懂了，其实只是看懂了别人的推理链，合上书照样空白。第二，想找可以直接交上去的完整程序——手册明确说了里面的程序是伪 C，本来就冲着"表达逻辑"去的，交不了作业也上不了线。第三，把它当参考手册查语法或者查库函数——它不干这个。

具体到一个场景：假设你在啃图那一章，四种经典算法看来看去都糊成一团。合理的顺序是，先在教材里把"从源点出发逐个确定最近点"这个贪心思路捋顺，然后自己动手在纸上跑一遍小图，把每一步的距离表写出来；跑完之后再翻手册对应的练习，看它给的复杂度分析和边界讨论跟你纸上跑出来的是不是一致。不一致的地方，就是你真正没搞懂的地方。

我自己的习惯是，每道题先在纸上写一个"我认为的答案"，哪怕只写三行；翻手册时只对照那三行，对上了就过，对不上就停下来找差在哪。这个习惯是被逼出来的——早年我图省事，直接顺着解答往下读，读的时候点头如捣蒜，一周后合上书，连第一章那道排序题都排不利索，血泪经验就是那时候攒下的。从那以后我每次翻开这类手册，都强制先留下自己的版本再对照，哪怕版本很粗糙。希望帮到你。

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