1. 顺序表 vs 链表的操作代价（一切比较的源头）

操作	顺序表	单链表
按序号取	$O(1)$ （基址 + i×元素大小）	$O(n)$
查找（无序）	$O(n)$	$O(n)$
插入/删除（已知位置）	$O(n)$ （搬移平均 n/2）	$O(1)$
空间	紧凑、需预估容量	每结点多一个指针域

真题：2013-1（两升序链表合并为降序，头插法 $O(\max(m,n))$ ）；2016-1（静态链表：数组下标当指针，链接地址推理）；2016-2、2023-2（双向链表插删的语句顺序：先接好新结点的两侧，再断旧链——写反就断链）；2021-1（循环链表尾指针删首元素）。

2. 栈的三大应用（选择题高频）

括号匹配：遇左括号入栈，遇右括号弹栈比对，串空栈空则匹配。
中缀 → 后缀表达式：操作数直接输出；操作符与栈顶比优先级，高于则入栈、不高于则弹栈输出再比；左括号入栈，右括号弹到左括号。2012-2（转换中栈内操作符最大个数 5）、2014-2（扫描到 f 时栈的内容）——模拟一遍栈变化即可。
后缀表达式求值：操作数入栈，遇操作符弹两个运算再压回（2018-1：双栈模型调用 3 次 F 后的栈顶值）。
递归与栈：函数调用的返回地址、参数、局部变量都压在系统栈上——“用非递归重写递归程序时必须用栈”（2017-2 I 正确）；这也解释了 DS-3 中遍历递归算法的本质。

3. 循环队列的实现要点

牺牲一个存储单元区分空满（为什么不利用全部单元：若 front==rear 既表示空又表示满会歧义；替代方案是加计数器或标志位）。入队 rear=(rear+1)%n、出队 front=(front+1)%n。判空判满条件严格依赖题目对 front/rear 的定义——2011-3 与 2014-3 两题指针定义不同，答案形式完全不同，这是本模块最经典的“读题陷阱”。

4. KMP：为什么朴素匹配慢、next 怎么救

朴素匹配每次失配主串指针 i 回退到起点+1，最坏 $O(nm)$ 。KMP 的关键观察：失配时主串已扫描过的部分与模式串前缀是已知的，如果模式串前 $j$ 个字符存在长度 $k$ 的相等前后缀，则主串指针 i 不必回退，只需把模式串向右滑到“前缀对齐后缀”的位置（ $j \leftarrow next[j]$ ）。i 单调不减 → $O(n+m)$ 。

2015-8：i=j=5 失配，模式串 "abaabc" 的 next[5]=2 → 下次 i=5、j=2。
2019-9：给定主串模式串，数总比较次数（按 i 不退、j 按 next 跳模拟）。

next 数组本身只需识别思想（近年考应用而非手算大表）；手算时记住“最长相等前后缀长度 +1”的定义约定，注意个别教材从 0 开始编号，以题面为准。

5. 特殊矩阵压缩存储

对称矩阵、三对角矩阵、稀疏矩阵（三元组表/十字链表）：把 $n \times n$ 存成约一半或对角线带，地址映射公式 $k = i(i-1)/2 + j - 1$ （下三角、从 1 开始）——只需识别思想 + 会代公式。