Author: Eman Lee
计算机软件基础，教材
P131，第4题参考答案
（1）查找e的过程
a | b | c | d | e | f | g | h |
Low=1 | Mid=4 | High=8 | |||||
a | b | c | d | e | f | g | h |
Low=5 | Mid=6 | High=8 | |||||
a | b | c | d | e | f | g | h |
Low=5 Mid=5 High=5 | 查找成功 |
（2）查找f的过程
a | b | c | d | e | f | g | h |
Low=1 | Mid=4 | High=8 | |||||
a | b | c | d | e | f | g | h |
Low=5 | Mid=6 | High=8 | |||||
查找成功 |
（3）查找h的过程
a | b | c | d | e | f | g | h |
Low=1 | Mid=4 | High=8 | |||||
a | b | c | d | e | f | g | h |
Low=5 | Mid=6 | High=8 | |||||
a | b | c | d | e | f | g | h |
Low=7 Mid=7 | High=8 | ||||||
a | b | c | d | e | f | g | h |
查找成功 | Low=8 Mid=8 High=8 |
P131，第5题参考答案
表长m=13 ，哈希函数：H(Ki)=Ki%13 (i=0,1,2,….9)
关键字Ki | 18 | 25 | 14 | 56 | 78 | 33 | 27 | 32 | 60 | 42 |
哈希地址 | 5 | 12 | 1 | 4 | 0 | 7 | 1 | 6 | 8 | 3 |
（1） 线性探测再散列，
哈希地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
关键字Ki | 78 | 14 | 27 | 42 | 56 | 18 | 32 | 33 | 60 | 25 | |||
比较次数 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
平均比较次数：11/10=1.1次
（2） 二次探测再散列, H(Ki)=(H(Ki)+di)%m, di=1*1,-1*1,2*2,-2*2,…..(m/2)*(m/2), -.(m/2)*(m/2)
哈希地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
关键字Ki | 78 | 14 | 27 | 42 | 56 | 18 | 32 | 33 | 60 | 25 | |||
比较次数 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
平均比较次数：11/10=1.1次
（3）链地址法
标签：8abcdefghLow,P131,6High,参考答案,查找,哈希,习题,5Mid From： https://blog.51cto.com/emanlee/8245759