数据结构1800道考研真题（数据结构1800题）｜权威真题库·深度解析·高效备考

叉树遍历与构造

三种遍历的递归/非递归实现：
• 前序：根→左→右
• 中序：左→根→右
• 后序：左→右→根

真题高频考点：
① 已知中序+前序/后序 → 构造二叉树
② 由后序序列判断中序遍历序列是否可能
③ 线索二叉树的线索化与遍历

特殊二叉树性质：
• 完全二叉树：n个节点高度为⌊log₂n⌋+1
• 满二叉树：第k层有2ᵏ⁻¹个节点
• 平衡二叉树：|hl-hr|≤1 且左右子树均平衡

树的存储与应用

树的存储结构对比：
• 双亲表示法：适合求结点双亲
• 孩子表示法：适合求结点孩子
• 孩子兄弟表示法：将树转为二叉树（左孩子右兄弟）

真题高频应用：
① 文件系统目录树（路径解析）
② 表达式树（中缀→表达式树→求值）
③ 哈夫曼树（最优编码，WPL最小）

图的存储与遍历

邻接矩阵 vs 邻接表：
• 稠密图（边数≈n²）→ 邻接矩阵
• 稀疏图（边数≪n²）→ 邻接表

遍历算法：
• DFS：递归/栈实现，适合路径存在性判断
• BFS：队列实现，适合最短路径（无权图）

最小生成树与最短路径

Prim vs Kruskal：
• Prim：适合稠密图，时间O(E log V)
• Kruskal：适合稀疏图，时间O(E log E)，用并查集检测环

Dijkstra vs Floyd：
• Dijkstra：单源最短路径，非负权图，O(V²)或O(E log V)
• Floyd：所有顶点对最短路径，O(V³)，可处理负权边（但无负环）

真题高频变种：
• 带路径记录的最短路径（如输出路径上的关键节点）
• 次短路径（在Dijkstra中维护dist1与dist2）
• 有向图中的关键路径（AOE网，最长路径）

排序算法深度对比

时间复杂度与稳定性对比：
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 | 适用场景 | |
|
|
|
|
|
|
| | 冒泡 | 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 log n) | O(n) | ✓ | 大规模/稳定 | | 快排 | O(n log n) | O(n log n) | O(n²) | O(log n) | ✗ | 大规模/平均快 | | 堆排 | O(n log n) | O(n log n) | O(n log n) | O(1) | ✗ | 大规模/空间敏感 |

真题高频陷阱：
• 快排最坏情况（已排序输入）→ 改用三数取中
• 归并排序需额外O(n)空间
• 堆排建堆时间O(n)，而非O(n log n)

查找算法核心

二分查找变体：
• 基础版：查找等于key的元素
• 左边界：查找第一个≥key的位置
• 右边界：查找最后一个≤key的位置
• 循环数组：如[4,5,6,7,0,1,2]中找最小值

哈希表设计要点：
• 负载因子α = n/m（n为元素数，m为桶数）
• 冲突解决：开放定址（线性/平方/双散列）、链地址法
• 真题高频：LRU缓存（哈希+双向链表）、字符串哈希

B树/B+树特性

B树定义（阶数为m）：
• 根：2≤子树数≤m
• 非根：⌈m/2⌉≤子树数≤m
• 关键字数 = 子树数
- 1
• 所有叶子在同一层

B+树 vs B树：
• B+树非叶子节点不存数据，仅作索引
• 所有数据在叶子节点，且叶子链表连接
• 适合数据库索引（减少I/O，顺序访问快）

AVL树旋转

四种旋转：
• LL型：右旋
• RR型：左旋
• LR型：先左旋子树，再右旋
• RL型：先右旋子树，再左旋

平衡因子：bf = hl
- hr ∈ {-1, 0, 1}
真题高频：在AVL树中插入/删除后，判断失衡类型并进行旋转调整。