第九章查找 习题解答.doc

第九章查找 习题解答 9.5 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 解：求得的判定树如下： 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） 在等概率情况下查找成功的平均查找长度为： ASL成功=（1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5 (2) 分析：对表中元素进行排序后，其实就变成了对长度为12的有序表进行折半查找了，那么在等概率的情况下的平均查找长度只要根据折半查找的判定树就很容易求出。 长度为12的有序表进行折半查找的判定树如下图所示： 所以可求出： 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）Typedef struct { Keytype key; }Elemtype; //记录类型； typedef struct { Elemtype *elem; int length; }SSTable; //顺序表类型； 按要求所得算法如下： int Search(SSTable ST, Keytype key) { ST.elem[ST.length].key=key; for (i=0; keyST.elem[i].key; i++); if (i==ST.length) return 0; else if (key==ST.elem[i].key) return i; else return 0; } (2)按此查找过程的判定树如下图所示： （3）等概率下的查找成功与查找不成功的平均查找长度分别为：、 ASL成功=（1+2+3+….+n）/n=(n+1)/2 ALS不成功=（1+2+3+…+n）/(n+1)=(n+2)/2 补充： 设散列表的长度为13，散列函数为H(K）=K%13，给定的关键字序列为: 19，14，23，01，68，20，84，27，55，11，10，79。试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，求这两种方法的查找成功和查找不成功的平均查找长度。 解：（1）用拉链法处理冲突： 因为：H(19)=6；H(14)=1;H(23)=10;H(01)=1;H(68)=3;H(20)=7; H(84)=6;H(27)=1;H(55)=3;H(11)=11;H(10)=10;H(79)=1 所以，构造的哈希表如下图所示： ^ ^ ^ ^ ^ 并求得：ASL成功=（1*6+2*4+3+4）/12=21/12 ASL不成功=（4+2*3+1*2）/13=12/13 （2）用线性探测再散列法处理冲突： 因为： H(19)=6； H(14)=1; H(23)=10; H(01)=1; H1(01)=2; H(68)=3; H(20)=7; H(84)=6; H1(84)=7; H2(84