13.6 章节回顾

本章可以压缩成一句话：线性结构看操作规则，数组矩阵看下标映射，树看性质与遍历，图看关系、存储和算法目标。

必会清单

模块	必会内容
顺序表/链表	随机访问、插入删除、单链表和双链表指针修改
栈/队列	LIFO、FIFO、出栈序列、循环队列队空队满
串	BF 与 KMP 的失配回退差异
数组	一维/二维地址计算，行优先与列优先
矩阵	上三角、下三角、对称、稀疏矩阵压缩
二叉树	满/完全、编号性质、$n_0=n_2+1$、空指针 $n+1$
遍历	先序、中序、后序、层序及序列还原
BST	左小右大，中序递增，退化与平衡动机
哈夫曼树	WPL、最小两权合并、前缀编码
图	邻接矩阵/表、DFS/BFS、拓扑、MST、最短路径

易错点集中纠偏

易错点	正确理解
线性结构必须连续存储	线性是逻辑关系，链表也可以是线性结构
链表插入语句顺序无所谓	顺序错误会丢失后继节点
队列和栈序列一样灵活	队列 FIFO，出队顺序固定；栈序列更灵活
KMP 就是主串和模式串都回退	KMP 主串不回退，模式串按 next 回退
完全二叉树就是满二叉树	完全二叉树最后一层可以不满，但必须靠左
先序/后序也能让 BST 有序	BST 的有序输出来自中序遍历
对称邻接矩阵一定是无向图	有向图双向边也可能形成对称矩阵
最小生成树等于最短路径	MST 是整体连接成本，最短路径是两点距离

考前 30 分钟复盘

1. 默写循环队列：队空、队满、长度公式。
2. 默写二维数组行优先/列优先地址公式。
3. 默写二叉树：第 $i$ 层最多节点、$n_0=n_2+1$、空指针 $n+1$。
4. 画一棵小树，分别写先序、中序、后序、层序。
5. 用 4-5 个权值手工构造一次哈夫曼树。
6. 对比 Prim、Kruskal、Dijkstra、Floyd 的目标。

本章收束

数据结构题的分数不是靠“见过名词”拿到的，而是靠过程：会数元素、会改指针、会模拟序列、会画树、会按图一步步走。把这些过程练熟，上午题里这一块会变成稳定得分区。