第 7 章 查找
【考纲内容】
1.查找的基本概念；2. 顺序查找法；3. 分块查找法；4. 折半查找法；
5.树型查找：二叉搜索树，平衡二叉树，红黑树；6. B 树的基本概念及其基本操作；
7.B + 树的基本概念；8. 散列 (Hash) 表；9. 字符串模式匹配；10. 查找算法的分析及应用
【考情统计】
年份
题数及分值
考点
单选题
综合题
总分值
2009
2
0
4
平衡二叉树定义及性质、B 树与 B + 树
2010
2
1
14
折半查找法、平衡二叉树插入操作、散列表
2011
2
0
4
二叉搜索树查找操作、散列表
2012
2
0
4
平衡二叉树定义及性质、B 树与 B + 树
2013
3
1
16
顺序查找法、二叉搜索树查找操作、平衡二叉树插入操作、B 树与 B + 树
2014
2
0
4
B 树与 B + 树、散列表
2015
3
0
6
折半查找法、平衡二叉树定义及性质、KMP 算法
2016
1
0
2
B 树与 B + 树
2017
2
0
4
折半查找法、B 树与 B + 树
2018
3
0
6
二叉搜索树定义及性质、B 树与 B + 树、散列表
2019
3
0
6
平衡二叉树插入与删除操作、散列表、KMP 算法
2020
2
0
4
二叉搜索树插入与构造、B 树与 B + 树
2021
2
0
4
平衡二叉树插入操作、B 树与 B + 树
2022
2
1
17
B 树与 B + 树、散列表、二叉搜索树
2023
3
0
6
B 树与 B + 树、折半查找、散列表
2024
3
1
16
折半查找、KMP、二叉搜索树、散列表
【考点解读】
本章内容在 408 考试中主要以选择题的形式出现。考生需熟悉各种查找算法的过程和性质，掌握各种查找表在查找成功和查找失败情况下的平均查找长度的计算。树型查找这一小节是本章最为高频的考点，考生需理解各种树型查找表以及它们之间的区别。此外，要熟练掌握散列表的思想，这与其他查找算法的思想有本质上的区别，在考试中的考查次数也较多。红黑树为新增考点，虽然没有出现过，但是红黑树理解难度较大，出题角度多样，考生需充分准备，红黑树的知识点可以与其他知识点来进行对照考查，学习过程中应多注意它们之间的差异。字符串模式匹配算法在真题中出现了多次，以 KMP 匹配内容为主，考生应该着重理解 KMP 算法思想，其代码实现了解即可。本章考查的方式比较固定，题目相对来说比较简单。【复习建议】
学习本章时应注重动手模拟算法执行过程，在复习过程中注意以下几点：1.熟练掌握各种查找算法在查找成功与查找失败情况下的平均查找长度。
2.区分直接查找法与折半查找法，熟练掌握折半查找判定树的构造过程。
3.掌握各种搜索树的定义以及特点，注重二叉搜索树、平衡二叉树、红黑树三者对比学习。
4.熟练掌握 B 树与 B + 树的特点及其两者之间的区别，该考点的考查较为频繁。
5.熟练掌握各种搜索树的增删改查操作，真题中多次考查插入和删除操作过程，增删改查等操作是该章节的重点。
6.熟练掌握散列表的各个概念、散列表的构造过程以及散列表的查找过程。
7.在字符串模式匹配算法中，重点是学会计算模式串的 next 数组和 nextval 数组，并能够描述 KMP 算法的实现过程。
7.1 查找的基本概念
7.2 顺序查找、折半查找与分块查找
7.2.1 顺序查找
7.2.2 折半查找
7.2.3 分块查找
7.2.4 习题精编
7.2.5 真题演练
7.3 二叉搜索树、平衡二叉树
7.3.1 二叉搜索树（BST）
7.3.2 平衡二叉树（AVL）
7.3.3 平衡二叉树手工快速调整方法
7.3.4习题精编
7.3.5真题演练
7.4 B、B+树基础、红黑树
7.4.1 B树的基本概念
7.4.2 B树的基本操作
7.4.3 B+树的基本概念
7.4.4 红黑树
7.4.5 红黑树与4阶B树的等价
7.4.6 习题精编
7.4.7 真题演练
7.5 散列表
7.5.1 散列表的基本概念
7.5.2 散列函数的构造方法
7.5.3 处理冲突的方法
7.5.4 散列表的查找
7.5.5 习题精编
7.5.6 真题演练
7.6字符串模式匹配
7.6.1 基本概念
// 函数定义：计算模式串 P 的 nextval 数组，nextval 数组用于优化 KMP 算法的匹配过程 // SqString P：模式串，存储要匹配的字符串内容；int nextval[]：用于存放计算出的 nextval 值 void GetNextval(SqString P, int nextval[]) { // 计算 nextval 值（函数功能说明，方便阅读） // i：用于遍历模式串 P 的下标，初始从 0 开始 int i = 0; // j：辅助计算的下标，初始为 -1，后续用于对比字符、推导 nextval 值 int j = -1; // 初始化 nextval 数组的第 0 个元素为 -1，是 KMP 算法优化 nextval 数组的常见起始设定 nextval[0] = -1; // 循环条件：i 小于模式串 P 的长度时，持续计算 nextval 数组后续元素 while (i < P.length) { // 分支条件：j 为 -1（说明到匹配边界或刚回溯完），或者当前 P[i] 和 P[j] 字符相等 if (j == -1 || P[i] == P[j]) { // i 和 j 都向后移动一位，继续对比后续字符 ++i; ++j; // 如果移动后，当前 P[i] 和 P[j] 字符不相等，说明找到当前位置 i 对应的 nextval 值为 j if (P[i] != P[j]) nextval[i] = j; else // 如果 P[i] 和 P[j] 相等，为避免冗余匹配，当前 i 位置的 nextval 值直接继承 j 位置的 nextval 值 nextval[i] = nextval[j]; } else { // 若 P[i] 和 P[j] 不相等，j 回溯到 nextval[j] 位置，重新尝试匹配 j = nextval[j]; } } }简单总结下逻辑：
通过i遍历模式串，j辅助找 “最长相等前后缀”，遇到字符相等时推进下标，遇到不等时用nextval回溯j，同时通过对比P[i]和P[j]，决定nextval[i]是直接赋j还是继承nextval[j]，最终得到优化后的nextval数组，让 KMP 匹配更高效 。7.6.4 习题精编
7.6.5 真题演练
7.7 本章总结
