考点拆分 04 · 树 · 图 · 串 · 查找 · 算法（约 35 分）
来源：2024 回忆版
系统笔记：2.1 数据结构基本概念 2.4 串、数组和广义表 2.5 树和二叉树 2.6 图 2.7 查找 2.9 算法基本概念与分析
必背清单
- [ ] 逻辑结构：线性 / 非线性
- [ ] 二叉树第 k 层最多 (2^{k-1}) 结点（根为第 1 层）
- [ ] 有向图出度/入度；ΣOD=ΣID=边数
- [ ] n 顶点连通图最少 n−1 条边（树）
- [ ] 折半查找前提：有序 + 顺序存储
- [ ] 广义表长度 = 第一层 元素个数
- [ ] 算法必有时间/空间复杂度；二者不必然反比
- [ ] ADT / 数据项定义（简答）
2024 真题回放
| 位置 | 答案 | 考点 |
|---|---|---|
| 单选 10 | D | 算法有时间复杂度 |
| 单选 13 | B 3 次 | 折半查找过程 |
| 单选 15 | C | 逻辑：线性/非线性 |
| 单选 19 | B 4 | 第 3 层最多 4 |
| 填空 4 | 3 | 广义表长度 |
| 填空 5 | 8 | 9 点连通最少边 |
| 判断 9 | × | 时空不必然反比 |
| 简答 1 | — | 数据项 + ADT |
| 简答 4 | — | 有向图·出度入度 |
简答模板
ADT
抽象数据类型 = 数学模型 + 操作集。
特征：抽象性、封装性。ADT = (D, S, P)。
有向图
边为有序对 <v,w>。
出度：从 v 出发弧数；入度：指向 v 的弧数。
折半手推
{12,18,21,35,45,55,66} 找 21：
- mid=35 → 左
- mid=18 → 右
- mid=21 → 中 · 3 次
同型自测
- 满二叉树 4 层共多少结点？
- 5 顶点连通图最少/最多边？
- 广义表
L=((a,b),c)长度？深度？
答案
- (2^4-1=15)
- 最少 4，最多 (C(5,2)=10)（无向简单图）
- 长度 2，深度 2
返回：_索引 · 全卷