发布时间 : 星期二 文章严蔚敏-数据结构集合习题更新完毕开始阅读4410cb09bb68a98271fefaf5
18．ASLsucc =15/10
19．ASLsuss =16/11
20． 散列地址 0 关键字 比较次数 1 ASLsucc =21/11 21． 散列地址 0 关键字 22． （1）
散列0 地址 关键字
1 1 2 1 3 1 4 2 5 1 6 2 7 3 8 2 9 4 10 3 11 231 89 79 25 47 16 38 82 51 39 151 1 33 2 2 46 1 3 13 2 4 01 4 5 67 5 6 7 8 41 1 9 53 1 10 30 3 22 比较次数 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 32 17 63 49 24 40 10
比较1 次数 1 6 3 1 2 1 1 1 3 3 （2）查找关键字63，H（k）=63 MOD 16=15，依次与31，46，47，32，17，63比较。 （3）查找关键字60，H（k）=60 MOD 16=12，散列地址12内为空，查找失败。 （4）ASLsucc=23/11
23．设用线性探测再散列解决冲突，根据公式Snl≈（1+1/（1-α）） /2 。可求出负载因子为α=0.67。再根据数据个数和装载因子，可求出表长m=15/0.67，取m=23。设哈希函数H（key）=（关键字首尾字母在字母表中序号之和）MOD 23。
从上表求出查找成功时的平均查找长度为ASLsucc=19/15<2.0，满足要求。 24．（1）哈希函数H（key）=（关键字各字符编码之和）MOD 7 （2） 散列地址 关键字 比较次数 0 be 1 1 cd 2 1 2 1 2 aa 1 3 ab 1 4 ac 1 6 1 5 ad 1 7 2 6 bd 1 8 3 7 bc 3 9 4 8 ae 3 9 ce 9 25．α=0.7，所以表长取m=7/0.7=10 散列地址 0 关键字 比较次数 6 3 4 5 1 SAT WED SUN MON TUE THU FRI ASLsucc=18/7 ASLunsucc=32/10 26．（1）
散列地址 0 关键字 比较次数 3 1 1 2 3 4 5 1 1 6 1 7 1 8 9 1 2 10 11 12 27 53 2 31 19 20 8 18 （2）ASLsuss =11/8 27．（1）
散列地址 0 1 2 3 4 关键字 0 比较次数 1 1 2 5 1 6 1 7 2 8 3 9 1 10 11 1 3 12 3 3 29 200 32 45 58 100 10 126 400 关键字29和45各发生一次碰撞，关键字58,126和400各发生两次碰撞，其余关键字无碰撞。 （2） 散列地址 0 关键字 比较次数 1 1 1 2 2 3 4 1 3 5 1 6 3 7 8 9 8 1 10 2 11 12 1 58 10 100 3 200 32 400 0 45 126 29 发生碰撞次数：100，126一次；200，400两次；0七次。其余关键字无碰撞。 28．由α=0.75，得表长m=11/0.75=15
（1）散列函数H（k）=k MOD 13（p取小于等于表长的最大素数）
（2）因为p=13，散列地址取0到12，用链地址法解决冲突，实际长就取13。
（2）ASLsucc=18/11 （3）ASLunsucc=24/13
29．在B-树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后，要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。
30．m阶的B+树和B-树主要区别有三：（1）有n棵子树的结点中含有n（B-树中n-1）个关键字；（2）B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点本身依关键字大小自小到大顺序链接；（3）B+树的非终端结点可以看成是索引部分，结点中只含其子树（根结点）中最大（或最小）关键字。B+树的查找既可以顺序查找，也可以随机查找，B-只能顺序查找。
31．本题等价于“含有n个关键字的m阶B-树的最大高度是多少”？一次检索中最多走一条从根到叶子的路径，由于根结点至少有两棵子树，其余每个（除叶子）结点至少有?m/2?
l-1
棵子树，则第三层至少有?m/2?*2个结点，第l+1层至少有2*?m/2?个结点。设B-树深度
l-1
为l+1，即第l+1层是叶子结点，叶子结点数是n+1（下面推导），故有n+1≥2*?m/2?，
即l≤log?m/2?（
）+1。
附：推导B-树中叶子结点数s与关键字数n的关系式：s=n+1
设B-树某结点的子树数为Ci，则该结点的关键字数Ni=Ci-1。对于有k个结点的B-树，有
∑Ni=∑(Ci-1)=∑Ci-k（1≤i≤k） ??（1）
因为B树上的关键字数，即∑Ni=n （1≤i≤k） ??（2）
而B-树上的子树数可这样计算：每个结点（除根结点）都是一棵子树，设叶子（子树）数为s；则
∑Ci=(k-1)+s （1≤i≤k） ??（3）
综合（1）（2）（3）式，有s=n+1。证毕。 32．表长m=12/0.6=20 （1）H（key）=key MOD 19
（2）两次碰撞。开地址线性探测法解决冲突，即是用拉链法解决冲突。见本章四第2题（2）③
第32题用拉链法解决冲突
33．由于地址空间为10，且从100开始，故散列函数选为H（key）=key%7+100。
散列地址 100 101 102 103 104 105 106 107 108 109 关键字 98 63 2 79 1 17 1 53 1 19 1 61 2 75 3 46 5 49 10 比较次数 1 用线性探测再散列解决冲突，ASLsucc=27/10
34．
35．