7.1-7.2考研408数据结构查找算法核心知识点深度解析
考研408数据结构查找算法核心知识点深度解析
一、查找基本概念
1.1 核心定义与易错点
-
查找表与关键字
- 易错点：混淆静态查找表（仅查询）与动态查找表（含插入/删除操作）的应用场景。例如哈希表属于动态查找结构，而分块查找适用于静态数据。
- 难点：理解平均查找长度（ASL）的计算公式：
[
ASL = \sum_{i=1}^{n} P_i \times C_i
]
其中 (P_i) 为查找概率，(C_i) 为比较次数。考生常忽略概率不等的情况，错误假设等概率条件。
-
判定树与查找效率
- 易错点：误将折半查找判定树视为完全二叉树。实际上，当元素个数 (n) 不是 (2^k-1) 时，判定树中存在非满结点层。
二、顺序查找
2.1 算法实现与优化