数据结构与算法¶
本页补充堆、图存储、卷积神经网络和递归等基础概念。
1. 排序、查找与树图基础¶
排序稳定性与近乎有序数据¶
稳定排序在关键字相等时保持原记录的相对次序。通常认为冒泡排序、直接插入排序和归并排序是稳定的；快速排序、堆排序和选择排序通常不稳定，具体实现若改变相等关键字的相对位置也会破坏稳定性。
初始数据基本有序时，直接插入排序通常最有优势：每个元素只需向左移动少量位置，最好时间复杂度可达 O(n)；快速排序平均为 O(n log n)，若选取不当的枢轴，在有序数据上可能退化为 O(n²)；堆排序和选择排序通常仍为 O(n²) 或 O(n log n)，不会因基本有序而显著受益。
哈希查找¶
哈希表通过哈希函数把关键字映射到存储位置。装填因子 α = n/m，其中 n 为表中元素个数、m 为哈希表容量；α 越大，冲突通常越多，平均查找长度通常越长。平均查找长度还取决于哈希函数和冲突处理方法，例如开放定址法、链地址法。
在常见渐近分析中，哈希查找平均时间复杂度为 O(1)，但最坏情况下可能退化为 O(n)。若题目已给定装填因子及冲突处理条件，不能仅凭结点数 n 单独推断查找性能；表容量固定时，n 会通过装填因子 α=n/m 影响冲突和查找长度。
完全二叉树的数组下标¶
采用 1 起始下标存储完全二叉树时，结点 i 的左孩子为 2i，右孩子为 2i+1，父结点为 ⌊i/2⌋。共有 n 个结点时，结点 i 有左孩子的充要条件是 2i ≤ n，等价于 i ≤ n/2。采用 0 起始下标时，左、右孩子分别为 2i+1、2i+2。
二叉树结点度数关系¶
设二叉树中度为 0 的结点数为 n₀，度为 2 的结点数为 n₂，则恒有 n₀ = n₂ + 1。证明可由树的边数等于结点总数减 1，且边数也等于 n₁ + 2n₂ 得出：n₀+n₁+2n₂ = n₀+n₁+n₂-1。
图的广度优先遍历¶
广度优先搜索（BFS）从起点开始，先访问当前层的所有顶点，再访问下一层，使用队列保存待访问顶点；因此它类似于二叉树的层序遍历。深度优先搜索（DFS）则沿一条路径尽量深入，常用递归或栈实现，思想上更接近先序遍历。遍历图时必须设置 visited 标记，避免无向图回到已访问顶点或有向图重复处理。
2. 二叉堆¶
二叉堆是满足堆序性质的完全二叉树，通常用数组存储。最小堆要求每个结点关键字不大于子结点，根结点是全局最小值；最大堆则相反。下标从 0 开始时，结点 i 的左、右孩子下标分别为 2i+1、2i+2，父结点下标为 floor((i−1)/2)。
插入元素时先放到数组末尾，再不断与父结点比较并上浮，时间复杂度 O(log n)；删除堆顶时用末尾元素补到根，再向下选择更优子结点下沉，时间复杂度 O(log n)；查看堆顶为 O(1)。从无序数组建堆可用自底向上的下沉法，复杂度为 O(n)。二叉堆适合实现优先队列，但不支持像平衡搜索树那样高效地查找任意关键字。
3. 邻接矩阵¶
邻接矩阵用 n×n 矩阵 A 表示 n 个顶点之间的边：若顶点 i 到 j 有边，则 A[i][j] 记录 1 或边权，否则记录 0、无穷大或其他约定值。无向图的矩阵关于主对角线对称；有向图的矩阵不一定对称；带权图把边权放入矩阵。
邻接矩阵判断两点是否相邻为 O(1)，适合边较多的稠密图，也便于表示带权边和执行矩阵运算；但空间复杂度为 O(n²)，遍历某顶点所有邻接点需要 O(n)。稀疏图通常使用邻接表节省空间。无向图边数统计时要注意矩阵中的一条边会出现两次，不能把所有非零元素直接当作边数。
4. 拓扑排序¶
拓扑排序用于把带有先后依赖关系的任务排列成一个合法顺序。它针对有向图，把每条有向边 A → B 理解为“A 必须先于 B 完成”。拓扑序列要求：对每条边 A → B，A 在序列中都排在 B 前面。
例子：学习“事务并发”前要先掌握数据库基础，学习“恢复机制”前要先掌握事务并发，可以排列为：
因此，拓扑排序解决的不是按照编号排序，也不是求最短路径，而是把局部的依赖约束转换成全局可执行顺序。常见应用包括课程先修安排、项目任务编排、编译构建依赖和软件包安装顺序。
入度法（Kahn 算法）¶
- 统计每个顶点的入度，即指向它的边数。
- 把所有入度为 0 的顶点加入队列；它们当前没有前置依赖，可以先执行。
- 取出一个入度为 0 的顶点加入拓扑序列，并删除它发出的所有边；每删除一条边，就让对应后继顶点的入度减 1。
- 如果后继顶点入度变为 0，就加入队列，重复上述过程。
- 若最终输出顶点数等于顶点总数，拓扑排序成功；若仍有顶点未输出，说明图中存在环。
例如依赖关系为 A → C、B → C、C → D，A、B 初始入度为 0，可以先输出 A、B（先后顺序不唯一）；删除 A、B 的出边后，C 入度变为 0，再输出 C，最后输出 D。因此拓扑序列可能是 A, B, C, D，也可能是 B, A, C, D。
关键结论¶
- 拓扑排序只适用于有向无环图（DAG）。
- 一个 DAG 可能有多个合法拓扑序列；拓扑排序不一定得到唯一答案。
- 若每一步入度为 0 的顶点都只有一个，序列才可能唯一；考试中判断唯一性可观察是否始终只有一个候选节点。
- 使用邻接表实现 Kahn 算法时，时间复杂度为
O(V+E)，其中 V 是顶点数，E 是边数。 - 若存在环，例如
A → B → C → A，每个节点都存在前置依赖，初始可能没有入度为 0 的节点，无法排出合法顺序。
5. CNN 各层的作用¶
卷积神经网络（CNN）通过局部连接和权重共享提取具有空间结构的数据特征，常用于图像、视频和部分时序任务。
- 输入层：接收像素或特征张量，通常按高、宽、通道组织，并做归一化等预处理。
- 卷积层：用可学习卷积核在局部区域滑动并计算加权和，提取边缘、纹理、形状等局部模式；多个卷积核产生多个特征图。
- 激活层：对卷积结果施加 ReLU 等非线性函数，使网络能表达复杂非线性关系，并改善深层训练效果。
- 池化层：对局部区域做最大值或平均值汇聚，降低空间分辨率、压缩计算量并增强一定的平移鲁棒性；现代网络也常用步幅卷积替代部分池化。
- 归一化层：如 Batch Normalization，通过调整中间特征分布帮助训练稳定和加速收敛，具体位置依网络结构而定。
- 全连接层/分类头：整合高层特征，将其映射为类别得分、回归值或其他任务输出。
- 输出层：分类时常用 Softmax 得到多类概率，二分类可用 Sigmoid；损失函数把预测与标签的差异转化为训练目标。
不是每个 CNN 都必须包含所有层，网络结构会根据分类、检测、分割等任务调整。
6. 递归与程序调用不是一回事¶
递归是函数或过程直接、间接调用自身的定义方式；程序调用是一个更一般的概念，表示调用者把控制权交给另一个函数或过程，执行结束后再返回。普通函数调用可以不递归，递归调用则必然包含函数调用。
一个正确的递归过程至少需要基准情形和递归情形：基准情形直接给出结果并停止继续调用；递归情形把问题缩小为更小的同类问题，并最终到达基准情形。每次调用都会在调用栈中保存参数、局部变量和返回位置，因此递归过深可能栈溢出，重复子问题还可能造成指数级时间。若能用循环或显式栈保存状态，可将递归改写为迭代形式，但要保持相同的终止条件和状态转移。
递归算法的时间复杂度¶
求递归算法的时间复杂度，不能只看递归“调用了几层”，而要看所有递归调用总共执行了多少工作。通用步骤如下：
- 确定输入规模
n，例如数组长度或整数大小。 - 写出一次调用中除递归调用外的工作量，记为
f(n)。 - 数清本次调用产生了几个子问题，以及每个子问题的规模。
- 写出递推式
T(n)，补上基准条件。 - 用递归树、展开法、主定理或记忆化分析递推式，最后保留最高阶项。
常见形式：
其中 a 是每次产生的子问题数量，n/b 是每个子问题规模，f(n) 是当前层的非递归工作。
例 1：每次只递归一个、规模减半¶
二分查找每次只保留一半数据，并做常数次比较：
每次规模减半，直到变成 1，需要约 log₂n 层，因此：
注意：递归深度和调用总数在这种“每层只有一个调用”的情况下都约为 log n。
例 2：分成两个子问题并线性合并¶
归并排序把数组分成两个大小约为 n/2 的子数组，再用 O(n) 时间合并：
递归树每一层所有节点的合并工作总和都是 O(n)，树高为 O(log n)，所以：
例 3：递归分叉但不缩小到一半¶
朴素递归斐波那契数列会同时计算 fib(n-1) 和 fib(n-2)：
大量子问题重复计算，递归树节点数呈指数增长，常用上界写作：
若使用记忆化或自底向上的动态规划，每个 fib(k) 只计算一次，则时间复杂度可降为 O(n)，空间复杂度通常为 O(n)；若只保留最近两个状态，空间可降为 O(1)。
递归复杂度易错点¶
- 递归深度表示调用栈最大层数，不一定等于总时间复杂度。
- 递归调用次数要结合每次调用的工作量计算，不能只看单次调用。
- 多个递归分支可能重复计算同一子问题，需判断是否存在重叠子问题。
- 最好先写递推式再判断复杂度，不要凭“递归看起来很深”直接下结论。
- 空间复杂度要单独分析：通常至少包括最大递归深度造成的调用栈空间；若有数组、哈希表或记忆化表，还要加上额外空间。
来源：补充知识点1.md
考前易错速记¶
二分查找时间复杂度为 O(log n)，哈希查找平均 O(1)，快速排序平均 O(n log n)。B+ 树适合数据库索引和范围查询；哈希索引适合等值查找，通常不适合范围查询。
广义表是线性表的推广，元素可以是原子或子表；长度是最外层元素个数，深度是括号最大嵌套层数。表头是第一个元素，表尾是其余元素组成的表，因此表尾仍然是表。
来源：专业课速记/09_考前必背清单.md
大纲补充：数据结构、算法与复杂度
数据是信息的载体，数据元素是讨论的基本单位，数据项是元素中不可再分的组成部分。数据对象是性质相同的数据元素的集合；数据结构研究元素之间的关系。逻辑结构包括集合、线性结构、树形结构和图状结构；存储结构包括顺序、链式、索引和散列存储。逻辑上的相邻不代表物理地址相邻，抽象数据类型（ADT）描述数据及其操作，不绑定某一种具体实现。
算法是解决问题的有限步骤，通常具有有穷性、确定性、可行性、零个或多个输入、一个或多个输出；正确性、可读性、健壮性和效率是评价要求。程序是算法的一种实现，算法不等于某段特定语言的代码。
时间复杂度按输入规模 n 统计基本操作增长趋势；O 表示渐近上界，Θ 表示渐近紧确界。最好、平均、最坏复杂度要分别说明，平均情况需要输入分布假设。空间复杂度通常指辅助空间，包含递归栈，不把输入本身重复计入；题目若要求总存储量则另算。常见增长次序为 1 < log n < n < n log n < n² < 2^n < n!。
补充样例 1：逐层统计基本操作
外层 i 从 1 到 n，内层执行 i 次，操作总数为 1+2+…+n=n(n+1)/2，故为 Θ(n²)；若循环变量从 1 开始每次乘 2，直到超过 n，则执行 ⌊log₂n⌋+1 次，为 Θ(log n)。两个循环若是先后执行，应相加而不是相乘；只使用固定数量计数器时辅助空间为 O(1)。
线性结构：数组、链表、栈与队列
数组以连续单元存储同类型元素，支持按下标 O(1) 随机访问；在数组中部插入、删除通常需移动元素，为 O(n)。线性表是逻辑结构，顺序表和链表是不同实现，不能把“线性”误解成一定连续存储。
补充样例 2：数组地址与插入移动
一维数组 A[0…4] 首地址为 1000，每个元素占 4 Byte，则 A[3] 地址为 1000+3×4=1012。若当前顺序表为 [10,20,30,40]，容量至少为 5，在下标 1 插入 15：先把 40、30、20 依次右移，再写入 15，得到 [10,15,20,30,40]，共移动 3 个原元素。必须从后往前移动，避免覆盖。
链表用指针连接结点，不要求地址连续；单链表按序号访问为 O(n)。已知插入位置的前驱时插入为 O(1)；只知道待查关键字时还需先查找。双链表增加前驱指针，便于双向访问和删除已知结点，但多占指针空间；循环链表的尾结点指向头结点或头哨兵，判结束时不能一概用空指针。
补充样例 3：单链表插入与删除
已有 A → B → C，p 指向 A，要在 A 后插入 X：先令 X.next=p.next，再令 p.next=X，得到 A → X → B → C。删除 X 时先保存 q=p.next，再令 p.next=q.next，最后释放或交给内存管理机制回收 q。若先改 p.next 再取原后继，可能丢失链；带头结点的空表通常为 head.next=null，头结点不计入有效元素数。
栈遵循后进先出（LIFO），在栈顶入栈、出栈，适合括号匹配、函数调用和表达式求值；队列遵循先进先出（FIFO），在队尾入队、队头出队，适合任务缓冲和 BFS。普通栈、队列的基本端点操作通常为 O(1)，但动态数组扩容的单次操作可能为 O(n)。
补充样例 4：栈操作与括号匹配
依次压入 1、2，弹出得到 2，再压入 3，随后两次弹出依次得到 3、1，出栈序列为 2,3,1。检查 ([)] 时，读入 (、[ 后栈顶为 [，遇到 ) 与栈顶不配对，立即判错；全部扫描后栈非空也不能判为匹配。
补充样例 5：循环队列判空判满
使用长度为 5 的数组，front 指向队头，rear 指向下一入队位置，并牺牲一个单元：空为 front=rear，满为 (rear+1) mod 5=front，长度为 (rear-front+5) mod 5。从 (0,0) 入队 A、B、C 后为 (0,3)；出队两次得到 A、B，状态为 (2,3)；再入队 D、E、F 后为 (2,1)，长度为 4，已满。这里容量为 4，不是 5。
字符串、集合与搜索
字符串是字符组成的有限序列，空串长度为 0；子串必须连续，子序列可以不连续。朴素模式匹配在长度 n 的文本中寻找长度 m 的模式，最坏为 O(nm)；KMP 用模式串的前后缀信息避免文本指针回退，预处理为 O(m)，匹配为 O(n+m)，失配表的下标定义需与实现一致。
补充样例 6：字符串匹配位置
文本 ababc、模式 abc，按 0 起始下标：从位置 0 比较，前两个字符相同，第三个字符 a≠c，失配；从位置 1 首字符即失配；从位置 2 连续匹配 a、b、c，故首次匹配位置为 2。按 1 起始位置回答则为 3，答题必须先声明下标约定。
集合中的元素不重复且没有固有次序；多重集合允许重复。集合的并、交、差是逻辑操作，可用有序表、位图或哈希表实现。位图适合有限、可编号的元素域；并查集用合并和查找维护不相交集合，常用于连通分量判断，不等同于普通关键字查找表。
补充样例 7：集合运算与顺序查找
A={1,2,4}、B={2,3}，则 A∪B={1,2,3,4}、A∩B={2}、A−B={1,4}。在无序数组 [7,2,9,4] 中顺序查找 9，要比较 7、2、9 共 3 次；查找不存在的 5 要比较 4 次，最坏为 O(n)，不要求有序。
补充样例 8：二分查找全过程
有序数组 [3,8,12,17,25,31,42]，使用闭区间 [low,high] 和 0 起始下标，查找 25：初始 (0,6)，mid=3，对比 17 后改为 (4,6)；mid=5，对比 31 后改为 (4,4)；mid=4，找到 25，共 3 次关键字比较。未找到时以 low>high 结束。二分查找要求关键字有序，并依赖高效的中点访问，不能直接认为链表上的查找也是 O(log n)。
树与二叉树
树是 n 个结点的有限集合；非空树有一个根，每个非根结点恰有一个双亲，共 n−1 条边。结点的度是孩子数，树的度是最大结点度，叶结点的度为 0。这里根所在层为第 1 层，高度按层数计；其他教材也可能按边数计，高度公式须先确认约定。
二叉树每个结点最多两个孩子，且区分左右；满二叉树（各层均满）高度 h 时有 2^h−1 个结点；完全二叉树除最后一层外各层满，最后一层从左连续排列，不能出现中间空位。二叉搜索树的左子树关键字小于根、右子树大于根（此处假定关键字互异），查找为 O(h)，退化成链时为 O(n)；平衡搜索树把高度控制在 O(log n)。
补充样例 9：树的遍历与搜索
根为 4，左孩子 2、右孩子 6，2 的左右孩子为 1、3：先序为 4,2,1,3,6，中序为 1,2,3,4,6，后序为 1,3,2,6,4，层序为 4,2,6,1,3。它也是一棵二叉搜索树，查找 3 依次访问 4、2、3。先序是“根左右”，中序是“左根右”，后序是“左右根”，中序有序是搜索树的性质，不是所有二叉树的性质。
图的类型、存储、遍历与拓扑
图由顶点集 V 和边集 E 组成。无向图的边没有方向，有向图用弧表示方向；带权图为边赋权。简单图不含自环和重边；n 个顶点的简单无向图最多 n(n−1)/2 条边，简单有向图最多 n(n−1) 条弧。无向图连通指任意两点间存在路径；有向图强连通要求任意两点可相互到达，弱连通只要求忽略方向后连通。
无向图所有顶点度数之和为 2E；有向图所有入度之和、出度之和都为 E。邻接表为每个顶点保存邻接点，空间为 O(V+E)；无向边通常保存两次。邻接矩阵空间为 O(V²)，带权图不能简单把 0 当作无边，因为边权可能为 0，需另约定无穷大等标记。
补充样例 10：图存储与遍历
无向图顶点为 A、B、C、D，边为 AB、AC、BD、CD，邻接表按字母序排列为 A:B,C；B:A,D；C:A,D；D:B,C。度数均为 2，度数和为 8，边数为 4；矩阵中有 8 个表示边的 1。从 A 开始，BFS 在入队时标记访问，输出 A,B,C,D；DFS 按字母序选择邻接点，输出 A,B,D,C。两种序列都依赖邻接点访问顺序；非连通图需再从未访问顶点启动遍历。邻接表遍历为 O(V+E)，邻接矩阵遍历为 O(V²)。
补充样例 11：拓扑排序与环检测
有向边 A→C、B→C、C→D，初始入度为 (A:0,B:0,C:2,D:1)。先输出 A 后 C 入度变为 1；再输出 B 后 C 入度变为 0；依次输出 C、D，得到 A,B,C,D。若增加 D→B，初始仅 A 入度为 0，输出 A 后其余点仍有前驱，总输出数 1 小于 4，说明存在环 B→C→D→B。并非只有“初始没有零入度点”才说明有环。
递归设计与排序选型
递归设计按“明确函数含义 → 写基准情形 → 缩小规模 → 合并结果 → 检查终止和复杂度”展开。每条递归路径都应趋向基准情形；存在递归调用并不自动保证终止。尾递归是否节省栈空间取决于语言和编译器是否优化，不能默认辅助空间为常数。
补充样例 12：阶乘递归的返回过程
定义 fact(0)=1，非负整数 n 满足 fact(n)=n×fact(n−1)。计算 fact(3)：调用链为 fact(3)→fact(2)→fact(1)→fact(0)，再依次返回 1、1、2、6。递推为 T(n)=T(n−1)+O(1)，时间为 O(n)，调用栈为 O(n)；需排除负数输入，并注意有限位宽整数的溢出。
排序按关键字使记录有序；稳定性关注相等关键字记录的先后，不是算法运行时间是否波动。下表按常见数组实现讨论，空间为辅助空间，归并排序不计输入输出重复占用。
| 排序 | 最好时间 | 平均时间 | 最坏时间 | 辅助空间 | 通常稳定 |
|---|---|---|---|---|---|
| 直接插入 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 冒泡（有提前结束标志） | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 简单选择 | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| 快速 | O(n log n) | O(n log n) | O(n²) | 平均 O(log n)，最坏 O(n) 栈 | 否 |
| 堆 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 |
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
补充选型：希尔排序通常不稳定，复杂度取决于增量序列，不能统一写成固定的 O(n log n)；计数排序要求关键字在大小为 k 的有限整数域内，时间、辅助空间均为 O(n+k)，常见稳定实现需要输出数组。基数排序按 d 位、每位 r 种取值且每趟分配稳定时，时间为 O(d(n+r))，辅助空间为 O(n+r)，不受比较排序下界直接约束。
补充样例 13：插入排序与稳定性反例
直接插入排序处理 [4,2,3,1]，三趟后依次为 [2,4,3,1]、[2,3,4,1]、[1,2,3,4]。对带身份标签的 [2甲,2乙,1]，简单选择排序第一趟把 1 与 2甲交换，得到 [1,2乙,2甲]，相等关键字相对次序改变，因此不稳定；插入排序仅移动严格大于待插入值的记录时可保持稳定。
索引与散列
索引以额外空间保存“关键字 → 记录位置”，减少定位成本，但会增加插入、删除、更新开销。稠密索引通常为每条记录或每个搜索键值建立索引项；稀疏索引只对部分搜索键值建项，通常要求数据按搜索键有序，以便定位后顺序扫描。分块查找要求块间有序、块内可无序，先查索引再查块内。
B 树结点可存放关键字及记录信息；B+ 树记录入口集中在叶层，内部结点主要作导航，叶结点通常按序相连，适合范围查询。二叉堆只保证父子堆序，不提供全局有序遍历或高效任意关键字检索。散列常用除留余数法等构造函数，以链地址法或开放定址法解决冲突；“不同关键字映射到同一地址”才是冲突，不等于关键字重复。
补充样例 14：分块索引查找
三块数据为 [3,1,5]、[9,6,8]、[14,11,12]，块内无序但前一块最大值小于后一块最小值。索引保存各块最大值 5,9,14 及块起始位置，查找 8 时找到首个不小于 8 的索引值 9，再扫描第二块 9、6、8，共 3 次块内比较；这里的 3 次不包含索引查找比较，不能只查到索引项就宣布找到记录。
补充样例 15：线性探测、查找长度与删除
表长 m=7，地址从 0 开始，h(k)=k mod 7，依次插入 10、17、24：初始地址都为 3，线性探测后分别放在 3、4、5，装填因子为 3/7。成功查找这三项的探测次数分别为 1、2、3，等概率成功平均查找长度为 (1+2+3)/3=2。查找 31 时依次探测 3、4、5、6，在从未使用的空槽 6 停止，共 4 次；删除 17 后槽 4 应保留删除标记，不能直接视为从未使用的空槽，否则会漏查槽 5 的 24。以上探测次数包含终止空槽，链地址法的比较计数口径则应另行说明。
II-2 应用与操作边界补缺
数组适合成绩表、矩阵等按编号读取的场景，访问前需检查下标；链表适合已定位结点附近频繁插删的场景，但不能免除定位成本。顺序表删除下标 i 的元素时，把后续元素依次左移，共移动 n−i−1 个元素（0 起始）；插入前要检查容量，删除前要检查非空及位置合法性。单链表删除尾结点仍需寻找前驱，不因持有尾指针就自动成为 O(1)。
字符串用于文本检索、标识符和日志处理；空串不同于含一个空格的串。定长存储要检查容量；采用 C 风格字符数组时，结束符 \0 占一个存储单元但不计入字符串逻辑长度，这不是所有字符串实现的共同规定。树适合表达目录、组织和语法的层次关系：逐个访问孩子即可递归处理子树；一般树的孩子数不限于两个，只有二叉树才直接使用左右孩子遍历规则。空树没有根，遍历时应直接返回。栈空时不得出栈，定容栈满时不得继续压入；循环队列的判满公式只适用于先前声明的指针及保留单元约定。
II-3 搜索的概念、分类与应用补缺
搜索（查找）是在数据集合中按给定条件定位元素或判定不存在；查找成功应返回记录、位置或约定标识，失败也要有明确返回约定。关键字不唯一时，返回任意一个、首个还是全部匹配必须另行规定。分类可以按不同维度进行，不能把它们当成互斥的同一张分类表：
- 按操作需求，静态查找表侧重查询，查找过程中不改变元素集合；动态查找表还需维护插入和删除。静态不等于必须顺序存储，动态也不等于必须链式存储。
- 按定位机制，顺序查找逐项比较，适合小规模或无序数据；二分查找利用有序性排除一半候选，适合更新少、可随机访问的有序数组；树查找逐层按关键字选择分支，平衡搜索树适合频繁更新并需有序查询的集合；散列查找先算地址再处理冲突，适合等值检索；索引查找先定位索引项再访问记录，适合大文件。各方法步骤和复杂度沿用样例 7～9、14～15，不另行重写。
- 若“搜索”指状态空间探索，DFS 沿分支深入并回溯，适合可达性、路径枚举；BFS 按距离层推进，适合无权图或所有边权相同的最少边数路径。二者不是关键字查找表的存储结构；带权图不能直接用普通 BFS 保证最小权值路径。
集合表示还需明确机制：有序表去重后存储元素，可用双指针同步扫描做并、交、差，两个表长度为 a、b 时为 O(a+b)；位图以元素编号为位下标，1 表示存在，位与、位或、与补运算分别实现交、并、差；哈希集合插入时先判断是否已存在。位图空间取决于整个编号域而非实际元素数，超大稀疏编号域不宜直接分配；求补集必须限定全集范围。
补充样例 16：搜索选型与重复关键字（答案解析）
题目：①固定有序编号表中反复按编号查询；②频繁增删并查询某编号区间；③只判断账号是否存在；④无权图求最少经过几条边。分别选什么？在 [2,4,4,4,7] 中找首个 4，普通二分命中就返回是否正确？
答案：①二分查找；②平衡搜索树，若是磁盘数据库索引则常用 B+ 树；③哈希集合；④BFS。原因分别是有序随机访问、有序动态维护、等值判定、按边数分层。普通二分可能命中下标 2，不能保证首个；找首个时记录命中位置并继续查左半区，最终应为下标 1。哈希不维持关键字顺序，不能仅靠一次哈希定位完成一般范围查询。
补充样例 17：位图表示与边界（答案解析）
全集 U={0,1,…,7}，位序按 b0,b1,…,b7 从左到右书写，A={1,3,6}、B={3,4,6}，则 A 位图为 01010010，B 为 00011010。逐位与得 00010010，对应交集 {3,6}；A 与 B 在 U 内补集的位图逐位与得 01000000，对应差集 {1}。这里左端是 b0，不是通常二进制数的最高有效位约定；使用机器按位取反时，要屏蔽 U 以外的位。
II-5 排序类型与方法机制补缺
内部排序指待排数据可整体放入内存；外部排序指数据量超过可用内存，需要分段生成有序归并段，再多路归并，主要关注外存 I/O 而非只统计关键字比较。按方法，可分为插入类（直接插入、希尔）、交换类（冒泡、快速）、选择类（简单选择、堆）、归并类和分配类（如基数）；计数、基数排序利用关键字取值结构，不是仅靠关键字比较的排序。稳定性及复杂度继续使用前表，只补尚缺的动作与使用边界：
| 方法 | 核心动作 | 场景与边界 |
|---|---|---|
| 冒泡 | 相邻逆序项交换，一趟把当前最大项送至末端 | 小规模或教学；一整趟无交换才可提前结束，相等项不交换以保稳定 |
| 快速 | 选枢轴并分区，再递归处理左右部分 | 常用于内存数组；一次分区不保证两侧各自有序，大量重复值可用三路分区缓解退化 |
| 堆 | 建最大堆，反复将堆顶与未排序区末项交换，缩小堆并下沉 | 需要最坏时间保证且辅助空间少；升序通常用最大堆，并非最小堆 |
| 归并 | 分治得到有序子序列，以双指针不断取较小项合并 | 稳定排序及外排序；相等时先取左段元素，数组实现需合并缓冲区 |
| 希尔 | 按增量把元素分组做插入排序，逐步缩小增量直至 1 | 借远距离移动减少逆序；最终增量必须为 1，不能承诺稳定 |
| 计数 | 统计频次、求累积次数、把记录分配到输出位置 | 整数域不大时适用；负数可减去最小值作偏移，值域过大浪费空间 |
| 基数（LSD） | 从最低位起逐位稳定分配并收集 | 固定位数整数或编码；需声明负数、变长键处理方式，每趟必须保留低位排序成果 |
直接插入与简单选择的动作已由样例 13 展示：前者维护有序前缀并插入，后者从未排序区选最小项与首项交换，不再另列重复过程。空序列或单元素序列无需交换；比较排序的 Ω(n log n) 最坏比较次数下界，针对一般输入、仅用关键字比较的模型，不否认插入排序在已排序输入上线性完成。
补充样例 18：一趟操作不等于排好序（答案解析）
对 [4,1,3,2] 升序排序：冒泡从左向右扫描一趟，依次得到 [1,4,3,2]→[1,3,4,2]→[1,3,2,4]；最大值 4 已就位，前缀尚未有序。快速排序若选末项 2 为枢轴，用从左向右把严格小于枢轴的项移到前部、最后交换枢轴的分区方式，一趟得 [1,2,3,4]，但这只是本例恰好整体有序，不是分区的普遍保证。归并排序首轮合并相邻单元素段得到 [1,4,2,3]，下一轮才合并为 [1,2,3,4]。
堆排序对此数组自底向上建最大堆得到 [4,2,3,1]；交换根与末项得到 [1,2,3,4]，仅在前三项中下沉后为 [3,2,1 | 4]。竖线右侧是已排序区，左侧仍是堆而非有序数组；建堆 O(n) 不代表完整堆排序也是 O(n)。
补充样例 19：非比较排序与稳定分配（答案解析）
计数排序处理 [2,0,2,1]，按键 0、1、2 的频次数组是 [1,1,2]，累积次数是 [1,2,4]。采用从右向左读取输入、先将相应累积次数减 1 再写入该下标的方式，输出 [0,1,2,2]；右侧的 2 先放到下标 3，左侧的 2 再放到下标 2，故相等记录的原先后关系保留。仅按频次重建整数值虽可排好数值，却不能据此证明附带记录的稳定性。
LSD 十进制基数排序处理 [21,13,12]：个位稳定排序得 [21,12,13]，十位稳定排序得 [12,13,21]；十位相同的 12、13 必须维持个位趟的先后次序。若把每个桶内记录任意倒置，就可能破坏结果。
II-5 索引与散列的剩余边界
已有稠密/稀疏索引、B/B+ 树区别、分块定位和线性探测样例，不重复重写。仅补两项机制：B+ 树内部按分隔键逐层选择子结点，先到叶层定位，再沿叶链扫描范围；插入可能造成结点分裂，删除可能借位或合并，以维护各叶同层及结点容量约束，不能理解为无需维护的静态目录。链地址法把同一桶的记录连接起来，只扫描目标桶并比较真实关键字；删除可直接摘除目标结点，不需要开放定址的删除标记。
补充样例 20：链地址与开放定址不能混用规则（答案解析）
仍取 m=7、h(k)=k mod 7，链地址按尾插方式加入 10、17、24，桶 3 为 10→17→24。查找 24 做 3 次关键字比较，删除 17 后为 10→24，仍能查到 24；查找不存在的 31 比较 10、24 共 2 次后到达链尾，这里不把空指针检测计作关键字比较。链地址装填因子可大于 1；开放定址每槽至多放一个有效记录，满表时插入可能失败，探测必须限制最多一轮以防死循环。散列期望常数时间还要求散列分布及负载控制合理，不能无条件承诺。