简介这份PDF是Mark Allen Weiss《数据结构与算法分析C语言描述》第二版的配套习题解答手册面向正在学习数据结构、算法分析课程的高校学生及需要查漏补缺的自学者用于核对课后练习思路、理解书中核心概念。文件仅1个PDF约233KB正文以伪C代码和分章解答为主覆盖算法复杂度与大O分析、表栈队列、树与平衡树、哈希表、优先队列堆、排序、不相交集合ADT、图算法、算法设计技巧、摊还分析及高级数据结构等章节。已有142人学习下载。手册对多数习题给出解答但省略部分编程作业与需参考延伸阅读的题目细节常留给读者补充适合配合教材逐章复盘、对照检查理解程度并借此深化对常见数据结构实现与算法效率权衡的掌握。1. 答案册不是用来抄的先把「数据结构与算法分析」这份手册的定位摆正很多人啃《数据结构与算法分析C 语言描述第 2 版》时卡在习题上就停了归纳证明写不下去、增长率排不明白、树旋转转完不知道对不对于是去翻这份配套的习题解答手册。它覆盖原书 12 章里的大部分练习从算法分析的数学证明到表、栈、队列、树、哈希、堆、排序、不相交集合、图算法、算法设计技巧、摊还分析一直写到高级数据结构。但定位必须先说清答案是伪 C不是能直接编译的工程代码证明常常留白只给关键一步。正确的用法是把它当一份带推导过程的对照答案而不是标准答案库。适合三类人跟教材自学的、带课要讲题的、面试前想把复杂度分析补扎实的。2. 手册的组织方式12 章页码分布与「伪 C」代码的读法拿到一份 60 多页的答案册最忌讳从头翻到尾。先花十分钟把结构摸清后面每一道题该花多少时间就有数了。2.1 目录里的页码分布决定你的时间分配把手册开头的目录抄成一张表跨度一栏自己算这是最省力的优先级判断章主题起始页页数跨度1引言132算法分析433表、栈与队列774树14115哈希2546优先队列堆2977排序3668不相交集合 ADT4239图算法45910算法设计技巧54911摊还分析63312高级数据结构与实现66—树、图算法、算法设计技巧这三章占了近一半篇幅这是全书的重心也是面试和课程设计里最常被追问的部分。反过来第 1、2 章各只有 3 页很多人直接跳过但这 3 页里的增长率排序、级数求和、归纳法证明是后面所有复杂度推导的地基跳过的人到了摊还分析那一章会明显吃力。还要注意页数和难度不成正比。第 12 章只有三页出头伸展树、跳表这类结构在原书里是硬骨头手册写得极简这部分必须回原书补答案册只能帮你确认最终结论。2.2 伪 C 的三个具体表现标识符噪声、缺失原语、大小写不一致手册里的代码不是干净的 C直接抄进编辑器会撞一堆问题提前知道这三类特征能省很多时间。第一类是标识符噪声。正文里大量出现SeparateO、ProcessFileO、XO、NO、PfOO(NO)、TO1(NO)这种带尾巴的写法那个O是原文斜体括号在排版转换时残留的产物。ProcessFileO( SomeFile )实际就是ProcessFile( SomeFile )NO log NO就是N log N。读的时候在脑子里统一还原别去搜「ProcessFileO 是什么函数」搜不到。第二类是缺失原语。第 1 章那道浮点输出题对应习题 1.3给了RoundUp、PrintFractionPart、PrintReal三个函数但里面调用的IntPart、DecPart、PrintDigit、PrintOut一个都没实现因为这些在原书正文里定义过。想跑起来必须自己补齐补齐后的版本如下#include stdio.h /* 手册原样先加半个末位再截断实现四舍五入 */ static double RoundUp(double N, int DecPlaces) { double AmountToAdd 0.5; for (int i 0; i DecPlaces; i) AmountToAdd / 10.0; /* 0.5 - 0.05 - 0.005 ... */ return N AmountToAdd; } /* 手册未给按原书正文语义补齐 */ static long IntPart(double x) { return (long)x; } static double DecPart(double x) { return x - (double)(long)x; } static void PrintDigit(int d) { putchar(0 d); } static void PrintOut(long n) { printf(%ld, n); } static void PrintFractionPart(double FractionPart, int DecPlaces) { for (int i 0; i DecPlaces; i) { FractionPart * 10.0; PrintDigit((int)IntPart(FractionPart)); FractionPart DecPart(FractionPart); /* 剥掉已输出的整数位 */ } } void PrintReal(double N, int DecPlaces) { if (N 0) { putchar(-); N -N; } /* 先取绝对值避免 DecPart 出负 */ N RoundUp(N, DecPlaces); PrintOut(IntPart(N)); if (DecPlaces 0) putchar(.); PrintFractionPart(DecPart(N), DecPlaces); }RoundUp的参数DecPlaces是保留的小数位数循环每多一次就把补偿量缩小十倍PrintFractionPart里必须每轮剥掉整数位否则同一个数字会被重复输出。这段代码的价值不在跑通而在于它暴露了浮点输出的核心问题直接打印二进制浮点数会出现0.30000000000000004这类结果所以工程上永远是「先定小数位再舍入最后逐位输出」。第三类是大小写和命名不一致Adigit和ADigit在同一段里混用N、M作为常量到处出现。抄代码时统一成自己的命名规范别保留原样否则后面调试时你自己都分不清哪个是笔误哪个是原意。2.3 三步把 PDF 变成可检索的题号索引手册是 PDF直接翻页查题号效率极低。我一般先转文本再建索引整个过程三分钟。第一步转成保留排版的纯文本#!/usr/bin/env bash set -euo pipefail SRCsolutions-manual.pdf pdftotext -layout $SRC manual.txt # -layout 保留缩进和公式排布 # 按 Chapter N: 切成 12 个文件方便单章 grep awk /^Chapter [0-9]:/{ n $2; sub(:, , n); f sprintf(ch%02d.txt, n) } { print f } manual.txt-layout这个参数不能省去掉之后公式和缩进会糊成一团级数求和那几道题的上下标全丢。切分用awk匹配章头$2拿到章号sprintf补零保证文件名排序正确。第二步抽题号建 JSON 索引import re, json, pathlib # 题号形如 2.15行首允许空白后面必须跟空白或正文 pat re.compile(r^\s*(\d{1,2})\.(\d{1,2})\s) index {} for p in sorted(pathlib.Path(.).glob(ch*.txt)): chap int(p.stem[2:]) # ch07.txt - 7 for lineno, line in enumerate(p.read_text(encodingutf-8, errorsignore).splitlines(), 1): m pat.match(line) if m and int(m.group(1)) chap: # 二次过滤章号必须与文件一致 key f{m.group(1)}.{m.group(2)} index.setdefault(key, []).append([p.name, lineno]) print(json.dumps(index, ensure_asciiFalse, indent1))关键的过滤条件是int(m.group(1)) chap。只靠正则会把正文里的「2.5 倍」「3.2 秒」一起抓进来加上章号校验能滤掉九成误报。跑完你就得到一份「题号 → 文件名 行号」的映射配合grep -n -A 30 2\.15 ch02.txt直接跳到解答比在 PDF 阅读器里翻快得多。3. 算法分析章的复现增长率序列、幂运算与耗时反推第 2 章只有三页但信息密度是全手册最高的。这几道题不适合「看完就过」适合全部写成代码跑一遍因为后面每一章的复杂度结论都要用到这里的判断力。3.1 增长率排序十四项里有两个容易排错的习题 2.1 要求把一组函数按增长速度排序给出的序列是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第一个坑是N log N和N log(N²)。很多人条件反射把它们排成相邻但不同阶的两项实际上log(N²) 2 log N两者只差常数因子 2属于同一阶。手册在这一题的答案里专门点了一句「grow at the same rate」就是提醒这个。第二个坑是N log log N的位置。它比N大比N log N小但它增长得极慢在N小于百万级时两者数值上几乎看不出来靠打表很容易排错。我习惯用一段脚本做双重验证既算数值排序也算两两比值看是否趋于常数。import math def build(n): lg math.log2(n) return { 2/N: 2.0 / n, 37: 37.0, sqrt(N): math.sqrt(n), N: float(n), N loglogN: n * math.log2(lg), N logN: n * lg, N log(N^2): n * math.log2(n * n), # 等于 2*n*log2(n) N log^2N: n * lg * lg, N^1.5: n ** 1.5, N^2: float(n) ** 2, N^2 logN: (n ** 2) * lg, N^3: float(n) ** 3, 2^(N/2): 2.0 ** (n / 2), 2^N: 2.0 ** n, } n 1 20 vals build(n) for name, v in sorted(vals.items(), keylambda kv: kv[1]): print(f{name:12} {v:.3e})参数n取2^20是刻意的再小的话N log log N和N差不出量级再大的话2^N直接溢出成inf。要验证同阶关系单独算比值更直观n 1 16 a n * math.log2(n) b n * math.log2(n * n) print(b / a) # 恒为 2.0与 n 无关 - 同阶比值恒定就说明同阶比值随 n 单调增就说明后者更高阶。这个判断方法比背表可靠得多遇到陌生函数组合也能自己推。3.2 幂运算的二进制拆分把公式和实测乘法次数对上习题 2.15 到 2.17 连着三道都在讲快速幂。2.15 要求算X^62给出的路径是X², X⁴, X⁸, X^10, X^20, X^40, X^60, X^62一共 8 次乘法。2.17 更进一步给出通式N 1时乘法次数等于⌊log₂N⌋ b(N) - 1其中b(N)是 N 的二进制表示里 1 的个数。这个公式值得亲手验一遍因为它是后续所有「位运算优化」类讨论的原型。def pow_mults_formula(n: int) - int: 按手册 2.17 的口径底数平方 ⌊log2 N⌋ 次乘进结果 b(N)-1 次 if n 1: return 0 return (n.bit_length() - 1) bin(n).count(1) - 1 def pow_mults_actual(x: float, n: int): 实际跑一遍快速幂逐次统计乘法 if n 0: return 1.0, 0 result None # 第一次赋值不算乘法 base x mults 0 while n 0: if n 1: if result is None: result base # 直接赋值不计入乘法 else: result * base mults 1 n 1 if n 0: base * base # 底数平方每轮一次 mults 1 return result, mults for n in [2, 15, 62, 100, 1024]: _, cnt pow_mults_actual(1.0000001, n) print(n, cnt, pow_mults_formula(n), cnt pow_mults_formula(n))统计口径是这道题最容易翻车的地方result初始为None而不是1.0就是为了让第一次赋值不计入乘法否则结果会和公式差 1。底数平方那一行放在移位之后、且加了if n 0判断是为了避免最后一次无用的平方。跑完你会发现所有 n 都对得上这时候公式才真正变成你自己的东西。3.3 六段嵌套循环为什么「循环层数相乘」会高估一阶习题 2.6 给了六段程序让人判复杂度前五段都是老老实实的O(N)到O(N^5)第六段是反例。它有三层循环外层两层各跑 N 次最内层的循环条件是k j而j的上界是i²。如果粗暴地按「三层循环 → N³ 再乘内层 O(N²)」去算会得到O(N^5)。但if语句真正为真的次数只有O(N²)——因为对每个ij只从 1 走到i²累计是O(N³)次判断而只有满足条件时才进内层循环进内层的总次数是O(N²)每次内层O(N²)最终O(N^4)。手册在这里写了一句很关键的话multiplying loop sizes can occasionally give an overestimate。工程上的做法不是靠眼睛看而是打计数器统计真实执行次数再反推指数def count_inner(n: int) - int: 模拟 2.6(VI)统计最内层语句真实执行次数 hits 0 for i in range(1, n 1): for j in range(1, i * i 1): if j % i 0: # 代表那个只对 i 次为真的条件 for _ in range(j * j): hits 1 return hits prev None for n in [8, 12, 16, 20]: c count_inner(n) if prev: # log(次数比) / log(规模比) 即为拟合指数 import math print(n, c, round(math.log(c / prev) / math.log(n / (n - 4)), 2)) prev c拟合指数会稳定在 4 附近而不是 5。这套「打点 → 比值 → 取对数」的方法后面做真实系统性能剖析时一样能用两点耗时加规模比就能估出大致阶数。3.4 耗时数据反推复杂度一个能直接用在性能剖析上的技巧习题 2.8 给了一组很具体的数字某算法在 N10,000 时约 5 天N100,000 时约 14.2 年N1,000,000 时约 140 个世纪。这三个数不是随便编的它们彼此自洽可以反推出复杂度。规模涨 10 倍时间从 5 天涨到 14.2 年即14.2 * 365 / 5 ≈ 1037倍。取对数log(1037) / log(10) ≈ 3.01所以是 O(N³)。再验一次1000³ 10⁹倍5 天 × 10⁹ 显然远超 140 个世纪所以第三个数据对应的应该是另一种算法或不同常数不能混着算。import math def infer_exponent(t1, t2, n1, n2): 由两点耗时反推增长指数t 单位任意但必须一致 return math.log(t2 / t1) / math.log(n2 / n1) days lambda y: y * 365.0 print(round(infer_exponent(5.0, days(14.2), 10_000, 100_000), 2)) # 约 3.01 print(round(infer_exponent(days(14.2), days(140 * 100), 100_000, 1_000_000), 2))第一个结果 3.01 坐实 O(N³)第二个结果会明显偏离 3说明第三个数在前两个的模型下不自洽。这种不自洽本身就是信息要么数据抄错了要么中间换了算法。做线上性能分析时我经常这么干——拿压测的两个点先估阶估出来的阶和代码结构对不上就说明有隐藏的 O(N²) 在某个循环里。3.5 二分边界2.22 和 2.24 的「不推进」是怎么来的这两道题看着像送分题实际是二分查找最经典的死循环来源。条件是Low 1, High 2取Mid (Low High) / 2 1如果递归调用仍然是[1, 2]这个区间下一次还是Mid 1永远出不去。根因是区间收缩不严格。整除向下取整意味着Mid可能等于Low此时如果递归右半区写成[Mid, High]而不是[Mid1, High]区间大小不变。正确的写法是把区间不变式固定下来/* 左闭右开区间 [lo, hi)循环不变量答案若存在必在区间内 */ int lower_bound(const int *a, int n, int target) { int lo 0, hi n; while (lo hi) { int mid lo (hi - lo) / 2; /* 不用 (lohi)/2避免溢出 */ if (a[mid] target) lo mid 1; /* 严格排除 mid */ else hi mid; /* mid 仍可能是答案保留 */ } return lo; }参数n是数组长度target是目标值返回第一个不小于 target 的下标。lo (hi - lo) / 2和(lo hi) / 2在数学上等价但前者在 lo、hi 都接近INT_MAX时不会溢出这是工程代码里必须改的一处。习题 2.11 提到用二分变体在O(log N)内解决用的就是这套区间不变式思路。4. 树、哈希与并查集把纸面结论写成断言中间这几章的答案大多是「结论 一句理由」看起来没营养但只要把结论转成可执行的断言价值立刻不一样。4.1 树的 11 页AVL 平衡因子与四种旋转的核对脚本树章是全书最厚的一章平衡树部分的手算答案尤其容易看走眼书上写「插入后做一次双旋」你手算出来是单旋谁对别争写代码验。class Node: __slots__ (key, left, right, h) def __init__(self, key): self.key, self.left, self.right, self.h key, None, None, 1 def h(t): return t.h if t else 0 def upd(t): t.h 1 max(h(t.left), h(t.right)) def bf(t): return h(t.left) - h(t.right) # 平衡因子 左高 - 右高 def rot_right(y): x y.left y.left x.right x.right y upd(y); upd(x) # 先更新下层再更新上层 return x def rot_left(x): y x.right x.right y.left y.left x upd(x); upd(y) return y def insert(t, key): if t is None: return Node(key) if key t.key: t.left insert(t.left, key) elif key t.key: t.right insert(t.right, key) else: return t # 重复键直接返回 upd(t) b bf(t) if b 1 and key t.left.key: # LL return rot_right(t) if b -1 and key t.right.key: # RR return rot_left(t) if b 1 and key t.left.key: # LR t.left rot_left(t.left); return rot_right(t) if b -1 and key t.right.key: # RL t.right rot_right(t.right); return rot_left(t) return t def check(t): 返回 (是否有序, 是否平衡)两个都为 True 才算插入正确 keys, stack, cur [], [], t while stack or cur: while cur: stack.append(cur); cur cur.left cur stack.pop(); keys.append(cur.key); cur cur.right ordered keys sorted(keys) balanced all(abs(bf(x)) 1 for x in _walk(t)) return ordered, balanced def _walk(t): if not t: return yield t yield from _walk(t.left) yield from _walk(t.right)两个细节值得说。upd的调用顺序在旋转里是先下层后上层写反了高度就是错的而高度错了平衡因子就错最终表现为「有时候该转不转」——这种 bug 极难靠肉眼发现。bf的符号约定要和判断分支严格对齐左高为正、右高为负一旦反了四种旋转会全部错位。插入一串随机数后跑check两个返回值都为 True手算结果才有底气。4.2 哈希的 4 页装填因子和冲突策略的实测哈希章只有 4 页主要讲函数选择和冲突解决。这部分的答案基本都是公式光看没用得跑出实际数字对比。常见做法是拿同一批键分别跑线性探测和链地址法比较平均探测次数def linear_probe_avg(keys, m): table [None] * m probes 0 for k in keys: i k % m while table[i] is not None: # 线性探测冲突就往后挪一格 i (i 1) % m probes 1 table[i] k probes 1 return probes / len(keys) def chaining_avg(keys, m): buckets [[] for _ in range(m)] probes 0 for k in keys: b buckets[k % m] probes len(b) 1 # 比较完整个链再插入 b.append(k) return probes / len(keys) import random random.seed(7) for m in [1009, 503, 251]: # 装填因子依次 0.5 / 1.0 / 2.0 keys random.sample(range(10**6), m // 2 * 2) print(m, round(linear_probe_avg(keys, m), 2), round(chaining_avg(keys, m), 2))参数m取质数是关键取合数时k % m的分布会出现明显周期性探测次数虚高。你会看到装填因子从 0.5 涨到 2.0 时线性探测的平均次数增长远快于链地址法这就是「开放定址对装填因子敏感」这句话的真实含义。手册里给的那些渐近公式只有在这种实测曲线上才有体感。4.3 并查集的 3 页路径压缩和按秩合并到底省了多少次跳转第 8 章只有 3 页讲的是不相交集合结论是「两种优化都用上摊还复杂度接近常数」。这个「接近常数」到底多接近加个计数器就知道了class DSU: def __init__(self, n): self.p list(range(n)) self.r [0] * n self.hops 0 # 累计指针跳转次数 def find(self, x): while self.p[x] ! x: self.p[x] self.p[self.p[x]] # 路径减半 x self.p[x] self.hops 1 return x def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False if self.r[ra] self.r[rb]: ra, rb rb, ra self.p[rb] ra # 矮树挂到高树下 if self.r[ra] self.r[rb]: self.r[ra] 1 return True把「路径减半」和「按秩合并」分别关掉跑同样的合并序列hops的差距通常是几倍到几十倍而且规模越大差距越明显。这就是手册里那句「摊还 O(α(N))」的实测意义α(N) 在 N 小于 10 的 600 次方时都不超过 4所以实际就是常数但前提是两个优化都得在。4.4 堆与排序比较次数、逆序对和稳定性的一次对照堆章和排序章加起来 13 页答案里反复出现「平均 O(N log N)」「不稳定」这类结论。想真正记住最省事的办法是写一个统一的测试脚手架对每种排序统计比较次数和交换次数再用一组含重复键的数据检查稳定性。同一组长度为 10⁴ 的随机数据和一组近乎有序的数据各跑一遍你会看到插入排序在后一组上直接退化成 O(N)、快排在已排序输入上如果 pivot 取首元素会退化成 O(N²)。这两条比背十遍结论都管用也是实际写业务代码时选择排序策略的依据。5. 避坑与排查五条血泪记录里最值得先看的5.1 抄下来的代码编译不过报一堆「未定义标识符」现象把 Fig 1.1 的代码复制进.c文件编译器报IntPart、DecPart、PrintDigit、PrintOut未声明。原因手册假设你手边有原书正文这四个函数在正文里定义过答案册只给被考的那部分逻辑。解决按 2.2 节的补全版本自己实现并把它们标成static避免和工程里同名函数冲突。凡是手册里出现但你没见过的函数名先在原书对应章节找一遍找不到就按语义补。5.2 增长率排序里把N log N和N log(N²)当成两个不同阶现象排序结果和标准答案差一位但怎么看都觉得有道理。原因log(N²) 2 log N只差常数因子。大 O 记号忽略常数两者同阶。解决判阶一律用比值法f(n)/g(n)趋于常数就是同阶趋于无穷才是高阶。别靠肉眼扫函数形式尤其是带对数的组合。5.3 直接把 2.8 的耗时数据当基准外推自己的系统现象照着「N10,000 约 5 天」推算出自己服务在百万数据下要跑多久结果差了几个数量级。原因那组数字是在特定机器、特定实现、特定常数因子下算出来的只用来演示「复杂度差一阶实际耗时就差出天际」不是任何真实系统的基准。解决只用它验证阶数推断方法实际外推必须用自己的机器打两个点。外推前先确认两件事数据规模还在同一复杂度区间内且没有触发缓存、分页、GC 这类非线性因素。5.4 手册版本和手上的教材对不上题号错位现象按题号 4.18 去查内容和教材上的 4.18 完全不是一回事。原因手册前言里写明了答案反映的是「第一次印刷」的状态后续印次教材有修订题号和题面都可能微调。解决以题面内容为准不以题号为准。查之前先扫一眼题目关键词对不上就前后各翻一页。做索引时把题面的前十几个字符一起存进去比只存题号稳。5.5 洗牌算法「看起来不随机」改完之后反而不等概率现象习题 2.7 第三种洗牌法Floyd 算法看着像没洗匀于是把循环里的交换改成Swap(A[i], A[RandInt(0, N-1)])觉得这样更随机。原因手册明确写了这么改之后不是所有排列等概率。N3 时三次交换共 27 种等可能路径而排列只有 6 种27 不能被 6 整除必然有排列被多算。解决判断随机算法对不对看的是「路径总数能否被结果数整除」以及归纳证明不是看代码顺不顺眼。任何「我觉得这样更随机」的改动都要先用小规模穷举统计频次验证。6. 把它当回归测试集一套可复用的章节自检流程读到最后会发现这份手册最大的用处不是提供答案而是提供了一批「已知正确」的结论。把这些结论写成断言每读完一章跑一遍比反复翻书有效得多。我现在的固定动作是每章挑三到五个可验证的结论落到一个测试文件里。import math import pytest def test_growth_same_order(): 2.1N log N 与 N log(N^2) 同阶 for n in (1 8, 1 16, 1 20): assert n * math.log2(n * n) pytest.approx(2 * n * math.log2(n)) def test_pow_multiplier_formula(): 2.17乘法次数 floor(log2 N) b(N) - 1 for n in range(2, 200): expect (n.bit_length() - 1) bin(n).count(1) - 1 assert expect 0 def test_binary_search_terminates(): 2.22区间必须严格收缩否则死循环 a [1, 2] lo, hi 0, len(a) steps 0 while lo hi: mid lo (hi - lo) // 2 lo mid 1 if a[mid] 2 else lo hi mid if a[mid] 2 else hi steps 1 assert steps 10, 区间未收缩出现死循环这套东西的价值随时间增长。半年后你回头复习不用重读 60 页跑一遍测试哪个断言红了就回哪一节。带课讲题也一样学生问「为什么这里要双旋」你把check()的两个返回值打印出来给他看比讲十分钟定义管用。还有一个进阶用法把手册里的结论当「预言机」去校验你自己写的实现。比如你写了一个 AVL先用手册的思路手算一遍插入序列的旋转次数再让代码输出实际旋转次数两者对上才算过。这个流程我做课程设计时会强制走一遍因为手算暴露的是理解漏洞代码暴露的是实现漏洞只做一边总有盲区。血泪经验是这么来的早些年我读这类答案册习惯一口气看完一章然后合上觉得「都懂了」。等到真正写代码时才发现看懂的只是「这个结论长这样」不是「为什么必须是这个结论」。后来我强制自己每读完一章就把关键结论写成断言跑一遍跑不过就回去重读那一节——从那以后凡是带答案的教材我都先建测试再读正文不再相信合上书那一刻的「懂了」的感觉。这份手册公开资料里按书名加 solutions manual 就能搜到同一份文件六十多页转成文本建好索引配合上面这套断言一章一章啃下来数据结构与算法分析这块地基算是能踩实了。希望帮到你。本文还有配套的精品资源点击获取