《数据结构》课后习题答案.doc 29页

'附录习题参考答案习题1参考答案1.1.选择题(1).A.(2).A.(3).A.(4).B.,C.(5).A.(6).A.(7).C.(8).A.(9).B.(10.)A.1.2.填空题(1).数据关系(2).逻辑结构物理结构(3).线性数据结构树型结构图结构(4).顺序存储链式存储索引存储散列表（Hash）存储(5).变量的取值范围操作的类别(6).数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7).关系网状结构树结构(8).空间复杂度和时间复杂度(9).空间时间(10).Ο(n)1.3名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述，是指令的有限序列。1.4语句的时间复杂度为：(1)Ο(n2)(2)Ο(n2)(3)Ο(n2)(4)Ο(n-1)(5)Ο(n3)1.5参考程序：main(){intX,Y,Z;scanf("%d,%d,%d",&X,&Y,&Z);if(X>=Y)if(X>=Z)if(Y>=Z){printf("%d,%d,%d",X,Y,Z);}else{printf("%d,%d,%d",X,Z,Y);} else{printf("%d,%d,%d",Z,X,Y);}elseif(Z>=X)if(Y>=Z){printf("%d,%d,%d",Y,Z,X);}else{printf("%d,%d,%d",Z,Y,X);}else{printf("%d,%d,%d",Y,X,Z);}}1.6参考程序：main(){inti,n;floatx,a[],p;printf("nn=");scanf("%f",&n);printf("nx=");scanf("%f",&x);for(i=0;i<=n;i++)scanf("%f",&a[i]);p=a[0];for(i=1;i<=n;i++){p=p+a[i]*x;x=x*x;}printf("%f",p);}习题2参考答案2.1选择题(1).C.(2).B.(3).B.(4).B.5.D.6.B.7.B.8.A.9.A.10.D.2.2.填空题(1).有限序列(2).顺序存储和链式存储(3).Ｏ(n)O(n)(4).n-i+1n-i(5).链式(6).数据指针(7).前驱后继(8).Ο(1)Ο(n)(9).s->next=p->next;p->next=s;(10).s->next2.3.解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…,（n-1）/2的元素交换，输出数组a的元素。 参考程序如下：main(){inti,n;floatt,a[];printf("nn=");scanf("%f",&n);for(i=0;i<=n-1;i++)scanf("%f",&a[i]);for(i=0;i<=(n-1)/2;i++){t=a[i];a[i]=a[n-1-i];a[n-1-i]=t;}for(i=0;i<=n-1;i++)printf("%f",a[i]);}2.4算法与程序：main(){inti,n;floatt,a[];printf("nn=");scanf("%f",&n);for(i=0;ia[0]{t=a[i];a[i]=a[0];a[0]=t;}printf("%f",a[0]);for(i=2;ia[1]{t=a[i];a[i]=a[1];a[1]=t;}printf("%f",a[0]);}2.5算法与程序：main(){inti,j,k,n;floatx,t,a[];printf("nx=");scanf("%f",&x);printf("nn=");scanf("%f",&n);for(i=0;ix)break;for(k=n-1;k>=i;i--)/*移动线性表中元素，然后插入元素x*/a[k+1]=a[k];a[i]=x;for(i=0;i<=n;i++)/*依次输出线性表中的元素*/printf("%f",a[i]);}2.6算法思路：依次扫描A和B的元素，比较A、B当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。有序表的合并算法：voidmerge(SeqListA,SeqListB,SeqList*C){inti，j，k；i=0；j=0；k=0；while(i<=A.last&&j<=B.last)if(A.data[i]<=B.data[j])C->data[k++]=A.data[i++]；elseC->data[k++]=B.data[j++]；while(i<=A.last)C->data[k++]=A.data[i++]；while(j<=B.last)C->data[k++]=B.data[j++]；C->last=k-1；}2.7算法思路：依次将A中的元素和B的元素比较，将值相等的元素赋给C，如此直到线性表扫描完毕，线性表C就是所求递增有序线性表。算法：voidmerge(SeqListA,SeqListB,SeqList*C){inti，j，k；i=0；j=0；k=0；while(i<=A.last)while（j<=B.last)if(A.data[i]=B.data[j])C->data[k++]=A.data[i++]；C->last=k-1； }习题3参考答案3.1.选择题(1).D(2).C(3).D(4).C(5).B(6).C(7).C(8).C(9).B(10).AB(11).D(12).B(13).D(14).C(15).C(16).D(17).D(18).C(19).C(20).C3.2.填空题（1）FILO,FIFO（2）-1,34X*+2Y*3/-（3）stack.top,stack.s[stack.top]=x（4）p>llink->rlink=p->rlink,p->rlink->llink=p->rlink（5）(R-F+M)%M（6）top1+1=top2（7）F==R（8）front==rear（9）front==(rear+1)%n（10）N-13.3答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”(pop)。3.4答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，一端(rear)插入。3.5答：可能序列有14种：ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA。3.6答：不能得到4，3，5，6，1，2，最先出栈的是4,则按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式进行push(1),pop(),push(2),push(3),pop(),push(4),push(5),pop(),pop(),pop(),push(6),pop()。3.7答：stack3.8非递归:intvonvert(intno,inta[])//将十进制数转换为2进制存放在a[]，并返回位数{intr;SeStacks,*p;P=&s;Init_stack(p);while(no){push(p,no%2);no/=10;} r=0;while(!empty_stack(p)){pop(p,a+r);r++;}returnr;}递归算法:voidconvert(intno){if(no/2>0){Convert(no/2);Printf(“%d”,no%2);}elseprintf(“%d”,no);}3.9参考程序：voidview(SeStacks){SeStack*p;//假设栈元素为字符型charc;p=&s;while(!empty_stack(p)){c=pop(p);printf(“%c”,c);}printf(”n”);}3.10答：char3.11参考程序：voidout(linkqueueq){inte;while(q.rear!=q.front){dequeue(q,e);print(e);//打印}} 习题4参考答案4.1选择题：(1).A(2).D(3).C(4).C(5).B(6).B(7).D(8).A(9).B(10).D4.2填空题：（1）串长相等且对应位置字符相等（2）不含任何元素的串，0（3）所含字符均是空格，所含空格数（4）10（5）“helloboy”（6）13（7）1066（8）模式匹配（9）串中所含不同字符的个数（10）364.3StrLength(s)=14,StrLength(t)=4,SubStr(s，8，7)=”STUDENT”,SubStr(t，2，1)=”O”,StrIndex(s,“A”)=3,StrIndex(s，t)=0,StrRep(s，“STUDENT”，q)=”IAMAWORKER”,4.4StrRep(s,”Y”,”+”);StrRep(s,”+*”,”*Y”);4.5空串：不含任何字符；空格串：所含字符都是空格串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的主串与子串：子串是主串的一个子集串变量的名字与串变量的值:串变量的名字表示串值的标识符4.6intEQUAl(S,T){char*p,*q;p=&S;q=&T;while(*p&&*q){if(*p!=*q)return*p-*q;p++;q++;}return*p-*q;}4.7(1)6*8*6=288(2)1000+47*6=1282(3)1000+(8+4)*8=1096 (4)1000+(6*7+4)*8=13684.8ijv1121215-132144347542665187539矩阵的三元组表习题5参考答案5.1选择（1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C（11）B（12）C（13）C（14）C（15）C（16）B5.2填空（1）1（2）1036；1040（3）2i（4）1；n;n-1;2（5）2k-1；2k-1（6）ACDBGJKIHFE（7）p!=NULL（8）Huffman树（9）其第一个孩子;下一个兄弟（10）先序遍历；中序遍历5.3叶子结点:C、F、G、L、I、M、K；非终端结点：A、B、D、E、J；各结点的度：结点：ABCDEFGLIJKM度：430120000100树深：45.4 无序树形态如下：二叉树形态如下：5.5二叉链表如下:ABC∧D∧E∧F∧G∧∧H∧∧I∧∧J∧三叉链表如下:∧A CBF∧∧G∧∧D∧E∧J∧∧I∧∧H∧5.6先序遍历序列:ABDEHICFJG中序遍历序列:DBHEIAFJCG后序遍历序列:DHIEBJFGCA5.7(1)先序序列和中序序列相同：空树或缺左子树的单支树；(2)后序序列和中序序列相同：空树或缺右子树的单支树；(3)先序序列和后序序列相同：空树或只有根结点的二叉树。5.8这棵二叉树为:5.9先根遍历序列:ABFGLCDIEJMK后根遍历序列:FGLBCIDMJKEA层次遍历序列:ABCDEFGLIJKM5.10证明：设树中结点总数为n，叶子结点数为n0，则n=n0+n1+……+nm（1）再设树中分支数目为B，则 B=n1+2n2+3n3+……+mnm（2）因为除根结点外，每个结点均对应一个进入它的分支，所以有n=B+1（3）将（1）和（2）代入（3），得n0+n1+……+nm=n1+2n2+3n3+……+mnm+1从而可得叶子结点数为：n0=n2+2n3+……+(m-1)nm+15.11由5.10结论得，n0=(k-1)nk+1又由n=n0+nk，得nk=n-n0，代入上式，得n0=(k-1)（n-n0）+1叶子结点数为：n0=n(k-1)/k5.12intNodeCount(BiTreeT){//计算结点总数if(T)if(T->lchild==NULL)&&(T-->rchild==NULL)return1;elsereturnNodeCount(T->lchild)+Node(T-->rchild)+1;elsereturn0;}5.13voidExchangeLR(Bitreebt){/*将bt所指二叉树中所有结点的左、右子树相互交换*/if(bt&&(bt->lchild||bt->rchild)){bt->lchild<->bt->rchild;Exchange-lr(bt->lchild);Exchange-lr(bt->rchild);}}/*ExchangeLR*/5.14intIsFullBitree(BitreeT){/*是则返回1，否则返回0。*/Init_Queue(Q);/*初始化队列*/flag=0;In_Queue(Q，T);/*根指针入队列，按层次遍历*/while(!Empty_Queue(Q)){Out_Queue(Q,p); if(!p)flag=1;/*若本次出队列的是空指针时，则修改flag值为1。若以后出队列的指针存在非空，则可断定不是完全二叉树*/elseif(flag)return0;/*断定不是完全二叉树*/else{In_Queue(Q，p->lchild);In_Queue(Q，p->rchild);/*不管孩子是否为空，都入队列。*/}}/*while*/return1;/*只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二叉树*/}/*IsFullBitree*/5.15转换的二叉树为：5.16对应的森林分别为： 5.17typedefcharelemtype;typedefstruct{elemtypedata;intparent;}NodeType;(1)求树中结点双亲的算法:intParent(NodeTypet[],elemtypex){/*x不存在时返回-2,否则返回x双亲的下标(根的双亲为-1*/for(i=0;i=MAXNODE)printf(“x不存在n”);else{flag=0;for(j=0;j=MAXNODE)return-2;/*x不存在*//*搜索x的双亲*/for(i=0;inextchild)if(loc==p->childcode)returni;/*返回x结点的双亲下标*/}/*ParentL*/(2)求树中结点孩子的算法:voidChildrenCL(NodeTypet[],elemtypex){for(i=0;inextchild){printf(“x的孩子:%cn”,t[p->childcode].data);flag=1;}if(flag==0)printf(“x无孩子n”);return;}/*if*/printf(“x不存在n”);return;}/*ChildrenL*/5.19 typedefcharelemtype;typedefstructTreeNode{elemtypedata;structTreeNode*firstchild;structTreeNode*nextsibling;}NodeType;voidChildrenCSL(NodeType*t,elemtypex){/*层次遍历方法*/Init_Queue(Q);/*初始化队列*/In_Queue(Q,t);count=0;while(!Empty_Queue(Q)){Out_Queue(Q,p);if(p->data==x){/*输出x的孩子*/p=p->firstchild;if(!p)printf(“无孩子n”);else{printf(“x的第%i个孩子:%cn”,++count,p->data);/*输出第一个孩子*/p=p->nextsibling;/*沿右分支*/while(p){printf(“x的第%i个孩子:%cn”,++count,p->data);p=p->nextsibling;}}return;}if(p->firstchild)In_Queue(Q,p->firstchild);if(p->nextsibling)In_Queue(Q,p->nextsibling);}}/*ChildrenCSL*/5.20(1)哈夫曼树为:692816941192210512743(2) 在上述哈夫曼树的每个左分支上标以1，右分支上标以0，并设这7个字母分别为A、B、C、D、E、F和H，如下图所示：则它们的哈夫曼树为分别为:A：1100B：1101C：10D：011E：00F：010H：111习题6参考答案6.1选择题（1）C（2）A（3）B（4）C（5）B______条边。（6）B（7）A（8）A（9）B（10）A（11）A（12）A（13）B（14）A（15）B（16）A（17）C6.2填空（1）4（2）1对多;多对多（3）n-1;n（4）0_（5）有向图（6）1（7）一半（8）一半（9）___第i个链表中边表结点数___（10）___第i个链表中边表结点数___（11）深度优先遍历；广度优先遍历（12）O（n2）（13）___无回路6.3 （1）邻接矩阵:（2）邻接链表：（3）每个顶点的度：顶点度V13V23V32V43V536.4（1）邻接链表：（2）逆邻接链表： （3）顶点入度出度V130V222V312V413V521V6236.5（1）深度优先查找遍历序列：V1V2V3V4V5;V1V3V5V4V2;V1V4V3V5V2（1）广度优先查找遍历序列：V1V2V3V4V5;V1V3V2V4V5;V1V4V3V2V56.6有两个连通分量：6.7顶点（1）（2）（3）（4）（5）LowCloseCostVexLowCloseCostVexLowCloseCostVexLowCloseCostVexLowCloseCostVexV10000000000V21000000000V31010000000V43021210101V5∞051322303U{v1}{v1,v2}{v1,v2,v3}{v1,v2,v3,v4}{v1,v2,v3,v4,v5} T{}{(v1,v2)}{(v1,v2),(v1,v3)}{(v1,v2),(v1,v3),(v2,v4)}{(v1,v2),(v1,v3),(v2,v4),(v4,v5)}最小生成树的示意图如下：6.8拓扑排序结果：V3àV1àV4àV5àV2àV66.9（1）建立无向图邻接矩阵算法：提示：参见算法6.1因为无向图的邻接矩阵是对称的，所以有for(k=0;ke;k++)/*输入e条边，建立无向图邻接矩阵*/{scanf("n%d,%d",&i,&j);G->edges[i][j]=G->edges[j][i]=1;}(2)建立无向网邻接矩阵算法:提示：参见算法6.1。初始化邻接矩阵：#defineINFINITY32768/*表示极大值*/for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=INFINITY;输入边的信息：不仅要输入边邻接的两个顶点序号，还要输入边上的权值for(k=0;ke;k++)/*输入e条边，建立无向网邻接矩阵*/{scanf("n%d,%d,%d",&i,&j,&cost);/*设权值为int型*/G->edges[i][j]=G->edges[j][i]=cost;/*对称矩阵*/}(3)建立有向图邻接矩阵算法:提示：参见算法6.1。6.10 (1)建立无向图邻接链表算法：typedefVertexTypechar;intCreate_NgAdjList(ALGraph*G){/*输入无向图的顶点数、边数、顶点信息和边的信息建立邻接表*/scanf("%d",&n);if(n<0)return-1;/*顶点数不能为负*/G->n=n;scanf("%d",&e);if(e<0)return=1;/*边数不能为负*/G->e=e;for(m=0;mn;m++)G->adjlist[m].firstedge=NULL;/*置每个单链表为空表*/for(m=0;mn;m++)G->adjlist[m].vertex=getchar();/*输入各顶点的符号*/for(m=1;m<=G->e;m++){scanf(“n%d,%d”,&i,&j);/*输入一对邻接顶点序号*/if((i<0||j<0)return-1;p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第i+1个链表中插入一个边表结点*/p->adjvex=j;p->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=p;p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第j+1个链表中插入一个边表结点*/p->adjvex=i;p->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=p;}/*for*/return0;/*成功*/}//Create_NgAdjList(2)建立有向图逆邻接链表算法：typedefVertexTypechar;intCreate_AdjList(ALGraph*G){/*输入有向图的顶点数、边数、顶点信息和边的信息建立逆邻接链表*/scanf("%d",&n);if(n<0)return-1;/*顶点数不能为负*/G->n=n;scanf("%d",&e);if(e<0)return=1;/*弧数不能为负*/G->e=e;for(m=0;mn;m++)G->adjlist[m].firstedge=NULL;/*置每个单链表为空表*/for(m=0;mn;m++)G->adjlist[m].vertex=getchar();/*输入各顶点的符号*/for(m=1;m<=G->e;m++){scanf(“n%d,%d”,&t,&h);/*输入弧尾和弧头序号*/if((t<0||h<0)return-1; p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第h+1个链表中插入一个边表结点*/p->adjvex=t;p->next=G->adjlist[h].firstedge;G->adjlist[h].firstedge=p;}/*for*/return0;/*成功*/}//Create_AdjList6.11voidCreate_AdjM(ALGraph*G1，MGraph*G2){/*通过无向图的邻接链表G1生成无向图的邻接矩阵G2*/G2->n=G1->n;G2->e=G1->e;for(i=0;in;i++)/*置G2每个元素为0*/for(j=0;jn;j++)G2->edges[i][j]=0;for(m=0;mn;m++)G2->vexs[m]=G1->adjlist[m].vertex;/*复制顶点信息*/num=（G1->n/2==0?G1->n/2:G1->n/2+1）;/*只要搜索前n/2个单链表即可*/for(m=0;madjlist[m].firstedge;while(p){/*无向图的存储具有对称性*/G2->edges[m][p->adjvex]=G2->edges[p->adjvex][m]=1;p==p->next;}}/*for*/}/*Create_AdjM*/6.12voidCreate_AdjL(ALGraph*G1，MGraph*G2){/*通过无向图的邻接矩阵G1，生成无向图的邻接链表G2*/G2->n=G1->n;G2->e=G1->e;for(i=0;in;i++)/*建立每个单链表*/{G2->vexs[i]=G1->adjlist[i].vertex;G2->adjlist[i].firstedge=NULL；for(j=i;jn;j++)/*对称矩阵，只要搜索主对角以上的元素即可*/{if(G1->edges[i][j]==1){p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第i+1个链表中插入一个边表结点*/p->adjvex=j;p->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=p;p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第j+1个链表中插入一个边表结点*/p->adjvex=i;p->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=p;}/*if*/}/*for*/ }/*for*/}/*Create_AdjL*/6.13(1)邻接矩阵中1的个数的一半;(2)若位于[i-1,j-1]或[j-1,i-1]位置的元素值等于1，则有边相连，否则没有。(3)顶点i的度等于第i-1行中或第i-1列中1的个数。6.14(1)邻接链表中边表结点的个数的一半;(2)若第i-1（或j-1）个单链表中存在adjvex域值等于j-1（或i-1）的边表结点，则有边相连，否则没有。(3)顶点i的度等于第i-1个单链表中边表结点的个数。6.15提示：参见算法6.2和6.3。习题7参考答案7.1选择题（1）C(2)C(3)C(4)B(5)A(6)A(7)D(8)B(9)D(10)B(11)B(12)A(13)C(14)C(15)A(16)D(17)C(18)B,C(19)B(20)A7.2填空题（1）O(n),O(log2n)（2）1,2,4,8,5,log2(n+1)-1（3）小于，大于（4）增序序列（5）,m-1（6）70;34,20,55（7）n/m（8）开放地址法，链地址法（9）产生冲突的可能性就越大，产生冲突的可能性就越小（10）关键码直接（11）②,①,⑦（12）16,16,8,21（13）直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法（14）开放地址法，再哈希法，链地址法，建立一个公共溢出区（15）装满程度（16）索引，快（17）哈希函数，装填因子（18）一个结点（19）中序（20）等于 7.3一棵二叉排序树(又称二叉查找树)或者是一棵空树，或者是一棵同时满足下列条件的二叉树：(1)若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。(2)若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。(3)它的左、右子树也分别为二叉排序树。7.4对地址单元d=H(K)，如发生冲突，以d为中心在左右两边交替进行探测。按照二次探测法，键值K的散列地址序列为：do=H(K)，d1=(d0+12)modm，d2=(d0-12)modm，d3=(d0+22)modm，d4=(d0-12)modm，……7.5衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找的场合。对于顺序查找，尽管效率不高，但却比较简单，常用于查找范围较小或偶而进行查找的情况。7.6此法要求设立多个散列函数Hi，i=1，…，k。当给定值K与闭散列表中的某个键值是相对于某个散列函数Hi的同义词因而发生冲突时，继续计算该给定值K在下一个散列函数Hi+1下的散列地址，直到不再产生冲突为止。7.7散列表由两个一维数组组成。一个称为基本表，另一个称为溢出表。插入首先在基本表上进行；假如发生冲突，则将同义词存人溢出表。7.8结点个数为n时，高度最小的树的高度为1，有两层，它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-l，有n层，它有1个叶结点，n-1个分支结点。7.9设顺序查找以h为表头指针的有序链表，若查找成功则返回结点指针p，查找失败则返回null值。pointersqesrearch(pointerh，intx，pointerp){p=null；while(h)if(x>h->key)h=h->link；else{if(x==h->key)p=h；return(p)；}}虽然链表中的结点是按从小到大的顺序排列的，但是其存储结构为单链表，查找结点时只能从头指针开始逐步进行搜索，故不能用折半(二分)查找。7.10 分析：对二叉排序树来讲，其中根遍历序列为一个递增有序序列。因此，对给定的二叉树进行中根遍历，如果始终能保证前一个值比后一个值小，则说明该二叉树是二叉排序树。intbsbtr(bitreptrT)／*predt记录当前结点前趋值，初值为-∞*／{if(T==NULL)return(1)；else{b1=bsbtr(T->lchild)；／*判断左子树*／if(!b1||(predt>=T->data))return(0)；*当前结点和前趋比较*／predt=T->data；／*修改当前结点的前趋值*／return(bsbtr(T->rchild))；／*判断右子树并返回最终结果*／}}7.11(1)使用线性探查再散列法来构造散列表如表下所示。散列表───────────────────────────────地址012345678910───────────────────────────────数据331131234382722───────────────────────────────（2）使用链地址法来构造散列表，如下图(3)装填因子a=8／11。使用线性探查再散列法查找成功所需的平均查找次数为Snl=0．5(1+1／(1-a))=0．5*(1+1／(1-8／11))=7／3使用线性探查再散列法查找不成功所需的平均查找次数为：Unl=0．5(1+1／(1-a)2)=0．5*(1+1／(1-8／11)2)=65／9使用链地址法查找成功所需的平均查找次数为：Snc=l+a／2=1+8／22=15／11使用链地址法查找不成功所需的平均查找次数为：‘Unl=a+e-a=8／1l+e-8／117.12分析：在等查区间的上、下界处设两个指针，由此计算出中间元素的序号，当中间元素大于给定值X时，接下来到其低端区间去查找；当中间元素小于给定值X时，接下来到其高端区间去查找；当中间元素等于给定值X时，表示查找成功，输出其序号。 Intbinlist(sqtableA，ints，t，keytypeX)／*t、s分别为查找区间的上、下界*／{if(sA.item[mid].key：return(a，mid+l，t，X))；／*在高端区间上递归*／}}}7.13intsqsearch0(sqtableA，keytypeX)/*数组有元素n个*／{i=l；A.item[n+1].key=X；／t设置哨兵*／while(A.item[n+1].key!=X)i++；return(i%(n／1))；／*找不到返回0，找到返回其下标*／}查找成功平均查找长度为：(1+2+3+…+n)／n：(1+n)／2。查找不成功平均查找长度为：n+1。7.14散列函数：H(key)=100+(key个位数+key十位数)modl0；形成的散列表：100101102103104105106107108109987563464979615317查找成功时的平均长度为：(1+2+1+1+5+1+1+5+5+3)/10=2.5次。由于长度为10的哈希表已满，因此在插人第11个记录时所需作的比较次数的期望值为10，查找不成功时的平均长度为10。习题8参考答案8．1选择题（1）B(2)A(3)D(4)C(5)B(6)A(7)B(8)C(9)A(10)C(11)D(12)C(13)C（14）D（15）C(16)B(17)D（18）C（19）B（20）D8.2填空题（1）快速，归并（2）O（log2n）,O(nlog2n)（3）归并（4）向上，根结点（5）19，18，16，20，30，22 192318162030（6）192318162030（7）49，13，27，50，76，38，65，97（8）8，8（9）插入，选择（每次选择最大的）（10）快速，归并(11)O(1),O(nlog2n)(12)稳定(13)3(14)(15,20,50,40)(15)O(log2n)(16)O(n2)(17)冒泡排序,快速排序(18)完全二叉树,n/2(19)稳定,不稳定(20)2,4,(20,40,15)8.3.假定给定含有n个记录的文件(r1，f2，…，rn)，其相应的关键字为(k1，k2，…，kn)，则排序就是确定文件的一个序列rr，r2，，…，rn，，使得k1"≤k2"≤…≤kn"，从而使得文件中n个记录按其对应关键字有序排列。如果整个排序过程在内存中进行，则排序叫内部排序。假设在待排序的文件中存在两个或两个以上的记录具有相同的关键字，若采用某种排序方法后，使得这些具有相同关键字的记录在排序前后相对次序依然保持不变，则认为该排序方法是稳定的，否则就认为排序方法是不稳定的。8.4．稳定的有：直接插入排序、二分法插入排序、起泡排序、归并排序和直接选择排序。8.5．初始记录序列按关键字有序或基本有序时，比较次数为最多。8.6．设5个元素分别用a，b，c，d，e表示，取a与b、c与d进行比较。若a>b，c>d(也可能是ad则a>b>d，若bd>b，此时已进行了3次比较，要使排序比较最多7次，可把另外两个元素按折半检索排序插入到上面所得的有序序列中，此时共需要4次比较。从而可得算法，共只需7次比较。8.7．题目中所说的几种排序方法中，其排序速度都很快，但快速排序、归并排序、基数排序和Shell排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连续位置上的最终元素。而堆排序则是每次输出一个堆顶元素(即最大或最少值的元素)，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小的，从而可知，欲在一个大量数据的文件中，如含有15000个元素的记录文件中选取前10个最大的元素，可采用堆排序进行。 8.8．二分法排序。8.9．voidinsertsort(seqlistr) ；{／／对顺序表中记录R[0一N—1)按递增序进行插入排序&NBSP；inti，j； ；for(i=n-2；i>=0;i--)／／在有序区中依次插入r[n-2]．．r[0] ；if(r[i].key>r[i+1].key)／／若不是这样则r[i]原位不动 ；{ ；r[n]=r[i]；j=i+l；／／r[n]是哨兵 ；do{／／从左向右在有序区中查找插入位置 ；r[j-1]=r[j]；／／将关键字小于r[i]．key的记录向右移 ；j++； ；}whle(r[j].keyr[j-1]=r[n]；／／将引i)插入到正确位置上 ；}／／endif ；}／／insertsort． ；8.10．建立初始堆：[9376948632654387517421290753011]&NBSP；&NBSP；第一次排序重建堆：[863694751765438301742129075]9378.11．在排序过程中，每次比较会有两种情况出现，若整个排序过程至少需作t次比较，则显然会有2^t个情况，由于n个结点总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是：2t≥n!即t≥log2n!因为log2nl=nlog2n-n／ln2+log2n／2+O(1)故有log2n!≈nlog2n从而t≧nlog2n得证。8.12．依据堆定义可知：序列(1)、(2)、(4)是堆，(3)不是堆，从而可对其调整使之为如下的大根堆(100，95，80，60，40，95，82，10，20)。8.13．第一趟：[265301][129751][863937][694742][076438]&NBSP；&NBSP；第二趟：[129265301751][694742863937][076438]&NBSP；&NBSP；第三趟：[129265301694742751863937][076438]&NBSP；&NBSP；第四趟：[076129265301438694742751863937]&NBSP；8.14．(1)归并排序：(18，29)(25，47)(12，58)(10，51)(18，25，29，47)(10，12，51，58)(10，12，18，25，29，47，51，58)(2)快速排序：(10，18，25，12，29，58，51，47)(10，18，25，12，29，47，51，58) (10，12，18，25，29，47，51，58)(3)堆排序：初始堆(大顶堆)：(58，47，51，29，18，12，25，10)第一次调整：(51，47，25，29，18，12，10)(58)第二次调整：(47，29，25，10，18，12)(51，58)第三次调整：(29，18，25，10，12)(47，51，58)第四次调整：(25，18，12，10)(29，47，51，58)第五次调整：(18，10，12)(25，29，47，51，58)第六次调整：(12，10)(18，25,29,47,51,58)第七次调整：(10，12,18,25,29,47,51,58)8.15．(1)直接插入排序。序号123456789101112关键字8340631384359657397961151=24083[63138435965739796115]1=3406383[138435965739796115]1=413406383[8435965739796115]I=51340638384[35965739796115]I=6133540638384[965739796115]1=713354063838496[5739796115]1=81335405763838496[39796115]1=9133539405763838496[796115]I=1013353940576379838496[6115]I=111335394057616379838496[15]1=12131535394057616379838496(2)直接选择排序。序号123456789101112关键字834063138435965739796115i=113[4063838435965739796115]i=21315[63838435965739796140]i=3131535[838463965739796140]i=413153539[8463965783796140]i=51315353940[63965783796184]i=6131535394057[966383796184]i=713153539405761[6383799684]i=81315353940576163[83799684]i=91315353940576163791839684]i=1013153539405761637983[9684]i=111315353940576163798384[96](3)快速排序。关键字834063138435965739796115第一趟排序后[154063136135795739]83[9684]第二趟排序后[13]15[63406135795739]8384[96]第三趟排序后1315[3940613557]63[79]838496 第四趟排序后1315[35]39[614057]6379838496第五趟排序后13153539[5740]616379838496第六趟排序后1315353940[57]616379838496第七趟排序后131535394057616379838496(4)堆排序。关键字834063138435965739796115排序成功的序列968483796361574039351513(5)归并排序。关键字834063138435965739796115第一趟排序后[4083][1363][35，84][5796][3979][1561]第二趟排序后[13406383][35578496][15396179]第三趟排序后[1335405763838496]][15396179]第四趟排序后131535394057616379838496'