《数据结构第九章查找习题解答》由会员分享，可在线阅读，更多相关《数据结构第九章查找习题解答（6页珍藏版）》请在金锄头文库上搜索。
1、第九章查找 习题解答 9.5 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的 平均查找长度。 解：求得的判定树如下： 5 7 10 9 6 4 3 1 8 2 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)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半
2、查 找时查找成功的平均查找长度。 解：（1）求得的二叉排序树如下图所示： Jan Feb Mar Apr Aug Dec June July May Sept Oct Nov 在等概率情况下查找成功的平均查找长度为： ASL 成功=（1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5 (2) 分析：对表中元素进行排序后，其实就变成了对长度为12的有序表进行折半查 找了，那么在等概率的情况下的平均查找长度只要根据折半查找的判定树就很容易求 出。 长度为12的有序表进行折半查找的判定树如下图所示：6 8 12 11 7 5 4 1 9 3 2 10 所以可求出： ASL 成功=
3、（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,)。试在 010的散列地址空间中对关键字序列 （22，41，53，46，30，13，01，67）造哈希表，并求等概率情况下查找成功时 的平均查找长度。 解：因为 H(22)=0； H(41)=2； H(53)=5； H(46)=6； H(30)=2；H 1 (30)=3； H(13)=6；H 1 (13)=8； H(01)=3；H 1 (01)=0；H 2 (01)=8；H 3 (01)=5；H 4 （01）=
4、2；H 5 (01)=10 H(67)=3；H 1 (67)=2；H 2 (67)=1 所以：构造的哈希表如下图所示：0 1 2 3 4 5 6 7 8 9 10 22 67 41 30 53 46 13 01Ci：1 3 1 2 1 1 2 6 并求得等概率情况下查找成功的平均查找长度为：ASL 成功=（1*4+2*2+3+6）/8=17/8 9.21 在地址空间为016的散列区中，对以下关键字序列构造两哈希表： （Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec） (1)用线性探测开放定址法处理冲突； (2)用链地址法处理。 并分别求这两个
5、哈希表在等概率情况下查找成功和不成功时的平均查找长度。设 哈希函数为H(x)=i/2取整,其中i为关键字中第一个字母在字母表中的序号。 解：（1）因为： H(Jan)=5; H(Feb)=3; H(Mar)=6; H(Apr)=0;H(May)=6; H 1 (May)=7; H(June)=5;H 1 (June)=6;H 2 (June)=7;H 3 (June)=8 H(July)=5;H 1 (July)=6;H 2 (July)=7;H 3 (July)=8;H 4 (July)=9; H(Aug)=0; H 1 (Aug)=1 H(Sep)=9; H 1 (Sep)=10 H(Oc
6、t)=7; H 1 (Oct)=8;H 2 (Oct)=9; H 3 (Oct)=10; H 4 (Oct)=11; H(Nov)=7; H 1 (Nov)=8;H 2 (Nov)=9; H 3 (Nov)=10; H 4 (Nov)=11;H 5 (Nov)=12; H(Dec)=2所以，用线性探测开放定址法处理冲突构造的哈希表如下图所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov Ci:1 2 1 1 1 1 2 4 5 2 5 6并求得：ASL 成功
7、=（1*5+2*3+4+5*2+6）/12=31/12ASL 不成功=（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14=60/14 （2）用链地址法处理冲突构造的哈希表如下图所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Apr Aug Dec Feb Jan July June Mar May Nov Oct Sep 并求得： ASL成功=（1*7+2*4+3）/12=18/12 ASL不成功=（1*3+2*3+3）14=12/14 9.25 假设顺序表按关键字自大至小有序，试改写教科书9.1.1节中的顺序查找算法， 将监视哨设在高下
8、标端。然后画出描述此查找过程的判定树，分别求出等概率下 查找成功和不成功的平均查找长度。 解：（1）顺序表的存储结构描述：Typedef struct Keytype key;Elemtype; /记录类型； typedef struct Elemtype *elem;int length;SSTable; /顺序表类型； 按要求所得算法如下：int Search(SSTable ST, Keytype key) ST.elemST.length.key=key;for (i=0; keyST.elemi.key; i+);if (i=ST.length) return 0;else if (
9、key=ST.elemi.key) return i;else return 0; (2)按此查找过程的判定树如下图所示： 1 2 3 n （3）等概率下的查找成功与查找不成功的平均查找长度分别为：、ASL 成功=（1+2+3+.+n）/n=(n+1)/2ALS 不成功=（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。试画出分别用拉链法和线性探 查法解决冲突时所构造的散列表，并求出在等概率情况下，求这两种方法的查找成功 和查找不成功的平均查找长
10、度。 解：（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/12ASL不成功=（4+2*3+1*2）/13=12/13（2）用线性探测再散列法处理冲突： 因为： H(19)=6； H(14)=1; H(23)=10; H(01)=1; H 1 (01)=2; H(68)=3; H(20)=7; H(84)=6; H 1 (8
11、4)=7; H 2 (84)=8; H(27)=1;H 1 (27)=2; H 2 (27)=3; H 3 (27)=4; H(55)=3; H 1 (55)=4; H 2 (55)=5; H(11)=11; 0 1 2 3 4 5 6 7 8 9 10 11 12 68 19 84 20 11 01 14 27 79 10 23 55H(10)=10; H 1 (10)=11; H 2 (10)=12; H(79)=1; H 1 (79)=2; H 2 (79)=3; H 3 (79)=4; H 4 (79)=5; H 5 (79)=6; H 6 (79)=7; H 7 (79)=8; H 8 (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/12ASL不成功=（1+13+12+11+10+9+8+7+6+5+4+3+2）/13=7
