第八章查找补作充业解答(Java版).docVIP

第八章查找 作业解答 1.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 解：求得的判定树如下： ASL成功=（1+2*2+4*3+3*4）/10 =2.9 2.已知如下所示长度为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+4*4）/12=33/12 3. 基于SeqList类，设计带监视哨的顺序查找算法，要求把监视哨设置在n号单元（其中n为查找表的表长）。 解： int seqSearchwithGuard(Compareable key) { int n=length(); r[n].setKey(key); //置哨兵 for (i=0; r[i].getKey().coppareTo(key)!=0; i++); if (i==n) return -1; //查找失败 else return i;; //查找成功 } 4. 设散列表的长度为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)=2; H2(84)=3; H(27)=1;H1(27)=2; H2(27)=3; H3(27)=4; H(55)=3; H1(55)=4; H2(55)=5; H(11)=11; H(10)=10; H1(10)=11; H2(10)=12; H(79)=1; H1(79)=2; H2(79)=3; H3(79)=4; H4(79)=5; H5(79)=6; H6(79)=7; H7(79)=8; H8(79)=9 所以，构造的哈希表如下图所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 14 01 68 27 55 19 20 84 79 23 11 10 Ci: 1 2 1 4 3 1 1 3 9 1 1 3 并求得： ASL成功=（1*6+2+3*3+4+9）/12=30/12 ASL不成功=（1+13+12+11+10+9+8+7+6+5+4+3+2）/13=7 5. 在地址空间为0~16的散列区中，对以下关键字序列构造两哈希表： （Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）（2）用链地址法处理冲突构造的哈希表如下图所示： ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 并求得： ASL成功=（1*7+2*4+3）/12=18/12 ASL不成功=（1*3+2*3+3）14=12/14 0 1 2 3 4 5 6 7 8 9 10 11 12 27 01 14 79 ^ 68 ^ 55 84 ^ 19 20 ^ 23 ^ 10 11 ^ 0 1 2 3 4 5 6 7 8 9