31 3阶 B-树（ 5）设哈希表的地址范围为 0～ 17，哈希函数为： H （ key） =key%16 。用线性探测法处理冲突，输入关键字序列： （ 10， 24， 32， 17， 31 ， 30， 46， 47， 40， 63， 49） ，构造哈希表，试回答下列问题：1 画出哈希表的示意图；2 若查找关键字 63，需要依次与哪些关键字进行比较？3 若查找关键字 60，需要依次与哪些关键字比较？4 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
31 3阶 B-树
（ 5）设哈希表的地址范围为 0～ 17，哈希函数为： H （ key） =key%16 。用线性探测法处
理冲突，输入关键字序列： （ 10， 24， 32， 17， 31 ， 30， 46， 47， 40， 63， 49） ，构造哈希表，
试回答下列问题：
1 画出哈希表的示意图；
2 若查找关键字 63，需要依次与哪些关键字进行比较？
3 若查找关键字 60，需要依次与哪些关键字比较？
4 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
题目解答
答案
5 画表如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
32
17
63
49
24
40
10
30
31
46
47
② 查找 63,首先要与 H（63）=63%16=15 号单元内容比较，即 63 与 31 比较 ,不匹配 ;
然后顺移，与 46,47,32,17,63 相比，一共比较了 6 次！
③ 查找 60, 首先要与 H（60）=60%16=12 号单元内容比较，但因为 12 号单元为空（应当有
空标记） ，所以应当只比较这一次即可。
④ 对于黑色数据元素，各比较 1 次；共 6 次；
对红色元素则各不相同，要统计移位的位数。 “ 63 ”需要 6 次， “ 49”需要 3 次， “ 40”需
要 2 次， “ 46”需要 3 次， “ 47”需要 3 次，
所以 ASL=1/11 （ 6＋ 2＋ 3× 3+6 ）＝ 23/11
（ 6） 设有一组关键字 （ 9， 01 ， 23， 14， 55， 20， 84， 27） ， 采用哈希函数： H（ key） =key %7
表长为 10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计
算查找成功的平均查找长度。
散列地址
1
2
3
4
5
6
7
8
9
关键字
14
1
9
23
84
27
55
20
比较次数
1
1
1
2
3
4
1
2
平均查找长度： ASL succ= （ 1+1+1+2+3+4+1+2 ） /8=15/8
以关键字 27 为例： H （ 27） =27%7=6 （冲突） H 1=（ 6+1 ） %10=7 （冲突）
H2=（ 6+2 2） %10=0 （冲突） H3= （ 6+3 3） %10=5 所以比较了 4 次。
（ 7）设哈希函数 H（ K ） =3 K mod 11 ，哈希地址空间为 0～ 10，对关键字序列（ 32， 13，