【例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《转② /查找在左半区进行
b. 若kx>转② /查找在右半区进行。
c. 若kx=返回数据元素在表中位置 //查找成功。
查找关键字为14的过程如下：
low=1设置初始区间high=13
表空测试，非空；
mid=7 ③得到中点，比较测试为a情形。
low=1high=6 high=mid-1，调整到左半区。
表空测试，非空；
mid=3得到中点，比较测试为a情形。
low=1 high=2high=mid-1，调整到左半区。
表空测试，非空；
mid=1得到中点，比较测试为b情形。
low=2 high=2low=mid+1，调整到右半区。
表空测试，非空；
mid=2得到中点，比较测试为c情形。
查找成功，返回找到的数据元素位置为2
查找关键字为22的过程如下：
low=1设置初始区间high=13
表空测试，非空；
mid=7 ③得到中点，比较测试为a情形。
low=1high=6 high=mid-1，调整到左半区。
表空测试，非空；
mid=3得到中点，比较测试为b情形。
low=4 high=6 low=mid+1，调整到右半区。
表空测试，非空；
mid=5得到中点，比较测试为a情形。
low=4 high=4high=mid-1，调整到左半区。
表空测试，非空；
mid=4得到中点，比较测试为b情形。
high=4 low=5low=mid+1，调整到右半区。
表空测试，为空；查找失败，返回查找失败信息为0
查找过程的判定树如图7-1所示。
例7-2】记录的关键字序列为：63，90，70，55，67，42，98，83，10，45，58，则画出构造一棵二叉排序树的过程。
解：构造二叉排序树的过程如图7-2所示。
例7-3】关键字集为（47，7，29，11，16，92，22，8，3），哈希表表长为11。h（key）= key mod 11，用线性探测法处理冲突。
解：建表如下：
分析均是由哈希函数得到的没有冲突的哈希地址而直接存入的。
h（29）= 7，哈希地址上冲突，需寻找下一个空的哈希地址：
由hi =（h（29）+1） mod 11 = 8 ，哈希地址8为空，将29存入。另外同样在哈希地址上有冲突，也是由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
哈希表如下：
共有12个关键字，等概率查找，则成功查找时。
asl=（1+2+1+4+3+1+1+3+1+1+3+2）/12=23/12≈1.9
习题7一、单项选择题。
1. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )
a. nb. n+1c. (n-1)/2 d. (n+1)/2
2. 对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为( )的9分之一。
a. 20b. 18c. 25d. 22
3. 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为( )
a. 3b. 4c. 5d. 6
4. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为( )
查找练习题答案
查找。一 选择题。1.对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为 a n 1 2 b.n 2 c.n d.1 n n 2 2.下面关于二分查找的叙述正确的是 a.表必须有序，表可以顺序方式存储，也可以链表方式存储 c.表必须有序，而且只能从小到大排列。b.表必须有序且表中...
三年级句子排序讲解
1 巧排句序。三年级句子排序讲解。综合各句的意思 想想这句话主要说的是什么内容。想想全段的内容是按什么顺序排列的 即找出排列顺序的依据。第一招 按事情发展的顺序排列。第二招 按时间先后顺序排列。第三招 按空间推移的顺序排列。第四招 按先总述后分述的顺序排列。按确定的顺序排列。按排好的顺序仔细读几遍 ...
三年级句子排序讲解
整理句子的顺序。1 巧排句序。这要求将一些顺序混乱的句子，按正确的顺序重新排列，整理成一段通顺连贯的话，以准确表达作者的写作思路和意图。做这类练习，可以按以下五个步骤进行 仔细阅读每句话或每组句子，理解它们的主要内容。综合各句的意思，想想这句话主要说的是什么内容。想想全段的内容是按什么顺序排列的，即...