企业官网建设流程全解析

数据结构期末复习，如果只能好好看一章，我大概率会选“查找”。原因很现实：在多数学校的《数据结构》期末考试里，第九章几乎稳定产出一道算法大题，而且这章题型高度套路化——ASL计算、判定树、哈希表构造，练熟三套流程就能稳稳拿分。我当年复习时，图、排序看得头晕眼花，唯独第九章靠一套系统整理直接上手，考场上看到哈希表大题心里是稳的。这篇文章就把这套整理完整分享出来，适合正在期末冲刺的同学，也适合考研初试快速回查。

1. 先建坐标系：第九章查找的核心脉络

1.1 查找的体系位置和两个基本分类

查找这一章，本质上回答一个问题：在一堆记录里，怎么快速找到关键字匹配的那一条。放在整个数据结构课程里，它和排序并称“两大算法应用题源泉”，但查找比排序更友好——涉及的操作种类少，主要就是插入、删除、查找三种，绕来绕去都是同一套思路。

先理清几个概念。查找表是记录的集合，关键字是用来区分记录的字段。按操作范围分，只查不改的叫静态查找，边查边插入删除的叫动态查找；按存储位置分，内存里的叫内查找，外存上的叫外查找。这个分类的意义不是背诵，而是决定查找方法的适用场景。折半查找要求有序顺序表，典型静态查找；二叉排序树和哈希表天然支持动态操作；B树则是奔着减少磁盘IO设计的。考试选择题常考“哪种结构适合动态查找”，记住这条对应关系就够。

还有一个容易被忽略的点：查找算法的优劣和数据的物理存储密切挂钩。顺序表能用下标随机访问，链表只能顺序访问，散列表需要连续内存配合哈希函数定位。“存储结构决定查找策略”这个观念，是分析全章所有方法的钥匙。

1.2 平均查找长度：全章唯一的度量衡

全章所有计算题的落点，几乎都是平均查找长度，简称ASL。定义式是：

ASL = Σ(Pi × Ci)

Pi是查找第i个记录的概率，Ci是找到它所需的比较次数。期末考试默认等概率，所以Pi=1/n。但要注意，ASL必须区分“查找成功”和“查找失败”两个口径，二者的比较次数统计方式不同，分母也不同。

成功时的ASL，是所有记录的比较次数加起来除以记录数；失败时的ASL，是对所有可能的失败位置（外部结点或哈希地址）统计比较次数后，除以失败位置的总数。这个“分母不同”是九九成的人丢分的地方——我后面每个例题都会把成功和失败分开算一遍。你先把ASL的概念吃透，再看具体方法，会发现所有知识点都长在同一根茎上。

2. 线性表上的查找：基础题型的分水岭

2.1 顺序查找：别觉得简单，监视哨是隐藏考点

顺序查找的思想就是从头到尾逐个比较，最简单的查找方式。它最大的优势是不挑存储结构，顺序表、链表都能用，也不需要数据有序；最大的劣势是慢，平均要查一半才找到。

很多同学觉得这有什么好复习的，但其实有个考点叫“监视哨”。做法是把待查找的关键字先存到a[0]位置，然后从a[n]开始往a[0]方向比较。好处是每个循环只需要判断“当前元素是否等于key”，不需要判断“下标是否越界”，数据量大时能减少近一半的判断开销。这个技巧在很多公司面试里也会被问到。

比较次数上，等概率查找成功时ASL=(n+1)/2；查找失败时，如果带监视哨，比较n+1次后碰到哨兵终止，失败ASL=n+1；如果不带哨兵，就是n次。不同教材对失败口径略有差异，做题前先看看自己教材怎么定义。

2.2 折半查找：判定树是考场必画的东西

折半查找的前提有两个，缺一不可：数据有序，且能随机访问——说白了就是有序顺序表。算法逻辑不难：low和high框定区间，mid=(low+high)/2，拿key和mid位置的元素比较，相等就命中，小于就去左半区间，大于就去右半区间。为什么链表不行？因为每次取mid都要从链表头走到中间，一次“跳到中间”的成本是O(n)，折半的意义直接报废。

考试的重点是画判定树。以n=11的有序表为例，第一次mid=6，根结点是第6个元素；左区间1~5的mid=3，作为左孩子；右区间7~11的mid=9，作为右孩子。继续对每个子区间重复，最终得到一棵平衡二叉树。查找某个元素的比较次数就是从根到该结点经过的结点数，最坏情况下不会超过⌊log₂n⌋+1。

画判定树时有一个细节：mid的取整方向要按教材来。有的教材mid=⌊(low+high)/2⌋，有的用向上取整，取整方向不同，树的形态会有细微差别，但高度和ASL基本一致。考试时如果没特别说明，就按你们教材约定来，千万别混用。

2.3 分块查找：块间快、块内慢的折中方案

分块查找又叫索引顺序查找，是顺序查找和折半查找的折中。核心思想是把数据分成若干块，块与块之间有序——前一块的最大值小于后一块的最小值——但块内可以乱序。做法是先建一个索引表，存每块的最大值和起始位置，查找时先查索引表确定块，再在块内顺序查找。

它的ASL = 索引查找的ASL + 块内顺序查找的ASL。如果把n个元素均匀分成b块、每块s个元素：索引表顺序查找时，ASL=(b+1)/2+(s+1)/2；索引表折半查找时，ASL≈log₂(b+1)-1+(s+1)/2。通过调整块大小，可以得到比纯顺序查找更优的性能。

这里容易踩的坑是：块内不能用折半查找。因为块内无序，只能从头顺序比较。还有，索引表本身必须有序，否则“确定块”这一步就无从谈起。

3. 树表查找：从BST到B树的考点连续剧

3.1 二叉排序树：插入容易，删除才是分水岭

二叉排序树（BST）是动态查找的典型代表。它的性质一句话总结：左子树所有结点小于根，右子树所有结点大于根，对树做中序遍历得到递增序列。插入好理解，从根出发，小于往左、大于往右，走到空位就挂上去。

真正的难点是删除。分三种情况：叶子结点直接删；只有一个孩子，让孩子顶上来；有两个孩子，不能直接删，要用中序前驱或中序后继的“值”替换当前结点，然后把那个前驱或后继删掉。为什么必须这样？因为如果直接把一个有两个孩子的结点摘掉，左右两棵子树会断开，很难重新接成合法BST。而前驱是左子树最右下的结点、后继是右子树最左下的结点，它们最多只有一个孩子，删起来只涉及简单替换。

还有一个反复考的点：BST的ASL不固定，依赖插入序列的顺序。同样是{1,2,3,4,5}这五个数，按递增序列插入就是一条链，ASL成功=3；按{3,1,5,2,4}插入，树形相对平衡，ASL会低很多。所以题目给你一个序列时，必须先画出树，再用树统计比较次数，不能直接套log公式。

3.2 平衡二叉树：四类旋转的识别口诀

BST最怕退化成链，于是有了平衡二叉树（AVL）。AVL要求每个结点的左右子树高度差绝对值不超过1，这个差值就是平衡因子。一旦插入后某结点平衡因子变成2或-2，就必须旋转调整。

旋转有四种：LL型右旋、RR型左旋、LR型先左旋后右旋、RL型先右旋后左旋。记法就是看“插入位置相对于最小不平衡子树根的方向”：插入在根的左孩子的左子树，就是LL；根的右孩子的右子树，就是RR；根的左孩子的右子树，就是LR；根的右孩子的左子树，就是RL。口诀：LL右旋，RR左旋，LR先左后右，RL先右后左。

我当年常犯的错是只记得旋转方向，却忘了旋转后需要“过继”子树。LL型右旋时，原左孩子的右子树要挂到新根的左子树上；RR型左旋时，原右孩子的左子树要挂到新根的右子树上。这一笔漏画，后面分析全崩。建议做题时把每个结点高度写在旁边，先找最小不平衡子树，再判断类型，最后动笔画旋转。

3.3 B树与B+树：概念题之外，最常考高度计算

B树是多路平衡查找树，专门为磁盘等外存设计。一棵m阶B树要满足：根结点至少1个关键字，至多m-1个；非根结点关键字数在⌈m/2⌉-1到m-1之间；所有叶子结点在同一层。插入时结点满就分裂，把中间的关键字提上去；删除时关键字太少就合并或借关键字。

B+树和B树的区别也要理清：B+树的内部结点只存索引，不存实际记录，所有记录都挂在叶子结点上，叶子结点之间用链表相连。好处是范围查询特别方便，找到下界后沿链表一路往后扫就行。考试选择判断爱考“哪个支持范围查找更高效”，答案是B+树。

高度计算是B树相对有区分度的考点。含n个关键字的m阶B树，高度h满足：最小高度时假设每个结点都塞满m-1个关键字，n≤m^h-1，所以h≥log_m(n+1)；最大高度时假设根只有1个关键字、其他结点都只有⌈m/2⌉-1个关键字，用等比数列求和推出上界。遇到具体题目，列不等式解整数层数即可，关键是不要漏算根这一层。

4. 散列表查找：期末大题的稳定出题区

4.1 哈希函数和装填因子：一切都是概率问题

散列表（哈希表）的思路是直接通过关键字计算存储位置，理想情况下查找时间复杂度O(1)。最常用的哈希函数是除留余数法：H(key)=key%p，其中p通常取不大于表长m的最大质数。为什么取质数？因为能减少关键字序列中周期性对余数分布的影响。如果表长是16，用key%16，所有低位相同的关键字必然冲突；取质数13，等于把低位信息打散，冲突更均匀。

装填因子α=n/m，是记录数与表长的比值。α越大表越“挤”，冲突概率越高，ASL越大；α越小越浪费空间，但查找更快。散列表的ASL不是固定的常数，它和α强相关，这也是后面计算ASL的底层逻辑。注意，散列表一旦α接近1，线性探测会出现严重的“堆积”，后面冲突的元素聚成一片，插一个元素可能要探测很久。

4.2 线性探测与链地址法：两种冲突处理的对比

冲突无法避免，只能处理。最常用两种：开放定址法中的线性探测，以及链地址法。

线性探测的公式是Hi=(H(key)+i)%m，i从0开始，位置被占就继续往后找，直到找到空位。实现简单，缺点是容易堆积——一个冲突会让后续连续区域越长越挤。二次探测Hi=(H(key)±i²)%m可以缓解堆积，但要求表长配合，考场极少出现。

链地址法最直观：每个桶对应一条链表，冲突元素挂到同一条链表上。查找时先定位桶，再沿链表顺序找。它的好处是α可以大于1也不会“满”，删除也方便，但要额外的指针空间。考试最多的是“给定序列，分别用线性探测和链地址法构造散列表，并计算ASL”。这种题要求你两步走：先画表，再数比较次数。

4.3 ASL成功与失败：同一个表，两种口径

散列表的ASL是期末大题的压轴戏，也是最容易算错的地方。先说口径：

成功ASL = 每个关键字插入时探测的次数之和 / n。

失败ASL = 对每个可能的哈希地址，从该地址开始探测直到第一个空位的比较次数之和 / m，注意除以的是表长m，不是关键字数n。

为什么失败要除以m？因为查找失败时，key经过哈希函数可能落在任何一个地址上，探测也从那个地址开始，所以分母是全部地址数。很多人在考场上顺手除以n，丢掉的10分就是这么丢的。

链地址法的失败ASL更简单：每个桶链表长度的总和除以m，数值上就是装填因子α。但注意，“比较到空指针算不算一次”有些教材有争议，做题先看教材约定。为了避免歧义，考试时如果题目只给了序列和表长，没特别说明比较规则，就按你们课堂讲的口径来。

5. 三道典型大题，手把手走一遍完整流程

5.1 折半查找判定树：从建树到统计比较次数

例题：有序表{3,8,15,21,33,45,52,67,71,86,90}，n=11，画出折半查找判定树，并计算查找不存在的元素10需要比较几次。

过程：第一次mid=⌊(1+11)/2⌋=6，根是45；左区间1~5，mid=3，根是15；右区间7~11，mid=9，根是71。继续递归：3的左区间1~2中mid=1，根3；3的右区间4~5中mid=4，根21，其右孩子是33；71的左区间7~8中mid=7，根52，其右孩子是67；71的右区间10~11中mid=10，根86，其右孩子是90。

判定树画出来，树高4层。查找10时：10小于45，走左；10小于15，走左；10大于3，走右；下一个是8，10大于8，还想往右，但8的右子树为空，此时low>high，判定失败，一共比较4次。这类题只要判定树画对，数次数就是数路径长度。

5.2 散列表构造与ASL：把计算过程写成分步式

例题：关键字序列{15,23,34,56,78,12}，表长m=11，哈希函数H(key)=key%11，用线性探测法构造散列表，并计算ASL成功和ASL失败。
仿真推演：

• 15%11=4，下标4空，放入，比较1次。
• 23%11=1，下标1空，放入，比较1次。
• 34%11=1，下标1冲突，探测下标2，空，放入，比较2次。
• 56%11=1，下标1冲突，下标2冲突，下标3空，放入，比较3次。
• 78%11=1，下标1冲突，下标2冲突，下标3冲突，下标4已有15，下标5空，放入，比较5次。
• 12%11=1，下标1到5全被占，下标6空，放入，比较6次。

最终表：下标1=23，2=34，3=56，4=15，5=78，6=12，其余空。
成功ASL=(1+1+2+3+5+6)/6=18/6=3。

失败ASL要对地址0~10逐个统计：地址0探测1次到空位；地址1要一直探测到下标7才遇到空位，共7次；地址2共6次；地址3共5次；地址4共4次；地址5共3次；地址6共2次；地址7、8、9、10各1次。总和1+7+6+5+4+3+2+1+1+1+1=32，失败ASL=32/11≈2.91。

同一题如果用链地址法：地址1链表为23→34→56→78→12，地址4链表为15。
成功ASL=(1+2+3+4+5+1)/6=16/6≈2.67。
失败ASL=所有链表总长除以11=(5+1)/11≈0.55。如果教材把“比较到空指针”也算一次，每个桶额外加1，结果是17/11≈1.55，建议提前确认教材口径。

5.3 BST的成败ASL：外部结点的比较次数怎么数

例题：按序列{45,24,53,12,37,93}构建二叉排序树，计算ASL成功和ASL失败。
插入过程：45作根；24入左；53入右；12入24的左；37入24的右；93入53的右。树形如下：45在第1层，24和53在第2层，12、37、93在第3层。
成功ASL=(1+2+2+3+3+3)/6=14/6≈2.33。

失败ASL要用外部结点区间法。n=6，失败位置共7个区间，每个区间对应一个空指针，比较次数等于从根到该空指针父结点的路径结点数：x<12是3次；12<x<24是3次；24<x<37是3次；37<x<45是3次；45<x<53是2次；53<x<93是3次；x>93是3次。
失败ASL=(3+3+3+3+2+3+3)/7=20/7≈2.86。

这个区间法比直接数空指针靠谱，不容易漏。难点是每个空指针代表的是哪个数值区间，只要按中序序列划分成n+1个区间，就不会错。

6. 考前必看的易错清单与冲刺计划

6.1 十处高频翻车点，踩过一半以上要警惕

每一条都是真实考场里的血泪。建议把这些写成便签贴在题本封面，做题前扫一遍，相当于打了一针免疫。

6.2 三天冲刺安排：从查漏补缺到限时模拟

如果你还有72小时，按下面这个节奏走：

第1天，主攻线性查找和折半查找。把判定树画法练到条件反射，至少画10棵，包括奇数和偶数个元素两种情况，然后做5道ASL计算题。这天不需要碰哈希表和B树。

第2天，主攻BST、AVL和B树。BST的删除多练双孩子替换，AVL的四类旋转各做两道完整过程题，B树把定义性质和高度计算公式背熟，做一道插入分裂题。这天是体量最大的一天，建议用整块时间集中刷。

第3天，全力练散列表大题。哈希函数、线性探测、链地址法三件套各做两题，尤其把成功和失败ASL的两种分母练到脱口而出，然后找一套往年期末卷或配套习题集，限时60分钟做完整一章的题量，模拟考场节奏。

我自己的经验是：第九章最忌“看懂了概念”就合上书。ASL是算出来的，判定树是画出来的，散列表是亲手构造出来的，不是看会的。每次复习都要求自己盖住答案，在纸上完整推一遍流程，练到看到“除留余数法+线性探测”就能直接写出探测序列。这个技能练到位，期末考试这一章的分数基本就到手了。你要是考前三天从头按这个节奏走一遍，大概率比我当年还要稳。