第九章查找习题解答

第九章查找 习题解答 9.5 画出对长度为10 的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 解：求得的判定树如下： 571 09643182 ASL 成功=（1+2*2+4*3+3*4）/10 =2.9 9.9 已知如下所示长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec） (1)试按表中元素的顺序依次插入一查初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 (2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 解：（1）求得的二叉排序树如下图所示： J a nF e bM a rA p rA u gD e cJ u n eJ u l yM a yS e p tO c tN o v 在等概率情况下查找成功的平均查找长度为： ASL 成功=（1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5 (2) 分析：对表中元素进行排序后，其实就变成了对长度为12 的有序表进行折半查找了，那么在等概率的情况下的平均查找长度只要根据折半查找的判定树就很容易求出。 长度为12 的有序表进行折半查找的判定树如下图所示： 681211754193210 所以可求出： ASL 成功=（1+2*2+4*3+5*4）/12=37/12 9.19 选取哈希函数H(k)=(3k) MOD 11。用开放定址法处理冲突，di=i((7k)MOD 10 +1)(i=1,2,3,…)。试在 0~10 的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）造哈希表，并求等概率情况下查找成功时的平均查找长度。 解：因为 H(22)=0； H(41)=2； H(53)=5； H(46)=6； H(30)=2；H1(30)=3； H(13)=6；H1(13)=8； H(01)=3；H1(01)=0；H2(01)=8；H3(01)=5；H4（01）=2；H5(01)=10 H(67)=3；H1(67)=2；H2(67)=1 所以：构造的哈希表如下图所示： 0 1 2 3 4 5 6 7 8 9 10 22 67 41 30 53 46 13 01 Ci：1 3 1 2 1 1 2 6 并求得等概率情况下查找成功的平均查找长度为： ASL 成功=（1*4+2*2+3+6）/8=17/8 9.21 在地址空间为 0~16 的散列区中，对以下关键字序列构造两哈希表： （Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec） (1)用线性探测开放定址法处理冲突； (2)用链地址法处理。 并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。设哈希函数为 H(x)=i/2 取整,其中 i 为关键字中第一个字母在字母表中的序号。 解：（1）因为： H(Jan)=5; H(Feb)=3; H...