第7章 查找
【例7-1】有序表按关键字排列如下：7，14，18，21，23，29，31，35，38，42，46，49，52，在表中查找关键字为14和22的数据元素，并画出折半查找过程的判定树。
解：折半查找的过程描述如下：
① low=1；high=length； //设置初始区间 ② 当low>high时，返回查找失败信息 //表空，查找失败 ③ low≤high，mid=(low+high)/2; //取中点
a. 若kx
0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 ↑ ↑ low=1 ①设置初始区间 high=13 ─────────────────────────── ↑ ②表空测试，非空；
mid=7 ③得到中点，比较测试为a情形 ↑ ↑
low=1 high=6 high=mid-1，调整到左半区 ──────────────────────────── ↑ ②表空测试，非空；
mid=3 ③得到中点，比较测试为a情形 ↑ ↑
low=1 high=2 high=mid-1，调整到左半区
──────────────────────────── ↑ ②表空测试，非空；
mid=1 ③得到中点，比较测试为b情形 ↑↑
low=2 high=2 low=mid+1，调整到右半区
──────────────────────────── ↑ ②表空测试，非空；
mid=2 ③得到中点，比较测试为c情形 查找成功，返回找到的数据元素位置为2
? 查找关键字为22的过程如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 ↑ ↑ low=1 ①设置初始区间 high=13 ──────────────────────────── ↑ ②表空测试，非空；
mid=7 ③得到中点，比较测试为a情形 ↑ ↑
low=1 high=6 high=mid-1，调整到左半区 ─────────────────────────── ↑ ②表空测试，非空；
mid=3 ③得到中点，比较测试为b情形
↑ ↑
low=4 high=6 low=mid+1，调整到右半区
────────────────────────────
↑ ②表空测试，非空；
mid=5 ③得到中点，比较测试为a情形
↑↑
low=4 high=4 high=mid-1，调整到左半区
────────────────────────────
↑ ②表空测试，非空；
mid=4 ③得到中点，比较测试为b情形
↑ ↑
high=4 low=5 low=mid+1，调整到右半区
────────────────────────────
②表空测试，为空；查找失败，返回查找失败信息为0
? 查找过程的判定树如图7-1所示。
7 10 3 5 8 12 1
2 4 6 9 11 13
折半查找过程的判定树图7-1
【例7-2】记录的关键字序列为：63，90，70，55，67，42，98，83，10，45，58，则画出构造一棵二叉排序树的过程。
解：构造二叉排序树的过程如图7-2所示。 63 63 63 63 63 63 63
55 90 90 90 55 90 55 90 55 90
70 42 70 98 70 70 42 70
67 67 67
63 63 63 63
55 55 90 55 90 90 55 90
42 42 58 70 98 70 98 42 70 98 42 70 98
10 45 67 83 10 45 67 83 10 67 83 67 83
图7-2 二叉排序树的构造过程
【例7-3】关键字集为（47，7，29，11，16，92，22，8，3），哈希表表长为11。H（key）= key MOD 11，用线性探测法处理冲突。
解：建表如下：
0 11 1 2 3 4 5 6 7 8 9 10 22 47 92 16 3 7 29 8 △ ▲ △ △
分析：47、7、11、16、92均是由哈希函数得到的没有冲突的哈希地址而直接存入的。 H（29）= 7，哈希地址上冲突，需寻找下一个空的哈希地址：
由Hi =（H（29）+1） MOD 11 = 8 ，哈希地址8为空，将29存入。另外，22、8同样在哈希地址上有冲突，也是由Hi找到空的哈希地址的。
而H（3）= 3，哈希地址上冲突，由：H1=（H（3）+1）MOD 11 = 4，仍然冲突。 H2=（H（3）+2）MOD 11 = 5，仍然冲突。H3=（H（3）+3）MOD 11 = 6，找到空的哈希地址，存入。
【例7-5】设有一组关键字（19，01，23，14，55，20，84，27，68，11，10，77），采用哈希函数：H（key）= key % 13，若用开放定址法的线性探测法解决冲突，试在0～13的哈希地址空间中对该关键字序列构造哈希表并求其成功查找时的ASL。
解：依题意，m=13，线性探测法的下一个地址计算公式为： di = H（key）
di+1 = （di+1）% m ；i=1，2，? 其计算函数如下： H（19）= 19 % 13 = 6 H（01）= 01 % 13 = 1 H（23）= 23 % 13 = 10
H（14）= 14 % 13 = 1 （冲突） H（14）=（1+1）% 14 = 2 H（55）= 55 % 13 = 3 H（20）= 20 % 13 = 7
H（84）= 84 % 13 = 6 （冲突）
H（84）=（6+1）% 14 = 7 （仍冲突） H（84）=（7+1）% 14 = 8
H（27）= 27 % 13 = 1 （冲突）
H（27）=（1+1）% 14 = 2 （仍冲突） H（27）=（2+1）% 14 = 3 （仍冲突） H（27）=（3+1）% 14 = 4
H（68）= 68 % 13 = 3 （冲突）
H（68）=（3+1）% 14 = 4 （仍冲突） H（68）=（4+1）% 14 = 5 H（11）= 11 % 13 = 11
H（10）= 10 % 13 = 10 （冲突）
H（10）=（10+1）% 14 = 11 （仍冲突） H（10）=（11+1）% 14 = 12 H（77）= 77 % 13 = 12 （冲突） H（77）=（12+1）% 14 = 13 哈希表如下：
哈希地址 关键字 0 1 1 1 2 14 2 3 55 1 4 27 4 5 68 3 6 19 1 7 20 1 8 84 3 9 10 23 1 11 11 1 12 10 3 13 77 2 比较次数 共有12个关键字，等概率查找，则成功查找时
ASL=（1+2+1+4+3+1+1+3+1+1+3+2）/12=23/12≈1.9
习题7
一、单项选择题
1. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。
A. n B. n+1 C. (n-1)/2 D. (n+1)/2
2. 对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为( )的9分之一。
A. 20 B. 18 C. 25 D. 22
3. 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为( )。
A. 3 B. 4 C. 5 D. 6
4. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为( )。
A. 2 B. 3 C. 4 D. 5
5. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K计算哈希地址，则元素64的哈希地址为( )。
A. 4 B. 8 C. 12 D. 13
6. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数( )。
A. 1 B. 2 C. 3 D. 4
7. 若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为( )。
A. d B. d+1 C. (d+1)/m D. (d+1)%m 二、填空题
1. 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为________，时间复杂度为________。
2. 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成________存储的________表。
3. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为________和________。
4. 假定对长度n=50的有序表进行折半查找，则对应的判定树高度为________，最后一层的结点数为________。 5. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点的值。
6. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。
7. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到________次存储冲突。
8. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为________。
9. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，
则哈希地址为0的元素有________个，哈希地址为5的元素有________个。
三、应用题
1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的折半查找判定树，求出其平均查找长度。
2. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。
3. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)，哈希地址空间为HT[13]，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。
元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 最终哈希地址
0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 4. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。