012345678 0123456789 12→34 →24 卡3827 10 13题图ASLe=11/8 ASL=19/1114题(2) ASlSuCC=13/8 ASL=19/1 值得指出,对用拉链法求查找失败时的平均查找长度有两种观点。其一,认为比较到空 指针算失败。以本题为例,哈希地址0、2、5、7、9和10均为比较1次失败,而哈希地址 1和3比较2次失败,其余哈希地址均为比较3次失败,因此,查找失败时的平均查找长度 为19/11,我们持这种观点。还有另一种理解,他们认为只有和关键字比较才计算比较次数 而和空指针比较不计算。照这种观点,本题的 ASLo=(1+1+2+2+2)/11=8/11 14.由 hashi(x)=xmod11可知,散列地址空间是0到10,由于有8个数据,装载因子取 0.7 (1) 关键字 131234 比较次数11134 28 SLu=21/8 47/11 15 1) 2)b:0 1234567890 Feb A M 八 11[△ 12 八 13∧ (1)ASL=42/12 2)2[散列地址01234 T9 lo i 12 i3l14Ts T161 字 Apr aug Dec T 比次数1211H1 (2)a:ASLm=31/12(2)b: ASL=18/12(注:本题[x]取小于等于x的最大整 数)（2） 13 题图 ASLsucc =11/8 ASLunsucc=19/11 14 题（2） ASLsucc=13/8 ASLunsucc=19/11 值得指出，对用拉链法求查找失败时的平均查找长度有两种观点。其一，认为比较到空 指针算失败。以本题为例，哈希地址 0、2、5、7、9 和 10 均为比较 1 次失败，而哈希地址 1 和 3 比较 2 次失败，其余哈希地址均为比较 3 次失败，因此，查找失败时的平均查找长度 为 19/11，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数， 而和空指针比较不计算。照这种观点，本题的 ASLunsucc=（1+1+2+2+2）/11=8/11 14．由 hashf(x)=x mod 11 可知，散列地址空间是 0 到 10，由于有 8 个数据，装载因子取 0.7。 （1） 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 33 1 13 12 34 38 27 22 比较次数 1 1 1 3 4 1 2 8 ASLsucc=21/8 ASLunsucc=47/11 15． （1）ASL=42/12 （2）a：ASLsucc=31/12 （2）b：ASLsucc=18/12 (注：本题[x]取小于等于 x 的最大整 数) 16．