发布时间 : 星期二 文章数据结构 第八章 查找表更新完毕开始阅读8bb4a50ccc17552707220851
19．设用线性探测再散列解决冲突，根据公式Snl≈（1+1/（1-α）） /2 。可求出负载因子为α=0.67。再根据数据个数和装载因子，可求出表长m=15/0.67，取m=23。设哈希函数H（key）=（关键字首尾字母在字母表中序号之和）MOD 23。
从上表求出查找成功时的平均查找长度为ASLsucc=19/15<2.0，满足要求。 20．（1）哈希函数H（key）=（关键字各字符编码之和）MOD 7 （2）
散列地址 关键字 比较次数 0 be 1 1 cd 2 2 aa 1 3 ab 1 4 ac 1 5 ad 1 6 bd 1 7 bc 3 8 ae 3 9 ce 9 21．α=0.7，所以表长取m=7/0.7=10
散列地址 0 关键字 1 2 3 4 5 6 7 8 9 SAT WED SUN MON TUE THU FRI 1 1 1 2 3 4 比较次数 6 ASLsucc=18/7 ASLunsucc=32/10 22．（1）
散列地址 0 关键字 1 2 3 4 5 6 7 8 9 10 11 12 27 53 2 31 19 20 8 18 1 1 1 1 1 1 2 比较次数 3 （2）ASLsuss =11/8 23．（1）
散列地址 0 1 2 3 4 关键字 5 6 7 8 9 10 11 12 0 3 29 200 32 45 58 100 10 126 400 1 1 2 3 1 1 3 3 比较次数 1 1 2 关键字29和45各发生一次碰撞，关键字58,126和400各发生两次碰撞，其余关键字无碰撞。 （2）
散列地址 0 关键字 1 2 3 4 5 6 7 8 9 10 11 12 58 10 100 3 200 32 400 0 45 126 29 1 2 1 3 1 3 8 1 2 1 比较次数 1 发生碰撞次数：100，126一次；200，400两次；0七次。其余关键字无碰撞。 24．由α=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
25．在B-树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后，要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。
26．m阶的B+树和B-树主要区别有三：（1）有n棵子树的结点中含有n（B-树中n-1）个关键字；（2）B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点本身依关键字大小自小到大顺序链接；（3）B+树的非终端结点可以看成是索引部分，结点中只含其子树（根结点）中最大（或最小）关键字。B+树的查找既可以顺序查找，也可以随机查找，B-只能顺序查找。
27．本题等价于“含有n个关键字的m阶B-树的最大高度是多少”？一次检索中最多走一条从根到叶子的路径，由于根结点至少有两棵子树，其余每个（除叶子）结点至少有?m/2?棵子树，则第三层至少有?m/2?*2个结点，第l+1层至少有2*?m/2?个结点。设B-树深度为l+1，即第l+1层是叶子结点，叶子结点数是n+1（下面推导），故有n+1≥2*?m/2? 附：推导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。证毕。 28．表长m=12/0.6=20 （1）H（key）=key MOD 19
（2）两次碰撞。开地址线性探测法解决冲突，即是用拉链法解决冲突。 29．由于地址空间为10，且从100开始，故散列函数选为H（key）=key%7+100。
l-1
l-1
散列地址 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
30．第一层有1个结点，第二层至少有2个结点，第三层有2*?m/2?个结点，第四层有2*?m/2?个结点，??，第h层至少有2*?m/2?个结点（h≥2）。结点总数是
1+2+2*?m/2?+2*?m/2?+?+2*?m/2?=2*?m/2?-1
31．满二叉检索树可以看作是三阶B-树（2—3树）。B-树的插入和删除算法不适合满二叉检索树。满二叉检索树插入和删除结点后均破坏了“多路平衡查找树”“叶子在同一层上”（查找失败结点）的定义。
32．B+树的查找可从根结点开始随机查找，也可以从最小关键字起顺序查找。
33．在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字K，时间复杂度是O（n）。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是（n+1）/2，时间复杂度也是O（n）。 34．按中序遍历序列将值1~9依次标上。 35.ASLsucc=32/10
36. （2）10,12,15,20,24,28,30,35,46,50,55,68
（3）ASLsucc=41/12
37．（1）本题的本质是给定中序序列1、2、3、4，有几种不同的二叉排序树，也即该中序序列相当多少不同的前序序列，这是树的计数问题。设中序序列中元素数为n，则二叉数的数目为1/（n+1）C2n，这里n=4，故有14种。图示如下： （2）最优查找树有4种，上面中⑽ ⑾ ⑿ ⒀ （3）AVL树有，也是（2）中的那4种 （4）完全二叉树有1种，上图中⑽
38．当m层的AVL树是满二叉树时，结点数为最大值2-1。
39．树的高度一定增加。因为“查找路径上的任一结点的平衡系数皆为零”，从根结点开始查找，根结点的平衡系数为零，说明根的左右子树等高（不一定是满二叉树）。沿左（或右）子树向下查找时，查找路径上所有结点的平衡系数皆为零，说明任一结点的左右子树等高，查找失败是在叶子结点，插入也是在叶子结点，树的高度自然增加。
m
n
2
h-2
h-1
h-2
2
说明：在（3）后，先删除结点CAN并未破坏平衡，在删AQU后破坏了平衡，根结点CAP的平衡因子为-2。需作何种调整，要看CAP右子树PIS的平衡因子，若该平衡因子是1，则作RL型调整；若为-1，则作RR型调整；若为0，则RR和RL均可，为简单计，选RR型。当然，在PIS平衡因子为零后，还可继续往下分析。
40．按索引顺序查找分块组织数据。N个区间分块有序，区间（块）内无序，将块内最大关键字置于块内最后一个位置，即向量下标为ik-1，其中i=1，2，?，N-1，k为每区间的长度（最后一个区间的最大关键字置于向量最后一个位置）。查找时，若N较小，可用顺序查找，依次将x与r[ik-1]*key进行比较，找到合适块后在块内顺序查找；若N很大，也可用折半查找，以确定x所在块，在块内顺序查找。 41．37/12
42．线性表应顺序存储且数据有序。
43．表长为n，每块大小取n时，平均查找长度取最小值n+1。若n=255，则每块长度为16。
44．表长2000，分成45块，每块的理想长度为45（最后一块长20）。若每块长25，则平均查找长度为ASL=(80+1)/2+(25+1)/2=53.5（顺序查找确定块），或ASL=19（折半查找确定块）。
45．将n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较，??，比较中的小者放前半部，大者放后半部，用了?n/2?次比较。再在前后两部分中分别简单选择最小和最大元素，各用?n/2?-1次比较。总共用了3*?n/2?-2次比较。 46．在有序表A[1..14]中，比较到A[4]时，已查找元素依次是A[7]，A[3]，A[5]。 查找成功的平均查找长度是=1*0.25+2*(0.12+0.20)+3*(0.1+0.08+0.20)+4*0.05=2.23 由于在构造次优查找树的过程中，没有考查单个关键字的相应权值，可能出现根的关键字的权值比之相邻的关键字的权值小，这时要作调整：选邻近的权值较大的关键字作次优查找树的根结点。
47．（1） 顺序查找判定树
（2）ASL顺序成功 =（1p1 +2p2+3p3+4p4+5p5)=0.97 ASL折半成功 =（1p3+2（p1+p4）+3（p2+p5)=1.04 ASL折半失败 =（2q0+3q1+3q2+2q3+3q4+3q5)=1.30 ASL顺序失败 =（1q0+2q1+3q2+4q3+5q4+5q5)=1.07 （3）本题中顺序检索好。
1/2
1/2