发生碰撞次数：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
48．时间复杂度是判断检索方法的一个重要指标，但不是唯一指标。使用什么检索方法要综合考虑。哈希检索时间O（1），查找速度最快，但需构建哈希函数，进行计算哈希地址，查找时要有解决冲突的方法；二分检索时间O（log2n），需要元素有序且顺序存储，排序操作的时间开销大；顺时检索时间最差为O（n），但对检索表无要求，数据有序无序均可，在数据量较小时使用方便。 返回
五．算法设计题
1． 1． 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与
其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 #define true 1 #define false 0 typedef struct node
{datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST（BTree t,int flag）
// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（t!=null && flag）
{ Judgebst（t->llink,flag）；// 中序遍历左子树
if（pre==null）pre=t；// 中序遍历的第一个结点不必判断 else if（pre->data
本题的另一算法是照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：
int JudgeBST（BTree t）
//判断二叉树t是否是二叉排序树，若是，返回true，否则，返回false {if（t==null）return true；
if（Judgebst（t->llink）&& Judgebst（t->rlink））//若左右子树均为二叉排序树
{m=max（t->llink）；n=min（t->rlink）；//左子树中最大值和右子树中最小值 return （t->data>m && t->data int max（BTree p）//求二叉树左子树的最大值 {if（p==null） return -maxint；//返回机器最小整数 else{while（p->rlink！=null）p=p->rlink； return p->data；} } int min（BTree p）//求二叉树右子树的最小值 {if（p==null） return maxint；//返回机器最大整数 else{while（p->llink！=null）p=p->llink； return p->data；} } 2．[题目分析]借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按k个集合分块（元素个数不一定相等），索引表中有两个域，一是各集合最后一个元素在数据表中的位置（一维数组中的下标），二是集合的个数（k）。实现数据运算时，根据给定的二元组（i，x），首先在索引表中找到集合i的位置，然后在数据表中查找x。如查到x ，则查找成功，返回x在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入x，同时修改索引表。 typedef struct {datatype data；}rectype； typedef struct {int a[]；//a数组容量够大，存储各集合最后一个数据在数据表中的下标 int k； //集合个数 }index； int SetSearch_Insert（rectype R[]，index id，datatype x，int i） //数据表R，查找第i个集合的元素x，若查找成功，返回其位置，否则将其插入第i个集合