知识点

1.基本概念

静态查找表：只做查找表是否存在某元素，从查找表中检索某特定元素的属性操作的称为静态查找表

动态查找表：在查找表中插入一个元素，在查找表中删除一个元素操作的称为动态查找表

为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度

2.线性表查找

2.1、顺序查找

顺序查找（Sequential Search）的查找过程为：从表的一端开始，依次将记录的关键字和给
定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若查找整个表后，仍
未找到关键字和给定值相等的记录，则查找失败。（简而言之就是从左往右依次比较）

时间复杂度为：O(n)

• 优点：对数据元素的存储没有要求，顺序存储或链式存储皆可，数据元素也不一定必须有序
• 缺点：当n较大时，平均查找长度较大，效率低

2.2、折半查找

折半查找（Binary Search）也称二分查找，它是一种效率较高的查找方法。但是，折半查
找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

基本思想：key 值与中间元素比较，相等则成功；key 大则比较右半边；key 小则比较左半边分别用low和high来表示当前查找区间的下界和 上界，mid为区间的中间位置

---

把当前查找区间的中间位置作为根，把左子表和右子表分别作为根的左子树和右子树，由此得到的二叉树称为折半查找的决策树。

具有n个节点的决策树的深度(h)为：log₂n + 1
ASL_成功：最多：h；最少：1
ASL_失败：最多：h；最少：h-1

时间复杂度为：O(log₂n)

2.3、分块查找

分块查找（Blocking Search）又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的查找方法。

如果线性表既经常动态变化，又需对其进行快速查找，则可采用分块查找。
其缺点是：要增加一个索引表的存储空间并对初始索引表进行排序运算。

总结

3.树表查找

3.1　二叉排序树

二叉排序树（Binary Sort Tree）又称二叉查找树，它是一种对排序和查找都很有用的特殊二
叉树。

定义/条件：

1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 它的左、右子树也分别为二叉排序树。

总结起来就是根据结点的值有：左子树<根结点<右子树

重要性质：中序遍历一棵二叉树时可以得到一个节点值递增的有序序列。

查找：二叉排序树插入的基本过程是查找，所以时间复杂度同查找一样，是O(log₂n)。

创建：创建二叉排序树算法的时间复杂度为O(nlog₂n)；

删除：时间复杂度仍是O(log₂n)

3.2　平衡二叉树（AVL树）

特征：

1. 左子树和右子树的深度之差的绝对值不超过1；
2. 左子树和右子树也是平衡二叉树。
3. 平衡因子（Balance Factor，BF）定义为该节点左子树和右子树的深度之差，则平衡二叉树上所有节点的平衡因子只可能是−1、0和1。

查找的时间复杂度为O(log₂n)

平衡二叉树的平衡调整方法

3.3　B- 树

B- 树的定义
多叉平衡搜索树
一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：

• 树中每个节点至多有m棵子树；
• 若根节点不是叶子节点，则至少有两棵子树；
• 除根之外的所有非终端节点至少有m/2棵子树；
• 所有的叶子节点都出现在同一层次上，并且不带信息，通常称为失败节点（失节点并不存在，指向这些节点的指针为空。引入失败节点是为了便于分析B−树的查找性能）；
• 所有的非终端节点最多有m − 1个关键字，节点的结构如图7.21所示。

来由, 定义, 插入, 构建：点击详情

删除：点击详情

3.4　B+ 树

B+ 树和 B- 树的差异
一棵m阶的B+ 树和m阶的B−树的差异在于：

• 有n棵子树的节点中含有n个关键字；
• 所有的叶子节点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接；
• 所有的非终端节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字。

B+ 树是一种B−树的变形树，更适合用于文件索引系统。

4.散列表的查找

4.1　散列表的基本概念

散列表也叫==>哈希表

1. 散列函数和散列地址:在记录的存储位置p和其关键字key之间建立一个确定的对应关系H,使 p= H(key) ,称这个对应关系H为散列函数，p为散列地址。
2. 散列表：采用散列技术将记录存放在一块连续有限的存储空间中，这块连续存储空间称为散列表或哈希表。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。

4.2　散列函数的构造方法

除留余数法

假设散列表表长为m，选择一个不大于m的数p，用p去除关键字，除后所得余数为散列地
址，即：
H(key) = key%p
这个方法的关键是选取适当的p，一般情况下，可以选p为小于表长的最大质数(素数)。例如，表
长m = 100，可取p = 97
若散列表的表长为m，通常p为小于表长的最大质数或不包含小于20质因子的合数。

4.3　处理冲突的方法

处理冲突的实际含义是：为产生冲突的地址寻找下一个哈希地址（散列地址）

1.开放地址法
所谓的开放地址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

①、线性探测法

d_i = 1,2,3,…,m-1

这种探测方法可以将散列表假想成一个循环表，发生冲突时，从冲突地址的下一单元顺序
寻找空单元，如果到最后一个位置也没找到空单元，则回到表头开始继续查找，一旦找到一个
空位，就把此元素放入此空位中。如果找不到空位，则说明散列表已满，需要进行溢出处理。

---

②、二次探测法

d_i = 1² ,-1² ,2² ,-2² ,3² ,……，+k² ,-k² （k≤m/2）

跟上述方法类似，只不过它是按照平方的顺序进行查找位置

③、伪随机探测法

略

2、链地址法

链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称之为同义词
链表。有m个散列地址就有m个单链表，同时用数组HT[0…m−1]存放各个链表的头指针，凡是散
列地址为i的记录都以节点方式插入以HT[i]为头节点的单链表。

---

总结

4.4　散列表的查找

查找过程中需和给定值进行比较的关键字的个数取决于三个因素：散列函数、处理冲突的方法和散列表的装填因子

散列表的装填因子α定义为：

α标志散列表的装满程度。直观地看，α越小，发生冲突的可能性就越小；反之，α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。

练习题

一、选择题

1.对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。

A. (n-1)/2
B. n/2
C. (n+1)/2
D. n

2.链表适用于（ ）查找

A. 顺序
B. 折半
C. 顺序,也能折半
D. 随机

3.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。

A. 20，70，30，50
B. 30，88，70，50
C. 20，50
D. 30，88，50

4.适用于折半查找的表的存储方式及元素排列要求为（ ）。

A. 链接方式存储，元素无序
B. 链接方式存储，元素有序
C. 顺序方式存储，元素无序
D. 顺序方式存储，元素有序

5.采用折半查找方式查找一个长度为n的有序顺序表时,其平均查找长度为( )。

A. O(n)
B. O(log2n)
C. O(n^2)
D. O(nlog2n)

6.已知一个长度为16的顺序表L,其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是()。

A. 4
B. 5
C. 6
D. 7

7.下列选项中，不能构成折半查找中关键字比较序列的是( )。

A. 500, 200, 450, 180
B. 500, 450, 200,180
C. 180, 500, 200, 450
D. 180, 200, 500, 450

8.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。

A. 100，80， 90， 60， 120，110，130
B. 100，120，110，130，80， 60， 90
C. 100，60， 80， 90， 120，110，130
D. 100，80， 60， 90， 120，130，110

9.如果有5个关键字{a,b,c,d,e}放在顺序表中,它们的查找概率分别为{0.35,0.25,0.20,0.15,0.05},按照( )顺序存放可使平均查找长度达到最小。

A. d,a,b,c,e
B. e,d,c,b,a
C. a,b,c,d,e
D. a,c,d,b

10.在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插入到集合中。这种方式主要适合于()

A. 静态查找表
B. 动态查找表
C. 静态查找表与动态查找表
D. 两种表都不适合

11.二叉排序树关键字中序遍历序列的排列顺序是( )。

A. 由小到大
B. 由大到小
C. 无序排列

12.设哈希表长为14，哈希函数是H（key）=key%11，表中已有数据的关键字为15、38、61、84现要将关键字为49的元素存储到表中，用二次探测解决冲突，则放入的位置是（）

A. 8
B. 3
C. 5
D. 9

13.下面关于哈希查找的说法，正确的是（ ）。

A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小。
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 哈希表的平均查找长度有时也和记录总数有关

14.为提高散列( Hash)表的查找效率，可以采取的正确措施是(）

I.增大装填(载)因子
II.设计冲突(碰撞)少的散列函数
Ⅲ.处理冲突(碰撞)时避免产生聚集(堆积)现象

A. 仅I
B. 仅II
C. 仅I、II
D. 仅II、Ⅲ

15.采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字( )。

A. 不一定都是同义词
B. 一定都是同义词
C. 一定都不是同义词
D. 都相同

16.用哈希(散列)方法处理冲突(碰撞)时可能出现聚集(堆积)现象，下列选项中， 会受堆积现象直接影响的是( )。

A. 存储效率
B. 散列函数
C. 装填(装载)因子
D. 平均查找长度

二、填空题

1.给定一组记录，其关键码为数字。记录按54，78，66，19，87，29，81，15的顺序输入并建立二叉排序树。请画出建立的二叉排序树，并给出查找81时分别与关键码 1 ， 2 ， 3 ， 4 进行比较，查找成功时的平均查找长度是 5 。（写出最简分数即可）

2.设哈希表的地址范围为0～13，哈希函数为：H（key）=key%13。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：
① 若查找关键字63，需要依次与（ 1 ）（ 2 ）关键字进行比较查找成功。
② 若查找关键字60，需要比较（3 ）次查找失败？
③ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度为（ 4 ）。（用最简分数表示）

答案解析

一、单选题解析

1.C
答案解析：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

2.A
答案解析：链表不能随机存储，所以只能顺序查找，不能折半查找。

3.A
答案解析：表中共10个元素，第一次取(1+10)/2=5，与第五个元素20比较，58大于20，再取(6+10)/2=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。

4.D
答案解析：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

5.B
答案解析：折半查找的平均查找长度与表长 n 的对数成正比，即 O(log₂n)。

6.B
答案解析：具有n个结点的二叉排序树查找失败的比较次数最多不会超过其深度，即不大于这个数最大整数+1，n=16时深度为5，叶子节点集中在第4和第5层上，所以查找失败最多需要比较5次。

7.A
答案解析：根据折半查找的规律，每次和中间的节点比较后根据其大小决定下一次的比较值，A选项第一次和500比较，根据第二次比较数值得出该值小于500，然后与200比较，第三次如果是与450比较，说明该值大于200，第四次结果与180比较，出现矛盾。以此类推可以检验其他选项是否合理。

8.C
答案解析：A、B、C、D四个选项构造二叉排序树都以100为根，易知A、B、D三个序列中第一个比100小的关键字为80，即100的左孩子为80。

9.C
答案解析：概率大的离根近。

10.B
答案解析：动态查找表在查找过程中可以插入不存在的数据元素。

11.A
答案解析：二叉排序树的中序遍历序列是一个递增有序序列。

12.D
答案解析：H(49)=49%11=5，但位置 5 已被 61 占用。二次探测法解决冲突：
第一次冲突：探测 (5+1²)%14=6（被 84 占用）
第二次冲突：探测 (5-1²)%14=4（被 15 占用）
第三次冲突：探测 (5+2²)%14=9（空），故放入位置 9。

13.C
答案解析：哈希表的查找长度与哈希函数、处理冲突的方法、表的装填因子、表的长度有关，与记录总数无关。

14.B
答案解析：提高散列表查找效率的措施包括：设计冲突少的散列函数（II）和处理冲突时避免产生聚集现象（III）。增大装填因子（I）通常会降低查找效率。

15.A
答案解析：出现冲突的时候，不一定都是哈希地址相同，有可能是处理冲突的计算地址。

16.D
答案解析：数据越是密集，那么在处理冲突的时候容易再次冲突。

二、填空题解析

1.答案：
(1) 54
(2) 78
(3) 87
(4) 81
(5) 21/8

答案解析：
依次插入 54, 78, 66, 19, 87, 29, 81, 15 构造二叉排序树。查找 81 的路径：54 → 78 → 87 → 81。
平均查找长度计算：各元素查找长度分别为 1(54), 2(78), 3(66), 2(19), 3(87), 3(29), 4(81), 3(15)，总和 21，平均 21/8。

正确答案：

(1) 24

(2) 63

(3) 7

(4) 20/11;1.82

答案解析：

散列地址	0	1	2	3	4	5	6	7	8	9	10	11	12	13
关键字	40				17	31	32	30	46	47	10	24	64	49
比较次数	1				1	1	1	4	2	2	1	1	2	4