老魏日常

3.5 防漏网清单（第 3 篇综合）

2026-11-03 11:39:00上一篇 / 下一篇

本篇定位：数据结构与算法（线性结构 + 树与图 + 查找排序 + 算法分析）的篇末收口。本清单 = ①各章横向扩展高概率项汇总 ②跨模块漏网点 ③跨篇交叉点。用途：定稿前逐项核对覆盖度。 2027 命题预测（源自 01-真题/考点汇总/2027命题预测分析.md）：数据结构=栈/队列应用、二叉树、查找（折半/平均）、排序（冒泡/快排/堆排每趟定位）、复杂度——低位且逐年压缩，预计 1–2 题。

一、本篇高频必考速查（回顾，3.1–3.4 已详解）

章节必背锚点一句话
3.1 线性结构串是线性结构、栈底最先入栈、队列先进先出、单链表平均比较 (N+1)/2场景判定：先来先服务→队列
3.2 树与图满二叉树节点数 2^K−1、叶子 n0=n2+1、DFS 用栈 BFS 用队列2025 单48 唯一直接真题
3.3 查找排序折半 ⌈log₂(n+1)⌉ 次（顺序存储+有序）、每趟定位=冒泡/选择/快排/堆2023 单23 = 2024 多81 跨年重复
3.4 算法分析好算法四目标全选、复杂度=时间+空间、大 O 七阶排序2018 多80、2019 多83

二、防漏网清单（按新增概率排序，2027 可能补考）

标注：【高】= 2027 大概率补考，优先覆盖；【中】= 可能补考；【低】= 视大纲。

  1. 【高】栈的典型应用（3.1）：括号匹配、表达式求值（中缀→后缀）、函数调用栈、撤销/后退——"给场景选数据结构"是 9 年真题的固定考法（2025 单21 打印缓冲区=队列），栈应用是镜像补考点。
  2. 【高】二叉树性质计算（3.2）：第 k 层 2^(k−1) 个、深度 K 最多 2^K−1、叶子 n0=n2+1——2025 单48 的直接变体（"深度 5 满二叉树叶子数=16""n2=5 求叶子=6"）。
  3. 【高】折半查找次数变体（3.3）：已知 n 求失败/成功最多次数；已知最多次数反推 n 范围（⌈log₂(n+1)⌉=k → 2^(k−1) < n+1 ≤ 2^k）——2019 单59、2024 单28 同族。
  4. 【高】排序稳定性辨析（3.3）：稳定=冒泡/插入/归并/基数；不稳定=选择/快排/堆/希尔——2023/2024 考"每趟定位"，稳定性是同一知识族最可能的补考方向。
  5. 【高】复杂度阶排序（3.4）：O(1)<O(log n)<O(n)<O(n log n)<O(n²)<O(2^n)——"由小到大排列"概念题，2027 预测点名复杂度。
  6. 【高】折半查找的前提条件（3.3）：顺序存储 + 有序；链表不能折半——"以下哪种结构不能折半查找"类判断题。
  7. 【中】二叉排序树（BST）（3.2/3.3）：左小右大、中序递增、查找平均 O(log n) 最坏 O(n)（退化链）——计算机基础常客。
  8. 【中】哈夫曼树与编码（3.2）：WPL 最小、频率高编码短——送分计算/概念题。
  9. 【中】完全二叉树编号（3.2）：节点 i 左孩子 2i、右孩子 2i+1、双亲 ⌊i/2⌋——堆排序的数组实现底层。
  10. 【中】图的基本概念（3.2）：有向/无向、入度出度、度之和=2×边数、连通分量、生成树（n 顶点 n−1 边）——9 年未考，大纲要求（图），防漏网。
  11. 【中】图的遍历（3.2）：DFS（栈/递归）vs BFS（队列）——与 3.1 栈队列特性呼应。
  12. 【中】哈希查找（3.3）：散列函数（除留余数法）、冲突处理（开放定址/链地址）——"哈希表平均查找 O(1)"概念题，与数据库索引（4.6）衔接。
  13. 【中】设计策略匹配（3.4）：折半/归并/快排=分治；Dijkstra/Prim/Kruskal/哈夫曼=贪心；Floyd/背包/LCS=动态规划——匹配题。
  14. 【中】递归 vs 迭代（3.4）：递归用系统栈（空间 O(深度)）、"递归一定比迭代高效"是错误说法。
  15. 【低】循环队列判空判满（3.1）：front==rear 判空、(rear+1)%maxsize==front 判满——顺序队列的经典细节。
  16. 【低】拓扑排序（3.2）：AOV 网、只适用于有向无环图（DAG）——课程先修关系场景。
  17. 【低】最小生成树/最短路径算法对应（3.2）：Prim=加点、Kruskal=加边、Dijkstra=单源最短路、Floyd=任意两点。
  18. 【低】串的模式匹配（KMP）（3.1）：KMP 是串匹配算法、时间 O(n+m)——名词辨析。

三、跨篇交叉点（写书时互引）

  1. 线性结构 × 操作系统：就绪队列/消息队列（2.2 进程调度）= 队列的典型应用；调用栈（2.4 递归）= 栈的应用——3.1 章可直接引用。
  2. 线性结构 × 网络：报文/分组排队（5.6 传输层）用队列；路由器转发表（5.4 路由）用哈希/查找表。
  3. 查找 × 数据库：折半查找/哈希 → 数据库索引原理（4.6 索引，B+ 树）；"重复值超 80% 不适合建索引"（2026 单33）与哈希冲突思想同源。
  4. 排序 × 数据库：归并排序 → 外部排序/多路归并（数据库排序）；堆 → 优先队列（SQL ORDER BY 底层）。
  5. 树 × 金融科技：决策树（8.3 机器学习，2026 单25）本质就是二叉树/多叉树的分类结构——"决策树是分类模型"与二叉树概念呼应。
  6. 复杂度 × 软件工程：算法复杂度（3.4）↔ 软件测试性能测试（6.7）、算法设计是详细设计任务（2019 多86"算法设计属详细设计"）——两处互引，避免重复展开。
  7. 图 × 网络：最短路径（Dijkstra）↔ 路由协议（5.4 OSPF 就是链路状态最短路径）；拓扑排序 ↔ 网络拓扑。
  8. 栈/队列 × 信息安全：缓冲区溢出（7.4 网络攻击）的底层就是栈（函数调用栈溢出）——C 语言与栈结构直接关联。

四、本篇写作状态自检

  • 3.1 线性结构（线性表/栈/队列/串 + 2019 单38、2019 多84、2022 单24、2025 单21、2025 单49）
  • 3.2 树与图（二叉树性质/遍历/BST/哈夫曼 + 图的概念/存储/遍历/经典算法 + 2025 单48）
  • 3.3 查找与排序（顺序/折半 + 八大排序三张表 + 2019 单59、2023 单23、2024 单27/28/多81）
  • 3.4 算法设计与复杂度分析（五特征/四目标/复杂度/设计策略 + 2018 多80、2019 多83）
  • 3.5 防漏网清单（18 条按概率排序 + 跨篇交叉 8 条）
  • 附录 A 考点×年份矩阵（第 3 篇部分，已完成）
  • 待办：2021 单40（流程逻辑题，if(i>j||m<k--)）实为 C 语言流程控制，归 2.4 程序设计，不属第 3 篇——总纲统计口径已核对
  • 待办：2026 年考点汇总把单45（CSMA/CD，网络考点）误归入"数据结构与算法"标题下——已在 3.1 章定位表注明"2026 年无独立数据结构题"，总纲权重表口径同步