查找成功的平均查找长度是=1*0.25+2*(0.12+0.20)+3*(0.1+0.08+0.20)+4*0.05=2.23 由于在构造次优查找树的过程中，没有考查单个关键字的相应权值，可能出现根的关键字的权值比之相邻的关键字的权值小，这时要作调整：选邻近的权值较大的关键字作次优查找树的根结点。调整后的次优查找树如图73（2）。 74．
75．这里失败结点是不存在的结点，在其双亲结点处查找失败，这时的比较次数为Li-1。
76．
（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）本题中顺序检索好。
77．时间复杂度是判断检索方法的一个重要指标，但不是唯一指标。使用什么检索方法要综合考虑。哈希检索时间O（1），查找速度最快，但需构建哈希函数，进行计算哈希地址，查找时要有解决冲突的方法；二分检索时间O（log2n），需要元素有序且顺序存储，排序操作的时间开销大；顺时检索时间最差为O（n），但对检索表无要求，数据有序无序均可，在数据量较小时使用方便。
五．算法设计题
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个集合 {if（i<1 || i>id.k）printf（“无第%d个集合\\n”，i）；exit（0）；} if（i==1）first=0；else first=id.a[i-1]+1； //first指向第i个集合在数据表的首址 last= id.a[i]；//last是第i个集合在数据表中的末址 for（j=first；j≤last；j++） if（R[j]==x）return （j）；//查找成功 for（j=id.a[id.k]；j>id.a[i]；j--） //查找失败，将x插入数据表 R[j+1]=R[j]；//元素后移 R[j+1]=x； //将x插入到原第i个集合最后一个元素之后。 for（j=i；j≤k；j++）id.a[j]++；//修改索引表中各集合最后一个元素的下标 }结束SetSearch_Insert 由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入（2,11.2）和（1,5.3），数据表前后状态如下： 插0 入10.前 2 插10.入2 后 1 1.7 1.7 2 4.8 4.8 3 16.2 16.2 4 1.7 5.3 5 8.4 1.7 6 0.5 8.4 7 4.8 0.5 8 9 10 11 12 13 14 2.7 4.2 5.1 3.6 3.9 2.7 5.1 3.9 4.2 3.6 11.2 4.8 插入前,索引表中a数组的内容是3，6，12，插入后修改为4，8，14。 3．（1）非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。 void Creat_BST（BiTree bst，datatype K[]，int n） // 以存储在数组K中的n个关键字，建立一棵初始为空的二叉排序树。 {for（i=1；i≤n；i++） {p=bst；f=null；//在调用Creat_BST时，bst=null while（p!=null） if（p->data s=（BiTree）malloc（sizeof （BiNode））；// 申请结点空间 s->data=K[i]；s->LLINK=null；s->RLINK=null； if（f==null）bst=s； //根结点 else if（s->data else f->RLINK=s；//右子树根结点的值大于等于根结点的值 }//算法结束 （2）[题目分析]本题要求输出遍历二叉排序树的嵌套括号表示。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输出左括号，在输出其右子树前要输出逗号，在输出其右子树后要输出右括号，在左右子树均空情况下，则不输出括号。 void Print（BiTree t） //以嵌套括号表示结构打印二叉排序树 {if（t！=null） {printf（t->data）；//打印根结点值 if（t->LLINK || t->LLINK）；//左子女和右子女中至少有一个不空 {printf（“（”）； //输出左括号 Print（t->LLINK）； //输出左子树的嵌套括号表示 if（t->RLINK）printf（“，”）；//若右子树不空，输出逗号 Print（t->RLINK）； //输出右子树的嵌套括号表示 printf（“）”）； //输出右括号 }//if }}//Print 4． void Delete（BSTree t，p） // 在二叉排序树t中，删除f所指结点的右孩子（由p所指向）的算法 {if（p->lchild==null）{f->rchild=p->rchild；free（p）；} //p无左子女 else //用p左子树中的最大值代替p结点的值 {q=p->lchild；s=q； while（q->rchild）{s=q；q=q->rchild ；}//查p左子树中序序列最右结点 if（s==p->lchild） //p左子树的根结点无右子女 {p->data=s->data；p->lchild=s->lchild；free（s）；} else{p->data=q->data；s->rchild=q->lchild；free（q）；} } }//Delete 5．[题目分析]上题用被删结点左子树中最大值结点代替被删结点，本题用被删结点右子树中最小值（中序遍历第一个）结点代替被删结点。 void Delete(BSTree bst,p,fp) //在二叉排序树bst上，删除fp所指结点的左子女（由p所指向）的算法。 {if（!p->lchild）{fp->lchild=p->rchild；free（p）；} //p无左子女 else if（!p->rchild）{fp->lchild=p->lchild；free（p）；} //p无右子女 else // p有左子女和右子女 {q=p->rchild；s=q；//用p右子树中的最小值代替p结点的值 while（q->lchild）{s=q；q=q->lchild ；}//查p右子树中序序列最左结点 if（s==p->rchild） //p右子树的根结点无左子女 {p->data=s->data；p->rchild=s->rchild；free（s）；} else{p->data=q->data；s->lchild=q->rchild；free（q）；} }//Delete 6．[题目分析] 在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。 void Delete(BSTree bst, keytype X) //在二叉排序树bst上，删除其关键字为X的结点。 {BSTree f,p=bst; while (p && p->key!=X) //查找值为X的结点 if (p->key>X) {f=p; p=p->lchild;} else {f=p; p=p->rchild;} if (p==null) {printf(“无关键字为X的结点\\n”); exit(0);} if {p->lchild==null} //被删结点无左子树 if (f->lchild==p) f->lchild=p->rchild;//将被删结点的右子树接到其双亲上 else f->rchild=p->rchild; else {q=p; s=p->lchild; //被删结点有左子树