Appearance
性质推导与最优性论证：结论后面得跟一句凭什么（专题总纲）
Intro
数据结构的大题里有这么几道，读完题干会发现横线上填不进任何东西：题面让你把「凭什么」当场写出来。
这五道题的题面是这样开口的：
- 2009 那道最直接——「若该方法可行，请证明之；否则，请举例说明」；
- 2016 那道在总问句里挂了半句——「请回答下列问题并给出推导过程」；
- 2012 那道在第 (2) 问追一句——「描述 N（N ≥ 2）个不等长升序表的合并策略，并说明理由」；
- 2015 那道换了个问法——「矩阵 A² 中位于 0 行 3 列元素值的含义是什么」「Bᵐ 中非零元素的含义是什么」；
- 2013 那道把要求藏在半句限定里——「且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？」
前三道明写着要论证，后两道要你自己认出来。 2015 问「含义」，答一个词是拿不到分的，得说清这个数是怎么数出来的；2013 通篇没有「理由」两个字，但「更短」这半句就是在让你论证自己给的排法确实到头了。
论证只有两种造法
把这五道题的标准答案并排看，卷面上写的东西可以归成两类动作：
第一种：把同一个量从两个角度各数一遍，让等式把公式逼出来。第二种：摆出一个具体的例子——一张图、一个排列、一棵树、一个合并顺序——当场算出它的代价，再跟对手比一次。
第一种用来推性质（2016、2015）；第二种既能打掉一个猜想（2009），也能论证某个安排已经到头了（2012、2013）。
认出手上要造哪一种，这道题就下笔了。
造法一：把同一个量数两遍
下笔方式：挑一个能从两个角度数的量，两边各写一个表达式，画等号，解出未知量。
2016 那道——正则 k 叉树有 m 个非叶结点，问叶结点几个。要数两遍的那个量是「非根结点」：
- 从父亲这边数：每个非叶结点都有 k 个孩子，m 个非叶一共生出
个孩子；而树里除根以外的每个结点都恰好是某个结点的孩子，于是孩子总数就是非根结点总数 → 。 - 从自己这边数：结点总数是
，除掉根，非根结点有 个。
两个表达式说的是同一堆结点，画等号：
2015 那道——要数两遍的量是「从顶点 0 出发走两步到顶点 3 的走法」：
- 从矩阵这边数：按矩阵乘法的定义，
； - 从图这边数：求和里每个非零的乘积项
，当且仅当边 (0,k) 和边 (k,3) 同时存在——一个非零项就是一条经过中转点 k 的两步走法。
于是「矩阵的这一格」和「走法条数」是同一个数。第 (3) 问把它推广到
要求上下界，就把两种极端形态画出来再数
2016 第 (2) 问要高度为 h 时结点数的最多与最少，做法仍然是数，只是先得把「最挤」和「最松」两种树各画出来：
| 极端 | 树长什么样 | 数出来 |
|---|---|---|
| 最多 | 每层都填满 | |
| 最少 | 每层只留 1 个非叶继续往下长，其余 |
「最少」那一档不能凭感觉写。 题面规定了「每个非叶结点都有 k 个孩子」，一个非叶就得配满 k 个孩子、少一个都不算正则——所以第 2 到第 h 层每层仍有 k 个结点，而不是 1 个。
造法二：摆出一个具体的例子
下笔方式：先把东西摆出来，再当场演算它的代价，最后跟对手比一次。三步缺一步就掉分。
打掉一个猜想（2009）
题面给了三步：从当前顶点 u 出发，「选择离 u 最近且尚未在最短路径中的一个顶点 v」，加入路径、u 换成 v，直到 u 是目标顶点。问这样能不能求出最短路径。
否掉它的全部工作量就是造一张图，让这个方法走岔：
摆 → 跑（题面方法给出的路径与长度）→ 比（真正的最短路径与长度）。两条线都要有数值，只画图不演算，那一档分拿不到。
论证一个安排已经到头（2012、2013）
摆出来之后，还要回答「凭什么不能更好」。说法有两条路：
- 引一条已有的定理。 2012 那道先把「总比较次数」翻译成一个已知量：把每次合并看成合并树里的一个内部结点，代价是左右子表长度之和，加起来正好是这棵树的 WPL；而哈夫曼算法保证 WPL 最小。定理一引，最优性就成立了。
- 把可能性穷举干净。 2013 第 (2) 问只有 4 个关键字，合法的二叉排序树形态一共 14 棵，按根结点归成四类扫一遍，最小的 ASL = 2.00 就是扫出来的。规模小的时候，穷举是完全正当的论证。
还有一个能自查的巧合：2012 那道五次合并的代价按
边界必错点
2009 那道：反例要跑到底，还要先确认它真的会走岔。 两件事各占一档分——给出反例图是一档，在图上双线演算又是一档。只画图不算数值，第二档直接没有。另外，自己造的图要先拿题面方法跑一遍：若把边权凑成 S→A=1、A→T=1、S→B=3、B→T=10，题面方法走的恰好就是最短路径，这张图什么也证不了。
2015 那道：
2016 那道：最少那一档常被写成 h 或者
2013 那道：最优二叉排序树必须守住左小于根、根小于右。 拿哈夫曼树的做法把概率大的往浅处放，得到的结构已经不是二叉排序树，这一问按错处理。这道题恰恰是反例：概率最大的 do 和 while（各 0.35）都在第 2 层，根是概率只有 0.15 的 for。
2012 那道：合并产生的新表立刻回到候选池。 第 2 轮选中的是 40 和 45，那个 45 正是第 1 轮 10+35 的产物；若还在原始六个表里挑，第 2 轮就会选 40 和 50，后面四轮跟着全错。
一道题的答卷长什么样
取 2009 那道，满分 10 分。下面这四段就是卷面上要写的全部内容——每一段对着一档分。
① 结论
上述方法不能保证求得最短路径。下面举反例说明。
② 反例（把图摆出来，边权写死）
取有向带权图 G：顶点 S、A、B、T；边 S→A = 1，A→T = 10，S→B = 3，B→T = 1。起始顶点 S，目标顶点 T。
A
1 ↗ ↘ 10
S T
3 ↘ ↗ 1
B③ 双线演算（题面方法一条线，真实最短一条线）
按题面方法：
- u = S：与 S 相邻且尚未在路径中的顶点为 A（距离 1）、B（距离 3），最近的是 A，加入 A，u ← A；
- u = A：与 A 相邻且尚未在路径中的只有 T（距离 10），加入 T，u ← T = 目标，算法终止。
- 得到的路径 S→A→T，长度 = 1 + 10 = 11。
而 S→B→T 的长度 = 3 + 1 = 4，且 4 < 11。 故题面方法给出的路径长于真正的最短路径，结论成立。
④ 错因
题面第 ② 步写的是「选择离 u 最近且尚未在最短路径中的一个顶点 v」，通行读法是在当前顶点 u 的出边里挑最近的一个，于是被局部的短边 S→A = 1 引走；它从不比较各顶点到起始顶点的累计距离。Dijkstra 每轮是在所有已确定顶点的出边里选「起点累计距离 + 边权」最小的那一个，因此有全局视野。
⚠️ 三个容易掉的地方：① 段答「能」并去证明它，方向就错了，后面写再多也不给分；③ 段只写题面方法的结果、不写真正的最短路径，比较就没发生；④ 段答一句「贪心不总是对的」太泛，要点出是「邻居视角」和「全局累计距离视角」的差别。
同一份卷面换成造法一，骨架短得多。以 2016 第 (1) 问为例（结论一档分、推导一档分）：
结论：叶结点有
个。 推导：数「非根结点」这一堆结点。每个非叶恰有 k 个孩子，m 个非叶共生出 个孩子；树中除根外每个结点都恰是某结点的孩子，故非根结点数 = 。另一方面结点总数为 ，除去根后非根结点数 = 。两者相等： ，解得 。 自验： 、 时 ，总结点 7，正是高度为 3 的满二叉树。
「自验」那一行值得养成习惯。 推公式最怕系数错一位，代一组小数字进去一秒就能查出来。
造法二的另一半：论证一个安排已经到头
打掉猜想只是造法二的一半，另一半是反过来——给出一个安排，并论证它已经最优。 这一半占了两道题 20 分，卷面结构和「举反例」完全不同：先给方案，再算代价，最后引一条定理封口。
2012 年那道（合并 6 个有序表）：
合并过程（每轮挑当前最短的两个表）：
10 + 35 → 45 比较 44 次
40 + 45 → 85 比较 84 次
50 + 60 → 110 比较 109 次
85 + 110 → 195 比较 194 次
195 + 200 → 395 比较 394 次
最坏总比较次数 = 44+84+109+194+394 = 825⚠️ 每轮的比较次数是
第 (2) 问才是论证，两句话缺一不可：
策略：每次选当前最短的两个表合并（等价于以各表长为权构造哈夫曼树，自底向上合并）
理由：总比较次数约等于这棵合并树的带权路径长度 WPL，
而哈夫曼算法保证 WPL 最小 —— 长表越晚参与合并，被反复搬动的次数越少引哈夫曼定理就是封口的动作。 只写「每次选最短两个」而不说为什么最优，第 (2) 问拿不满。
2013 年那道（4 个元素怎么放），两小问各给一个方案加一个 ASL：
(1) 顺序存储：按查找概率非升序排列 → do, while, for, repeat
用顺序查找
ASL = 0.35×1 + 0.35×2 + 0.15×3 + 0.15×4 = 2.10
(2) 链式存储：按概率构造最优二叉排序树，用 BST 查找
以 for 为根或以 repeat 为根都可以，两种的 ASL 都是 2.00⚠️ 第 (2) 问的根不唯一——for 和 repeat 两种都是标答接受的。 写了另一个的人不要以为自己错了；关键是把加权深度和算成 2.00，那 3 分给在这个数上。
真题的两种形态
第一组 · 把同一个量数两遍（2016·42、2015·42）——正则 k 叉树的叶结点数、高度为 h 时结点数的上下界；邻接矩阵的平方与
第二组 · 摆出一个具体的例子（2009·41、2012·41、2013·42）——举反例否掉「每步走最近的邻居」；给出 6 个不等长有序表的最优合并顺序与最坏总比较次数；给出 4 个关键字在顺序存储与链式存储下各自的最优排列、查找方法与 ASL。手上做的是：先摆出来，再算代价，最后跟对手比一次。
两组的分界画在动作上：2016 考树、2015 考图，归在一起；2009 考图、2013 考查找，也归在一起。看的是你手上那支笔这一刻正在写什么。
巩固栏只收要写论证的题
别的专题的巩固栏用来补真题没正面考过的知识点。这个专题的巩固栏做的是另一件事：只收题面真的要你写出理由的题，一道算数值的都不收。
站内数据结构有 86 道综合型巩固题，其中题面明写「给出证明」「若不正确给出反例」「证明该结论普遍成立」「说明理由」的，一共五道。这五道全部收进来了，而且正好两种造法都有：
| 巩固题 | 造法 | 与哪道真题同构 |
|---|---|---|
| 破圈法求 MST 对不对 | 造法二（对就证、错就举反例） | 2009·41，连题面结构都一样 |
| Dijkstra 生成树是不是 MST | 造法二 | 2009·41 |
| 造法一 | 2015·42 | |
| 先序加中序为何唯一确定一棵二叉树 | 造法一（递归奠基 + 递归步） | 2016·42 的推法 |
| 森林先根遍历与转换后二叉树先序遍历相同 | 造法一 | 2016·42 的推法 |
其余 81 道不收。它们是给参数算个数出来——算 ASL、算结点数、算比较次数、算探查序列。填进来读者会做完十道得到「我又算对了十次」，而这五道真题的分给的是「你有没有把话说清楚」。用算数值的题冒充论证题的补位，比空着更糟，因为它会让人以为自己练过了。
所以这一栏比别的专题短，只有五道，但每一道都要求你在卷面上写出一段能站住的理由。
另外，这五道真题本身也是材料：两种造法各有完整示范，判分维度细到能当检查表用（反例必须双线演算、
和算法代码题正好成对
算法代码题专题的指导思想是一句话：
所有算法的原子操作都一样——增、删、改、查。最优解并没有发明新的原子操作，它只是砍掉了暴力解里重复和无用的那部分。
这个专题接着问下一句：凭什么砍掉那部分之后，答案还是对的、还是最优的。
一个讲怎么构造，一个讲凭什么成立。2012 那道最能看出两边的接缝：「每次选最短的两个表合并」这条策略，在算法代码题那边不过是一个小根堆循环——弹两次、压一次、重复 N−1 轮；到了这边，题面追一句「说明理由」，你就必须把「总比较次数等于这棵合并树的 WPL」这一步显式写出来，再引哈夫曼定理封口。同一个贪心，一边考你写不写得出来，一边考你说不说得清凭什么。
两边的练法因此可以互相借：写代码的时候顺手问一句「我砍掉的那部分凭什么可以砍」，写论证的时候顺手问一句「这段论证落到代码上是哪几行」。这两问都答得上来，这道题才算真的过了。
（手推与逐步模拟那个专题的文末也提到过：外部排序那道要论证归并段长度的上下界、出栈序列那道要推卡特兰数——那部分的动作属于本篇的造法一。）
交卷前扫一眼
先认造法：数一个量数两遍，还是摆一个具体例子 · 反例要跑完两条线，并且先确认它真的走岔 · 求上下界先画最挤和最松两种形态 · 论最优先写清「代价等于什么量」，再引定理或穷举形态 · 推完公式代一组小数字自验 · 结论后面永远跟一句凭什么
配套内容
逐题精讲（建设中）——真题作答与 AI 判分入口见站内大题专题。
基础没打牢的，先回这几篇：
同科的另外两个大题专题：