简介：这份PDF是Mark Allen Weiss《Data Structures and Algorithm Analysis in C》第二版的配套习题解答手册，面向正在学习数据结构与算法分析课程、需要对照课后练习查漏补缺的高校学生与自学者。内容覆盖算法复杂度分析、表栈队列、树、哈希、优先队列（堆）、排序、不相交集合、图算法、算法设计技巧、摊还分析及高级数据结构等章节，解答以伪C代码和思路说明为主，部分题目仅给出要点或留给读者补充。资源包共1个PDF文件，大小约233KB，轻量便于在电脑或平板上查阅；已有143人学习。它可用于核对习题结论、理解大O分析与经典结构实现思路，并借助章节编排定位薄弱环节，适合作为教材精读和考前复习的辅助材料。

1. 习题解答手册：为什么答案比正文更接近算法分析的真相

很多人把这份 C 语言版数据结构与算法分析教材的第二版习题解答手册当成对答案的工具，这其实低估了它。教材正文给出的是干净结论，解答手册给出的是结论成立的条件：时间复杂度怎么推、空间复杂度怎么估、大 O 表示法在什么边界上会骗人。比如增长率排序里，N log N 和 N log(N²) 被放在同一档，N^1.5 却排在 N log² N 后面；这些顺序不是背出来的，而是由极限、归纳和反例一步步压出来的。读这份手册的乐趣在于看见“数据结构为什么这样组织、算法分析为什么能 work”的中间层，而不是只拿到一个最终答案。

2. 算法分析：增长率排序为什么不能只看大O符号

2.1 从 2/N、37、√N 到 2^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。这个顺序背后不是“谁看起来复杂谁就大”，而是每一对函数做极限比较的结果。2/N 随 N 增大趋于 0，所以它排在最前；37 是常数，增长率是 0；√N 小于 N；N log log N 小于 N log N，因为 log log N 增长极慢；N log(N²) 化简后是 2N log N，和 N log N 只差常数因子，所以手册明确说两者同速。

真正容易翻车的是 N log² N 与 N^1.5 的比较。两边同时除以 N，变成比较 log² N 与 √N。对数多项式增长慢于任何正幂次，所以 N^1.5 在 N 足够大时反超。这个“足够大”是渐近分析的关键限定词：在小规模输入上，37 可能比 2/N 大得多，N² 算法也可能比 N log N 算法跑得快。大 O 描述的是上界，不是紧界；Θ 才表示同阶。血泪经验是，排序算法在小数组上切回插入排序，不是因为插入排序的渐近界更好，而是因为它的常数和分支预测更友好。

手册里还特意把 2^(N/2) 和 2^N 分开。两者都是指数级，但底数不同，差距在 N 增大时会被迅速拉开。读这种排序题时，我一般会先把每个函数化简到最简形式，再两两做比值极限，最后才看手册的最终顺序。直接背顺序没有意义，因为换一组函数就会露馅。

2.2 反例与归纳证明：解答手册如何拆掉“想当然”

手册第 2 章有一组判断真假的题，专门打“想当然”的脸。比如“若 T1(N)=O(f(N)) 且 T2(N)=O(f(N))，则 T1(N)+T2(N)=O(f(N))”是真的，因为两个上界相加还是上界。但“若 T1(N)=O(f(N)) 且 T2(N)=O(f(N))，则 T1(N)/T2(N)=O(1)”是假的，反例取 T1(N)=2N、T2(N)=N、f(N)=N，比值是 2，确实有界；可如果取 T1(N)=N²、T2(N)=N、f(N)=N²，比值是 N，没有常数上界。手册用这种最小反例说明：大 O 只约束单个函数的增长，不约束两个函数之间的商。

更微妙的是乘法题。“若 T1(N)=O(f(N)) 且 T2(N)=O(f(N))，则 T1(N)×T2(N)=O(f(N))”同样不成立，反例还是 N² 和 N，乘积 N³ 已经超过 N² 的上界。这里的关键是 O 的传递方向：T1 和 T2 各自被 f 压住，不代表它们的乘积还被同一个 f 压住。手册的答案没有停在“假”字上，而是把反例写全，让读者看到假在哪里。

还有一道题用振荡函数说明商没有渐近上界：f(N) 在 N 为偶数时取 1、奇数时取 N；g(N) 在 N 为奇数时取 1、偶数时取 N。f/g 在 0 和无穷之间来回跳，既不是 O(1)，也没有稳定的增长阶。这个反例的价值在于提醒：渐近分析默认函数有单调趋势，遇到振荡、周期性、分段定义时，先检查定义域和极限是否存在。手册里这类题不多，但每一道都在训练“先找边界，再谈结论”的习惯。

归纳证明也是同一套思路。手册第 1 章证明 log X < X 时，先验证 0<X≤1 和 1<X≤2 的基例，再假设 p<X≤2p 成立，推到 2p<Y≤4p。每一步不等式都写出来，不跳步。斐波那契那一组题则用 φ+1=φ² 把递推式压成闭式。读这些证明时，重点不是记住不等式，而是看作者怎样选基例、怎样设归纳假设、怎样把目标规模折半。自己先推一遍再对照，比直接看答案有效得多。

2.3 幂运算与递归式：从 O(log N) 乘法次数看“降规模”的代价

手册第 2 章后面有一组幂运算题，要求计算 X^62，并统计乘法次数。最直接的做法是连乘 61 次，时间复杂度 O(N)。但把指数拆成二进制后，可以用平方链把规模压到 O(log N)。下面这段迭代快速幂把“降规模”的代价摊开：每次循环只做一次平方，遇到二进制位为 1 时再做一次乘法。

/* 迭代快速幂：把指数拆成二进制位，避免递归栈和重复子问题 */ long long fast_pow(long long base, unsigned int exp) { long long result = 1; while (exp > 0) { if (exp & 1u) { /* 当前最低位为 1，累乘进结果 */ result *= base; } base *= base; /* 平方，为下一位准备 */ exp >>= 1; /* 指数右移一位 */ } return result; }

这段代码的参数很直白：base 是底数，exp 是无符号指数，result 累积当前结果。循环每轮把 exp 右移一位，所以最多执行 ⌊log₂ exp⌋+1 次；平方操作每轮一次，置位乘法只在二进制位为 1 时发生。若把 result 初始化为 1 的那次赋值不算乘法，总乘法次数约为 ⌊log₂ N⌋ + popcount(N) - 1，和手册第 2 章给出的计数公式对得上。空间复杂度是 O(1)，没有递归栈。

对比递归写法 X^N = X^(N/2) × X^(N/2)，如果真写成两次递归调用，复杂度会退化成 O(N)，因为同一个子问题被算了两遍。正确做法是把 X^(N/2) 存进临时变量再平方。这个细节是很多人的翻车点：看起来是分治，实际上没有消除重复子问题。手册用幂运算这个小题把“分治不等于自动降复杂度”讲得很清楚，也顺带引出了递归式求解和摊还分析的入口。

3. 线性结构：PrintLots 的 O(L+P) 为什么不是 O(L×P)

3.1 双指针同步推进的时序

手册第 3 章有一道 PrintLots 题：给定链表 L 和位置链表 P，按 P 中指定的位置打印 L 中对应元素。朴素写法是对 P 中每个位置 p，从头遍历 L 到第 p 个节点，复杂度 O(L×P)。手册给出的答案用两个指针同步推进，把复杂度压到 O(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("%? ", Lpos->Element); /* 命中位置，打印 L 当前元素 */ Ppos = Next(Ppos, P); /* P 推进到下一个待打印位置 */ } Lpos = Next(Lpos, L); /* L 每轮都推进 */ } }

参数和变量需要说清楚：L 是被扫描的链表，P 是位置链表，Counter 记录 L 当前节点的位置编号，从 1 开始；Lpos 和 Ppos 分别是两个链表的游标。循环每轮先比较 Ppos 的位置和 Counter，命中就打印并推进 Ppos；无论是否命中，Lpos 都前进一格，Counter 自增。这样 L 只走一遍，P 也只走一遍，总代价 O(L+P)。

这个复杂度成立有两个前提：P 中的位置按升序排列，且 Next 操作是 O(1)。如果 P 乱序，比如先要第 5 个再要第 2 个，Lpos 已经走过第 2 个节点，单指针无法回头，算法会漏打。手册没有把这两个前提藏起来，读答案时要自己补上。链表的位置抽象也让这件事变复杂：Position 可能是节点指针，也可能是数组下标；如果是数组，随机访问第 p 个元素是 O(1)，根本不需要双指针。手册用伪 C 写答案，保留了抽象性，也留下了“具体实现取决于 Position 语义”的讨论空间。

3.2 链表游标与位置语义：抽象层级的取舍

手册第 3 章反复提到“抽象性用了多少”的问题。链表、栈、队列都是抽象数据类型，答案里可以用数组实现，也可以用链式实现，复杂度一样但常数和边界不同。以链表为例，Position 如果是指针，Next 是 O(1)，FindKth 是 O(N)；如果 Position 是数组下标，FindKth 是 O(1)，但插入删除要搬元素。PrintLots 之所以能用双指针，是因为它只顺序扫描，不需要随机访问；一旦题目改成“按 P 中位置随机打印”，链表就得反复从头找，复杂度立刻上去。

栈和队列的抽象更隐蔽。栈只暴露 push 和 pop，用数组实现时，push 可能触发扩容，单次 O(N)，但均摊 O(1)；用链式实现时，每次 push 都要分配节点，单次 O(1)，但分配器有成本。队列用循环数组时，front 和 rear 的语义必须约定清楚：rear 指向下一个空位还是当前尾元素，直接决定判空判满条件。手册里的答案通常不会把每种实现都写全，而是选一种最贴近题意的，剩下的留给读者。这种“不完整”不是偷懒，而是训练读者自己补边界。

我一般会这么理解：抽象数据类型定义“能做什么”，数据结构实现决定“做得多快、边界多容易错”。PrintLots 的双指针解法之所以优雅，是因为它利用了链表顺序访问的天然顺序，而不是硬把链表当数组用。读手册第 3 章时，先把每个操作的复杂度写在纸上，再看答案用了哪种实现，能少踩很多下标和空指针的坑。

3.3 栈与队列的隐藏成本：数组实现 vs 链式实现

把栈和队列的实现放在一起对比，隐藏成本会更清楚。下面这张表只列关键差异，不追求穷尽：

数组栈的扩容成本可以用均摊分析摊平：容量从 1 开始翻倍，1+2+4+…+N < 2N，所以 N 次 push 的总搬迁代价是 O(N)，均摊到每次是 O(1)。但单次扩容仍然是 O(N)，对延迟敏感的场合要提前 reserve。循环数组队列的判满条件是最容易翻车的地方：如果只维护 front 和 rear，不维护 size，通常要牺牲一个槽，用 (rear+1)%cap==front 判满，front==rear 判空；一旦 rear 的语义改成“当前尾元素”，条件全变。

链式队列没有扩容问题，但每次 enqueue 都要分配节点，dequeue 要释放节点，分配器的开销和内存碎片会吃掉一部分性能优势。手册第 3 章的答案更关注抽象操作的正确性，工程实现里的这些成本要自己补。一个实用的习惯是：先确定队列的最大容量，能预估就用循环数组；不能预估且对延迟不敏感，再用链式队列。不要因为“链表插入 O(1)”就无脑选链式，缓存局部性在真实机器上经常是隐形的胜负手。

4. 树与哈希：平衡、堆序和散列冲突背后的不变量

4.1 平衡二叉搜索树：旋转不是目的，高度差才是约束

平衡二叉搜索树的核心不变量有两个：左子树所有键小于根，右子树所有键大于根；每个节点左右子树高度差不超过 1。插入和删除可能破坏第二个不变量，于是从修改点向上回溯，找到第一个失衡节点，按 LL、RR、LR、RL 四种形态做旋转。旋转本身是 O(1)，回溯路径长度是 O(log N)，所以单次插入删除是 O(log N)。旋转不是目的，它只是把高度差压回去的手段；真正要维护的是“整棵树高度保持在 O(log N)”。

下面这个节点结构把高度记账显式写出来，空树高度约定为 -1，叶子为 0：

typedef struct AvlNode { int Element; struct AvlNode *Left; struct AvlNode *Right; int Height; /* 空树高度约定为 -1，叶子为 0 */ } *AvlTree;

参数说明：Element 是键值，Left/Right 是左右孩子，Height 是当前节点高度。旋转后要先更新低位节点的高度，再更新高位节点；顺序反了，高位节点会拿到旧高度，后续平衡判断全错。常见翻车还有空指针高度：计算高度前先判空，空返回 -1，不要返回 0 又混用叶子高度。删除比插入麻烦，因为删掉一个节点可能让整条回溯路径上的节点都失衡，最坏要一路旋转到根。

红黑树用颜色约束代替严格高度差，换取更少的旋转次数；伸展树不存高度，靠访问局部性把摊还代价压到 O(log N)。这些结构在手册第 4 章和第 12 章都有对应题目，答案通常只给关键步骤，旋转的指针改法要自己画图。我一般会先画三节点的小树，把四种失衡形态各转一遍，再写代码；直接在纸上推指针，比调试器里看地址清楚得多。

4.2 哈希表：负载因子、探测序列与再散列阈值

哈希表的核心问题是把大键空间映射到小桶数组，冲突不可避免。分离链接法给每个桶挂一条链表，负载因子 λ=N/M 表示平均链长，查找代价 O(1+λ)。开放定址法把冲突元素放进表内其他空槽，线性探测容易形成一次聚集，平方探测能打散但可能探测不到全表，双散列用第二个哈希函数决定步长，要求步长与表大小互素。无论哪种方法，删除都不能简单置空：开放定址法里置空会截断后续元素的探测序列，必须用墓碑标记，查找遇到墓碑继续走，插入可以复用墓碑。

字符串哈希是另一个容易踩坑的地方。直接把字符 ASCII 码累加，冲突率高得离谱；用多项式滚动哈希，乘数取一个小素数，分布会好很多。下面这段代码用 31 作为乘数，利用无符号整数溢出自动模 2³²，最后对桶数取模：

/* 经典多项式滚动哈希：h = h * 31 + c，31 是经验选的小素数 */ unsigned int string_hash(const char *s, unsigned int table_size) { unsigned int h = 0; while (*s != '\0') { h = h * 31u + (unsigned char)*s; s++; } return h % table_size; /* table_size 取素数，减少聚集 */ }

参数：s 是待哈希字符串，table_size 是桶数。循环逐字符更新 h，时间复杂度 O(len)，空间 O(1)。31 不是唯一选择，但它小、是奇数、乘法可以移位优化，所以常见。table_size 取素数能让取模分布更均匀；如果表大小是 2 的幂，可以用位掩码代替取模，但要求哈希函数低位足够随机。安全场景不能只用固定乘数，攻击者可以构造大量同余字符串制造冲突，需要加随机种子。

再散列是哈希表保持性能的关键。负载因子超过阈值（分离链接常用 1，开放定址常用 0.5 到 0.75）时，把桶数扩到约两倍的下一个素数，重新插入所有元素。单次再散列 O(N)，但摊还到每次插入仍是 O(1)。手册第 5 章的答案会讨论不同冲突解决方法的期望代价，读的时候注意区分“平均情况”和“最坏情况”：哈希表的最坏情况可以退化到 O(N)，这不是实现错误，而是哈希冲突的固有风险。

4.3 优先队列：二叉堆的数组下标映射与 buildHeap 线性时间

二叉堆是一棵完全二叉树，用数组存储不需要指针。最小堆满足父节点不大于子节点，堆顶就是最小值。0 基数组的下标映射是：父节点 (i-1)/2，左孩子 2i+1，右孩子 2i+2；1 基数组则是父 i/2，左 2i，右 2i+1。插入时把新元素放末尾再上滤，删除堆顶时把末尾元素移到根再下滤，两者都是 O(log N)。下面这段是 0 基最小堆的下滤：

/* 0 基最小堆的下滤：把 hole 位置的元素下沉到合适位置 */ void percolate_down(int heap[], int n, int hole) { int child; int tmp = heap[hole]; for (; hole * 2 + 1 < n; hole = child) { child = hole * 2 + 1; /* 左孩子 */ if (child + 1 < n && heap[child + 1] < heap[child]) { child++; /* 选较小的孩子 */ } if (heap[child] < tmp) { heap[hole] = heap[child]; /* 孩子上移 */ } else { break; } } heap[hole] = tmp; /* 放到最终空位 */ }

参数：heap 是堆数组，n 是元素个数，hole 是起始空位。循环条件是左孩子存在；先选左右孩子中较小的一个，再和 tmp 比较，小就上移，否则停止。最后把 tmp 放回最终空位。buildHeap 从最后一个非叶节点 n/2-1 开始，倒序对每个节点下滤。总代价不是 O(N log N)，而是 O(N)：高度为 h 的节点最多有 N/2^(h+1) 个，每个下滤代价 O(h)，求和 ∑ h/2^h 收敛到常数。

常见翻车点有三个：0 基和 1 基混用导致下标差一；buildHeap 从最后一个元素开始而不是最后一个非叶节点；比较符号写反，最小堆变成最大堆。左式堆和斜堆用合并操作代替上滤下滤，合并代价 O(log N) 或摊还 O(log N)，适合需要频繁合并的优先队列。二项队列用一组堆序树支持合并和插入，最坏 O(log N)，插入摊还 O(1)。手册第 6 章和第 12 章把这些结构排在一起，读的时候先抓住“堆序”这个不变量，再看每种结构用什么手段恢复它。

5. 避坑与排查：习题解答里最容易翻车的五个细节

5.1 复杂度推导类踩坑：上界、紧界与定义域

现象：看到 O(N log N) 就认为一定比 O(N²) 快，忽略小 N 和常数因子。原因：大 O 只描述上界，且渐近性质在 N 趋于无穷时才成立；Θ 才是紧界。解决：先明确问题规模范围，保留低阶项和常数，小 N 用实测或插入排序兜底；证明同阶时用极限定义，不要只看符号。手册第 2 章的增长率排序和真假判断题，练的就是这个边界感。

现象：把 N log N 和 N log(N²) 当成不同增长率。原因：log(N²)=2logN，只差常数因子，渐近上同阶。解决：比较前先化简，对数幂、底数变化都只影响常数；手册明确说两者同速，不要被括号里的平方骗了。

5.2 实现细节类踩坑：下标、哨兵与边界

现象：二分查找写成 mid=(low+high)/2，在 low=1、high=2 时 mid=1，递归调用不前进，死循环。原因：下取整让 mid 可能等于 low，区间更新又写成 low=mid 而不是 mid+1。解决：mid=low+(high-low)/2，缩小范围时用 mid+1 或 mid-1，循环不变量写清楚。手册第 2 章专门有一道题点这个，答案很短，但坑很真实。

现象：循环队列判满用 front==rear，结果队空队满不分。原因：front 和 rear 的语义没有约定，循环数组的“满”和“空”在模运算下可能同余。解决：维护 size 计数，或者牺牲一个槽，判满 (rear+1)%cap==front，判空 front==rear；入队出队后更新顺序保持一致。手册第 3 章的抽象实现里这种边界反复出现，读答案时别只看主循环。

5.3 图与并查集类踩坑：前提条件被忽略

现象：非负权单源最短路算法遇到负权边，结果错得离谱。原因：贪心前提是“已确定的最短距离不会再被更短路径更新”，负权边破坏了这个单调性。解决：先检查边权范围，负权图改用可处理负边的松弛算法，或者先做势能变换；读手册第 9 章的答案时，先看它声明了什么前提。

现象：开放定址哈希表删除元素时直接置空，后续查找断链。原因：置空截断了探测序列，后面的元素明明存在却找不到。解决：用墓碑标记删除，查找遇到墓碑继续探测，插入可以复用墓碑；负载因子计算要把墓碑算进去，墓碑过多时触发再散列。这个坑在手册第 5 章的冲突解决题里埋得很深，自己写一遍删除操作就会记住。

6. 设计取舍：从答案手册反推教材作者省略了什么

这份解答手册在序言里说得很清楚：省略了可能的编程作业，以及章节末尾引用所指的题目；答案的完整度不一，细节留给读者；程序是伪 C，不是完全正确的代码。这些“不完整”不是缺陷，而是教学取舍。编程作业要自己设计测试、处理输入输出、调边界，答案给不了；引用题指向外部文献，答案给了反而截断探索；伪 C 省掉头文件和错误处理，把注意力压在数据结构和算法本身。读手册时如果拿它当“标准代码库”，一定会踩坑；拿它当“推导过程记录”，价值才出来。

我后来养成了一个习惯：每看一道答案前，先自己写三行——前提是什么、复杂度紧不紧、反例可能在哪。比如 PrintLots 的前提是 P 升序且链表只能顺序访问；二叉堆 buildHeap 的紧界是 O(N) 而不是 O(N log N)；哈希删除的反例是探测序列被截断。三行写完再对照手册，如果答案和我的前提冲突，优先检查前提，而不是怀疑答案。这个习惯比背结论有用，因为它逼着我把“为什么能 work”说清楚。

这份 PDF 按章分节，第 2 章的增长率排序和第 8 章的并查集摊还分析最适合先推一遍，第 3 章的 PrintLots 适合手写代码验证边界。从那以后我每次读这类解答手册，都强制自己先关掉答案把例题推一遍，再打开对照；错的地方才是真正学到的地方。希望帮到你。

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