高等学校——数据结构习题答案.doc 49页

'第一章1、简述下列术语：数据元素、数据、数据对象、数据结构、存储结构和算法解：数据元素：数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。数据：信息的载体。是描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。数据对象：性质相同的数据元素的集合，是数据的一个子集。数据结构：相互之间存在着一种或多种关系的数据元素的集合，包括数据的逻辑结构和物理结构两方面的内容。存储结构：数据的逻辑结构在计算集中的表示方式，包含顺序存储方法、链接存储方法、索引存储方法、散列存储方法。算法：对特定问题求解步骤的一种描述，它是指令或语句的有限序列，并具有有穷型、确定性、可行性、输入和输出五个重要特性。2、试写一算法，自大至小依次输出顺序读入的三个整数x，y和z的值解：voidf1(void){intx,y,z;printf("enterx,y,z:");scanf("%d,%d,%d",&x,&y,&z);if(x>y)if(y>z)printf("%d,%d,%d",x,y,z);elseif(x>z)printf("%d,%d,%d",x,z,y);elseprintf("%d,%d,%d",z,x,y);elseif(x>z)printf("%d,%d,%d",y,x,z);elseif(z>y)printf("%d,%d,%d",z,y,x);elseprintf("%d,%d,%d",y,z,x); }3、举出一个数据结构的例子，叙述其逻辑结构、存储结构、运算等三方面的内容解：4、分析下列算法的时间复杂度：（1）intprime(intn){for(i=2;ilen==0)return-1;/*表已空*/while(i<=L->len)if(L->elem[i]=x){for(j=i;j<=L->len-1;j++)L->elem[j]=L->elem[j+1];/*被删除元素之后的元素左移*/--L->len;}elsei++;return1;}4、设线性表(a1，a2，…，an)存储在带表头结点的单链表中，试设计算法，求出该线性表中值为x的元素的序号。如果x不存在，则序号为0。intIndex_Linkst(LNode*H,ELEMTPx){p=H->next;j=1;f=0;/*P指向第一个结点，j为计数器，f为标志*/while(p){if(p->data!=x){j++;p=p->next;}elsef=1;}if(f=1)returnj; elsereturn0;}5、在一个非递减有序线性表中，插入一个值为x的元素，使插入后的线性表仍为非递减有序。分别写出用顺序表和单链表表示时的算法。顺序表：intInsert_Sq(SqList*L,ELEMTPx){if(L->len==MAXSIZE-1)return-1;/*表已满*/if(x>=L->elem[L->len]){L->elem[L->len+1]=x;L->len+=1;}else{i=1;while(x>=L->elem[i])i++;for(j=L->len;j>=i;j--)L->elem[j+1]=L->elem[j];L->elem[i]=x;L->len+=1;}return1;}单链表：intInsert_Linkst(LNode*H,ELEMTPx){p=H;s=(LNode*)malloc(sizeof(LNode));if(s){s->data=x;s->next=NULL;}elsereturn0;while(p->next)if(p->next->datanext; else{s->next=p->next;p->next=s;/*插入*/return1;}/*Insert_Linkst*/p->next=s;return1;}6、设一个线性表L=(a1，a2，…，an)，编写算法将其逆置，即成为（an，an-1，…a2，a1）。要求逆置后的线性表仍占用原来的存储空间，并且用顺序和单链表两种方法表示，写出不同的处理过程。顺序表：voidinverse_Sq(SqList*L）{inti;ELEMTPx;for(i=1;i<=L->len/2;i++){x=L->elem[i];L->elem[i]=L->elem[L->len-i+1];L->elem[L->len-i+1]=x;}}单链表：voidinverse_Linkst(LNode*H）{d=h->next;if(d!=NULL){p=d->next;while(p){t=p->next;p->next=d;d=p;p=t;}h=d;}} 7、设两个单链表A和B，它们的数据元素分别为(x1，x2，…,xm)和(y1，y2，…，yn)。设计一个算法将它们合并为一个单链表C，使得：当m≥n时，C＝(x1，y1，x2，y2，...，xn，yn，...,xm)当n＞m时，C＝(y1，x1，y2，x2，...，ym，xm，...,yn)。LNode*Link_Linkst(LNode*A,LNode*B){p=A->next;q=B->next;m=0;n=0;while(p){m++;p=p->next;}while(q){n++;q=q->next;}if(m>=n){p=A->next;q=B->next;C=A;}else{p=B->next;q=A->next;C=B;}while(q){t=p->next;p->next=q;q=q->next;p->next->next=t;p=t; }returnC;}8、试写一算法，在无表头结点的单链表中值为a的结点前插入一个值为b的结点,如果a不存在，则把b插在表尾。将该算法与第2.3.2节中的算法2．7进行比较。voidInsertx_Linkst(LNode*H,Elemtpa,Elemtpb){s=(LNode*)malloc(sizeof(LNode));s->data=b;s->next=NULL;if(H==NULL){H=s;}else{p=H;q=p->next;if(p->data==a)/*对首元节点处理*/{s->next=p;H=s;}else{while(q&&q->data!=a){p=q;q=q->next;}p->next=s;s->next=q;}}}9、假设有一个单向循环链表，其结点包含三个域：data，pre和next，其中data为数据域，next为指针域，其值为后继结点的地址，pre也为指针域，其初值为空（NULL），试设计算法将此单向循环链表改为双向循环链表。voidChange_Linkst(LNode*H) {q=H;p=H->next;while(p){p->pre=q;q=p;p=p->next;}H->pre=q;q->next=H;}10、已知二维数组A[5][7]，其每个元素占四个存储单元，且A[0][0]的存储地址为1100，试求出元素A[3][5]的存储地址（分别讨论以行为序和以列为序方式存储时的结论）。行为序1100+4*(3*7+5)=1204列为序1100+4*(5*5+3)=121211、设有一个二维数组A[M][N]，对以下三种情况分别编写算法：（1）求数组A的最外围元素之和；（2）求从A[0][0]开始的互不相邻的各元素之和；（3）当M=N时，分别求两条对角线上的元素之和，否则输出M≠N的信息。intA1(intA[M][N])/*求数组A的最外围元素之和*/{s=0;for(i=0;im&&j<=B->m)/*若A的当前项的行号等于B当前项的行号，则比较其列号，将较小列号的项放入C，如果列号也相等，相加后放入C；*/if(A->elem[i].i==B->elem[j].i)if(A->elem[i].jelem[j].j){C->elem[k].i=A->elem[i].i;C->elem[k].j=A->elem[i].j;C->elem[k].v=A->elem[i].v;k++;i++;}elseif(A->elem[i].j>B->elem[j].j){C->elem[k].i=B->elem[j].i;C->elem[k].j=B->elem[j].j;C->elem[k].v=B->elem[j].v;k++;j++; }else{C->elem[k].i=B->elem[j].i;C->elem[k].j=B->elem[j].j;C->elem[k].v=B->elem[j].v+A->elem[i].v;k++;j++;i++;}elseif(A->elem[i].ielem[j].i){/*若A当前项的行号小于B当前项的行号，则将A项放入C*/C->elem[k].i=A->elem[i].i;C->elem[k].j=A->elem[i].j;C->elem[k].v=A->elem[i].v;k++;i++;}else{/*若A当前项的行号大于B当前项的行号，则将B项放入C*/C->elem[k].i=B->elem[j].i;C->elem[k].j=B->elem[j].j;C->elem[k].v=B->elem[j].v;k++;j++;}C->m=A->m;/*C的行数*/C->n=A->n;/*C的列数*/C->t=k-1;/*C的非零元个数*/}14、设稀疏矩阵A用十字链表表示，编写算法查找元素：（1）已知i，j，查找A[i][j]；（2）已知x的值，查找它在第几行第几列。解：（1）intfindmat(CrossList*M,inti,intj,int*val){if(i<=M->mu&&i>0){p=M->rhead[i];while(p) {if(p->col==j){*val=p->val;return1;/*找到*/}elsep=p->right;}return0;/*未找到*/}elsereturn-1;/*行号错误*/}（2）intfindmat(CrossList*M,intx,int*rown,int*coln){for(inti=1;i<=M->mu;i++){p=M->rhead[i];while(p){if(p->val==x){*rown=p->row;*coln=p->col;return1;}elsep=p->right;}}return0;}上机实习题1.设A=（a1,a2,…,an）和B=（b1,b2,…,bm）是两个线性表，其数据类型是整型。若n=m且ai=bi(1≤i≤n),则称A=B；若ai=bj（1≤i＜j），而aj＜bj(j＜n≤m),则称A＜B；除此以外，均称A=B。设计一个比较A、B大小的程序。#include#defineMAXSIZE100typedefstruct {intelem[MAXSIZE];/*存储线性表中的元素*/intlen;/*线性表的当前表长*/}SqList;SqList*InitList(SqList*L){L=(SqList*)malloc(sizeof(SqList));L->len=0;returnL;}intInsert(SqList*L,inti,intx){intj;if(i<1||i>L->len+1)return0;/*不合理的插入位置i*/if(L->len==MAXSIZE-1)return-1;/*表已满*/for(j=L->len;j>=i;--j)L->elem[j+1]=L->elem[j];/*插入位置及之后的元素右移*/L->elem[i]=x;/*插入x*/++L->len;/*表长加1*/return1;}intf(SqList*A,SqList*B){SqList*As=NULL,*Bs=NULL;inti=1,j,ms=0,ns=0;As=InitList(As);Bs=InitList(Bs);while(A->elem[i]==B->elem[i])i++;for(j=i;j<=A->len;j++)Insert(As,j-i+1,A->elem[j]);for(j=i;j<=B->len;j++)Insert(Bs,j-i+1,B->elem[j]);ms=As->len;ns=Bs->len;if(ms==ns&&ms==0)return0;elseif(ms==0&&ns>0||(ms>0&&ns>0&&As->elem[1]elem[1]))return-1; elsereturn1;}intmain(){SqList*A=NULL,*B=NULL;intn=0,m=0,i=0,d=0;A=InitList(A);B=InitList(B);if(A!=B)printf("A!=B");elseprintf("A=B");printf("nInputn:");scanf("%d",&n);for(i=1;i<=n;i++){printf("a%d:",i);scanf("%d",&d);Insert(A,i,d);}for(i=1;i<=A->len;i++)printf("%d",A->elem[i]);printf("n");printf("nInputm:");scanf("%d",&m);for(i=1;i<=m;i++){printf("b%d:",i);scanf("%d",&d);Insert(B,i,d);}for(i=1;i<=B->len;i++)printf("%d",B->elem[i]);printf("n");printf("n");for(i=1;i<=A->len;i++)printf("%d",A->elem[i]);printf("n");for(i=1;i<=B->len;i++)printf("%d",B->elem[i]); i=f(A,B);if(i==0)printf("A=B");elseif(i<0)printf("AB");return0;}2.设计一个程序求出约瑟夫环的出列顺序。约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。例如n=7,7个人的密码依次为：3，1，7，2，4，8，4，m的初值取6，则正确的出列顺序应为6，1，4，7，2，3，5。要求使用单向循环链表模拟此出列过程。#includetypedefstructnode{intdata;structnode*next;intid;}LNode;LNode*insert(LNode*rear,intx,intid){LNode*s;s=(LNode*)malloc(sizeof(LNode));s->data=x;s->id=id;if(rear==NULL){rear=s;s->next=s;returnrear;} else{s->next=rear->next;rear->next=s;rear=s;returnrear;}}intmain(){LNode*rear=NULL,*p=NULL,*q=NULL;intd,m,i=1;printf("input:");scanf("%d",&d);while(d!=0){rear=insert(rear,d,i++);printf("ninput:");scanf("%d",&d);}p=rear->next;/*显示数据*/while(p!=rear){printf("%d",p->data);p=p->next;}printf("%d",p->data);printf("inputm:");/*输入初始m*/scanf("%d",&m);p=rear;while(p!=p->next){for(i=1;inext;q=p->next;p->next=q->next;m=q->data;printf("%d",q->id);free(q); }printf("%d",p->id);free(p);return0;}第三章习题l．假定有编号为A、B、C的3辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序(注：每一列车由站台开出时均可进栈，出栈开出站台，但不允许出栈后回退)。写出每一种可能的序列。解：产生：ABC、ACB、BAC、BCA、CBA不会产生：CAB2．有字符串次序为5*-y-a/y↑2，试利用栈排出将次序改变为5y-*ay↑/-的操作步骤（可用X代表扫描该字符串过程中顺序取一字符进栈的操作，用S代表从栈中取出一字符加到新字符串尾的出栈的操作）。例如，ABC变为BCA的操作步骤为XXSXSS。解：XSXXXSSSXXSXXSXXSSSS3．写出链栈的取栈顶元素和置栈空的算法。解：（1）intGetTop(SNode*top,ELEMTP*Y){if(top==NULL)return-1else*y=top->data;return1;}（2）SNode*Empty(SNode*top){while(top){ p=top;top=top->next;free(p);}returnNULL;}4．假设一个算术表达式中包含圆括弧、方括弧和花括弧，编写一个判别表达式中括弧是否正确配对的算法。解：intf(){InitStack(p);Push(p,"#");c=getchar();while(c!="#"||GetTop(p)!="#"){if(c=="("||c=="["||c=="{")Push(p,c);if(c==’)’){Pop(p,o);if(o!=’(’)return-1;}if(c==’]’){Pop(p,o);if(o!=’[’)return-1;}if(c==’}’){Pop(p,o);if(o!=’{’)return-1;}c=getchar();}return1;}5．写出计算表达式5+3*4/6-7时操作数栈和运算符栈的变化情况。解：步骤OPTROPND输入字符1#5+3*4/6-7# 2#5+3*4/6-7#3#+53*4/6-7#4#+5，3*4/6-7#5#+*5，34/6-7#6#+*5，3，4/6-7#7#+5，12/6-7#8#+/5，126-7#9#+/5，12，6-7#10#+5，2，-7#11#7-7#12#-77#13#-7，7#14#0#6．对于给定的十进制正整数，打印出对应的八进制正整数。(1)写出递归算法。(2)写出非递归算法。解：intf(intn)/*递归算法*/{if(n<8)printf("%d",n);else{f(n/8);printf("%d",n%8);}}voidf(intn)/*非递归算法*/{InitStack(p);/*初始化栈*/do{Push(p,n%8);n=n/8;}while(n);while(!Empty(p)){Pop(p,o);printf("%d",o); }}7．已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非递归算法。n+1当n＝0时f(n)＝n*f(n/2)当n≠0时解：intf(intn)/*递归*/{if(n==0)return1;elsereturnn*f(n/2);}intf(intn)/*非递归*/{intstack[MAXLEN][3];inttop=1,fval;stack[top][1]=n;/*初值入栈*/while(n!=0)/*存入所有的n/2*/{top++;n/=2;stack[top][1]=n;}stack[top][0]=1;while(top>1)/*退栈求值*/{fval=stack[top][0];top--;stack[top][2]=fval;stack[top][0]=stack[top][1]*stack[top][2];}return(stack[top][0]);}8．对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。解：(sq.front-sq.rear+m)%m 9．假设用一个数组Q[M]来表示队列，该队列只设一个队头指针front，不设队尾指针而改设计数器count用以记录队列中元素的个数。试编写出相应的置空队列，入队列和出队列的算法。解：typedefstruct{ELEMTPelem[MAXSIZE];intfront;/*队头*/intcount;}MySqQueue;voidEmpty(MySqQueue*Sq)/*置空队列*/{Sq->front=0;Sq->count=0;}intEnQueue(MySqQueue*Sq，ELENTPx)/*在循环队列Sq的尾部插入一个新的元素x*/{if(Sq->count==MAXSIZE)return-1;/*队列上溢*/else{Sq->count++;Sq->elem[(Sq->front+Sq->count)%MAXSIZE]=x;}return1;}intDelQueue(MySqQueue*Sq，ELEMTP*y)/*删除循环队列Sq的队头元素，并存人*y中*/{if(Sq->count==0)return-1;/*队列下溢*/else{Sq->front=(Sq->front+1)%MAXSIZE;*y=Sq->elem[Sq->front];Sq->count--;}return1;} 10．假设以带头结点的循环链表示列队，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写出相应的置空队列，入队列和出队列的算法。解：typedefstructnode{/*结点结构*/ELEMTPdata;structnode*next;}QNode;typedefstruct{QNone*rear;/*队尾指针*/}MyLQueue;voidEmpty(MyLQueue*Lq)/*置空队列*/{if(Lq->rear!=NULL)/*循环队列为非空*/{head=Lq->rear->next;while(head!=Lq->rear){p=head;head=head->next;free(p);}free(head);Lq->rear=NULL;}}intEnQueue(MyLQueue*Lq，ELENTPx)/*在循环队列Sq的尾部插入一个新的元素x*/{p=(QNone*)malloc(sizeof(QNone));if(p==NULL)return-1;else{p->data=x;p->next=NULL;if(Lq->rear==NULL)/*循环队列为空*/{Lq->rear=p;p->next=p; }else{head=Lq->rear->next;Lq->rear->next=s;Lq->rear=s;s->next=head;}}return1;}intDelQueue(MyLQueue*Lq，ELEMTP*y)/*删除循环队列Sq的队头元素，并存人*y中*/{if(Lq->rear==NULL)/*队列下溢*/return-1;else{head=Lq->rear->next;if(head==Lq->rear)/*只有一个节点*/{*y=head->data;free(head);Lq->rear=NULL;}else{*y=head->data;Lq->rear->next=head->next;free(head);}}return1;}上机实习题1．设计一个算法，检验C源程序代码中的括弧对是否正确配对。要求在某个C源程序文件上对你的算法进行验正。#includetypedefstructnode{chardata;structnode*next; }SNode;SNode*Push(SNode*top,charx){SNode*p;p=(SNode*)malloc(sizeof(SNode));p->data=x;p->next=top;top=p;returntop;}SNode*Pop(SNode*top,char*y,int*flag){SNode*p;if(top==NULL)*flag=0;/*链栈已空*/else{/*出栈*/p=top;*y=p->data;top=p->next;*flag=1;}returntop;}intmain(intargc,char*argv[]){FILE*fp;charch,o;intflag=1;SNode*p=NULL;if(argc!=2){printf("Youforgottoenterthefilenamen");exit(1);}if((fp=fopen(argv[1],"r"))==NULL){printf("cannotopenfilen");exit(1);}ch=getc(fp); while(ch!=EOF){if(ch=="("||ch=="["||ch=="{"){printf("Push%cn",ch);p=Push(p,ch);}if(ch==")"){p=Pop(p,&o,&flag);printf("):Pop%c,%dn",o,flag);if(flag==0)printf("dlose"("");elseswitch(o){case"(":break;case"[":printf("lose"]"");exit(0);case"{":printf("lose"}"");exit(0);}}if(ch=="]"){p=Pop(p,&o,&flag);printf("[:Pop%c,%dn",o,flag);if(flag==0)printf("dlose"["");elseswitch(o){case"(":printf("lose")"");exit(0);case"[":break;case"{":printf("lose"}"");exit(0);}}if(ch=="}"){p=Pop(p,&o,&flag);printf("{:Pop%c,%dn",o,flag);if(flag==0)printf("dlose"{"");elseswitch(o) {case"(":printf("lose")"");exit(0);case"[":printf("lose"]"");exit(0);case"{":break;}}ch=getc(fp);}p=Pop(p,&o,&flag);if(flag==0)printf("OK");while(flag!=0)/*如果栈未空*/{switch(o){case"(":printf("lose")"");break;case"[":printf("lose"]"");break;case"{":printf("lose"}"");break;}p=Pop(p,&o,&flag);}fclose(fp);return0;}2．设计程序，模拟手机的某些短信息功能。功能要求：（1）接受短信息，若超过存储容量（如最多可存储20条），自动将最早接受的信息删除。（2）显示短信息数量。（3）逐条显示短信息（从最新的开始）；（4）删除其中的任意一条短信息；（5）清除。/*（1）接受短信息，若超过存储容量（如最多可存储20条），自动将最早接受的信息删除。（2）显示短信息数量。（3）逐条显示短信息（从最新的开始）；（4）删除其中的任意一条短信息；（5）清除。*/ #include#include#include#defineMAXSIZE20/*存储容量*/#defineINFOLEN100/*信息长度*/typedefstructnode{/*结点结构*/charInfo[INFOLEN];structnode*next;}QNode;typedefstruct{QNode*front;/*队头指针*/QNode*rear;/*队尾指针*/intcount;}MyInfo;MyInfo*Init()/*初始化*/{MyInfo*p;QNode*q;p=(MyInfo*)malloc(sizeof(MyInfo));p->count=0;q=(QNode*)malloc(sizeof(QNode));q->next=NULL;p->front=q;p->rear=q;returnp;}intGetNew(MyInfo*Lq)/*获得新短信*/{time_tt;structtm*local;QNode*p;t=time(NULL);local=localtime(&t);/*获得时间信息，模拟短信内容*/if(Lq->count==MAXSIZE){ Delete(Lq);}p=(QNode*)malloc(sizeof(QNode));strcpy(p->Info,asctime(local));p->next=NULL;Lq->rear->next=p;Lq->rear=p;Lq->count++;return1;}intDelete(MyInfo*Lq)/*删除循环队列Lq的队头元素*/{QNode*p;if(Lq->front==Lq->rear)return0;p=Lq->front->next;/*p指向新的队头结点*/Lq->front->next=p->next;if(Lq->rear==p)Lq->rear=Lq->front;/*尾指针指向头结点*/free(p);Lq->count--;return1;}intDeleteI(MyInfo*Lq,inti)/*删除循环队列Lq的第i个元素*/{QNode*p,*q;intn=1;if(Lq->front==Lq->rear||i<0||i>Lq->count)return0;p=Lq->front;while(nnext;n++;}q=p->next;p->next=q->next;if(Lq->rear==q)Lq->rear=p;/*尾指针指向前结点*/free(q);Lq->count--;return1; }voidEcho(MyInfo*Lq,inti)/*显示第i条短信*/{QNode*p=Lq->front->next;intn=1;if(i>0&&i<=Lq->count){while(nnext;n++;}printf("message%dof%d:%sn",i,Lq->count,p->Info);}}voidRemove(MyInfo*Lq){while(Lq->front!=Lq->rear)Delete(Lq);}voidPrintHlp(){printf("nnnn");printf("============================================================n");printf("====pressGtogetnewmessage====n");printf("====pressEtoEchomessage====n");printf("====pressDtodeleteamessage====n");printf("====pressPtodeletelastmessage====n");printf("====pressRtoremoveall====n");printf("====----------------------------------------------------====n");printf("========n");printf("====pressQtoQuit====n");printf("========n");printf("============================================================n");printf("nnnn");}intmain(){charc; MyInfo*p;inti;p=Init();PrintHlp();c=getch();while(c!="q"&&c!="Q"){switch(c){case"g":/*获得新消息*/case"G":GetNew(p);break;case"e":/*显示消息*/case"E":for(i=1;i<=p->count;i++)Echo(p,i);break;case"d":/*删除当前消息*/case"D":printf("inputi:");scanf("%d",&i);DeleteI(p,i);break;case"p":/*删除最先的纪录*/case"P":Delete(p);break;case"r":/*清楚所有消息*/case"R":Remove(p);break;}c=getch();PrintHlp();}Remove(p);return0;}第四章ABDJIEKHGFC题图4-1树T1．有一棵树如题图4-1所示，求出树的叶子结点、非终端结点、各结点的度、树的度和树深。解：（1）叶子结点：E、F、G、H、K、J（2）非终端结点：A、B、C、D、I（3）各结点的度：度为3的结点：A、C度为2的结点：D度为1的结点：B、I度为0的结点：E、F、G、H、K、J（4）树的度：3（5）树深：42．具有三个结点的二叉树有多少种不同的形态?请分别画出。解：具有三个结点的二叉树有5种不同的形态，如下所示： 3．如果一棵树有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，则该树共有多少个叶子结点?可参考二叉树性质3的证明方法来思考m叉树问题。解:设树中有n0个叶子结点，那么树中总结点数N为：N＝n0+n1+…+nm（a）由于树中除根结点外，其它各结点都有仅有一个分支指向它，所以树中的总结点数恰好比分支数少1。设B为树中总分支数，即有：B＝N-1另外，除度为0的结点没有分支外，每个度为k的结点有k个分支，所以总分支数又为：B＝1×n1+2×n2+…+m×nm即总结点数为：N＝n1+2×n2+…+m×nm+1（b）由式(a)和式(b)有：n0+n1+…+nm＝n1+2×n2+…+m×nm+1即得：n0＝1×n2+2×n3+…+（i-1）×ni+（m-1）×nm+1＝∑（i-1）×ni+1（i=2～m）4．写出按层遍历二叉树的算法。解：二叉链表结点结构描述为：typedefstructbtnode{ELEMTPdata;/*数据域*/structbtnode*lchild,*rchild;/*左、右孩子指针域*/}BTNode;voidLevorder(BTNode*bt){/*按层次遍历二叉树bt非递归算法，Q是BTNode*类型的队列*/InitQueue(Q);/*初始化队列Q*/if(bt){EnQueue(Q,bt);/*根结点入队列*/while(！QueueEmpty(Q)){/*队列非空*/DelQueue(Q,&p);/*队头元素存入变量p中*/Visit(p->data);/*访问根结点*/if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}}/*Levorder*/ 5．设计算法求二叉树中度为1的结点数。解：设置一个初始值为0的全局变量Count进行计数，在对二叉树进行遍历的过程中判断当前所访问的结点是否为度为1的结点，若是则Count加1。因此当遍历完整个二叉树后，count的值就是度为1的结点的数目。算法描述如下：intCount=0;voidCountDegree1(BTNode*bt){if(bt){if((bt->lchild&&!bt->rchild)||(!bt->lchild&&bt->rchild)){Count++;/*计数*/}CountDegree1(bt->lchild);CountDegree1(bt->rchild);}}/*CountDegree1*/6．设计递归算法，求出先根序列中第k个结点的值。解:charLocat_bt(BTreebt,intk){/*求先序序列中第k个结点的值的递归算法*/staticintn;n=k;if(bt){n--;if(n==0)return(bt->data);Locat_bt(bt->lchild,n);if(n!=0)Locat_bt(bt->rchild,n);}elsereturn("#");}7．现有按中根遍历二叉树的结果为：ABC，请画出可以得到这一结果的全部二叉树。解：CBACABBACBACACB8．已知遍历某二叉树后的中根遍历序列CDBAFGEIHJ和后根遍历序列DCBGFIJHEA，试画出该二叉树。解：根据二叉树后的中根遍历和后根遍历的特点，其中根遍历序列和后根遍历序列的形式如下所示：中根遍历序列：后根遍历序列：左子树中根序列根右子树中根序列左子树中根序列右子树中根序列根 显然，后根历序列中的最后一个结点就是二叉树的根结点，然后再在中根序列中找出根结点所在位置。根据根结点的位置可以将中根序列划分为两部分，其中在根结点之前的子序列为左子树的中根序列，而根结点之后的子序列为右子树的中根序列。由于左子树的后根序列长度应与中根序列长度相等，因此可以从二叉树的后根历序列中找出左子树的后根序列，同也可以找出右子树的后根序列。这样，我们可以根据左、右子树的中根序列和后根序列，按照上述方法继续划分，直到划分的子序列为空。在这个划分过程中，可以逐步构造出唯一的一棵二叉树。构造过程如下图（a）～(f)所示：CDBAFGEIHJ(c)BAFGEIHJCD(b)ACDBFGEIHJ(a)EFGCDBAIHJ(d)FGECDBAIHJ(e)JHIFGECDBA(f)9．画出题图4-2所示二叉树的先根、中根、和后根线索化树。解：先根遍历序列：ABDGCEHJKFI中根遍历序列：BGDAEJHKCIF后根遍历序列：GDBJKHEIFCA (a)先根线索树NULLDEBAHIFCGJKDEBAHIFCGJKNULLNULL（b）中根线索树DEBAHIFCGJK（c）后根线索树NULL10．根据4．4．2节中根线索递归算法，改写成一个结点结构仅有4个域(无左标志域)，试建立其后继线索的递归算法。解：线索链表结点结构类型：typedefstructthrnode{TElemtpdata; structthrnode*lchild,*rchild;intRtag;}ThrNode2;voidinthread2(ThrNode2*t);ThrNode2*pre;voidCrt_inthread2(ThrNode2*thrt){/*已知thrt指向二叉树的根结点，中序遍历建立中序后继线索二叉树*/pre=NULL;inthread2(thrt);/*中序遍历线索化*/pre->Rtag=1;/*最后一个结点线索化*/}/*Crt_inthread2*/voidinthread2(ThrNode*t)/*中序遍历线索化以t为根的二叉树*/{if(t){inthread2(t->lchild);/*左子树线索化*/if(pre!=NULL){if(pre->rchild==NULL){/*建立pre结点的后继线索*/pre->Rtag=1;pre->rchild=t;}}pre=t;/*pre指向t的前驱*/inthread2(t->rchild);/*右子树线索化*/}}/*inthread2*/题图4-2FBDHKGJICAE11．画出与题图4-2所示二叉树对应的森林。解：FBDHKGJICAE上机实习题一、实习目的1．掌握树的结构的非线性特点、递归性特点和动态数据结构等特点。2．掌握二叉树的存储结构、各种遍历算法以及基于遍历算法的其他操作的实现。二、实习内容 1．编写一个C语言程序，对二叉树实现以下操作：（1）按先根、中根和后根次序遍历二叉树；（2）按二叉树的层次输出各结点（每一行输出一层）；（3）利用遍历算法，将二叉树中所有结点的左右子树交换。2．在一段文字中10个常用汉字及出现的频度如下：的地得于个和在再是有2664157685185试为这些常用汉字设计哈夫曼编码表。 第五章12341V1入度2,出度1，v2入度1，出度2,v3入度1，出度0，v4入度1，出度2邻接阵G0001101000001100邻接表v1->v4v2->v1v3v4->v1->v2逆邻接表v1->v2->v4v2->v4v3->v2v4->v12广度优先序列是：v2,v1,v3,v6,v4,v5深度优先序列是:v2,v1,v3,v4,v5,v63深度优先序列是：v1,v3,v4,v2,v5（根据存储顺序，如果根据序号大小有不同结果）4给出归并顺序：普里姆：v1,-v3-v4-v5-v2克鲁斯卡尔：v4,v5边，v4,v2边，v3,v4边，v3,v1边（有权值相同的边，不唯一）５最短路径(v1-v3)5(v1-v6)15(v1-v4)19(v1-v2)20(v1-v5)256AOV网络 v1,v4,(或者v4,v1)可换;v2位置不可变，v5,v3(或者 v3,v5)，v6不可变邻接表中:v1,v4,v2,v3,v5,v6第六章1算法说明：本程序使用两个结点链交换的方法，比较复杂，要简化的同学可以直接交换内容。代码可以省去三分之二。/*insertsortviaLinkList*/structNode{intdata;structNode*next;};structNode*locateCount(structNode*h,intk){inti=0;structNode*h1=h;for(i=1;i<=k;i++)h1=h1->next;returnh1;};show(structNode*head){structNode*p;p=head->next;while(p!=0){printf(":%3d:",p->data);p=p->next;}printf("n");return;}sort(structNode*head){structNode*h,*searchGoalPtr,*p,*q,*qStart,*preGoal;structNode*temp,*pt1,*pt2,*goalNext;intcount=2;h=head;preGoal=head->next;searchGoalPtr=head->next->next;qStart=head;while(searchGoalPtr!=0){/*go*/h->data=searchGoalPtr->data;q=qStart;while(q->next->datadata){q=q->next;}pt1=q->next;q->next=searchGoalPtr;pt2=searchGoalPtr->next;searchGoalPtr->next=pt1;preGoal->next=pt2;preGoal=locateCount(head,count);count++;searchGoalPtr=locateCount(head,count);show(head); }/*while*/}main(){structNode*h,*p1,tail;intvar=0;h=(structNode*)malloc(sizeof(structNode));h->data=0;h->next=0;/*constructalinkedlist*/while(1){printf("PleaseinputaNode,enter-1end:");scanf("%d",&var);if(var==-1)break;p1=(structNode*)malloc(sizeof(structNode));p1->data=var;p1->next=h->next;h->next=p1;}show(h);sort(h);show(h);/*yesconstructed!*/free(h);return;}2排序过程5667594198472638755216原始数据1626384152476759759856d=51626384152476756759859d=31626384147525659677598d=13不需要，因为排序已经完成4冒泡过程14152851030a14155102830b14510152830c1014152830d快速过程1415302851010153028514101430285151053028141510514283015-分左右再内部排序得10141528305直接插入5冒泡5快速146提示：改动算法6.5的判断条件即可。7/*insertsortviaLinkList*/structNode{intdata; structNode*next;};show(structNode*head){structNode*p;p=head->next;while(p!=0){printf(":%3d:",p->data);p=p->next;}printf("n");return;}sort(structNode*head){structNode*p,*ptr1,*ptr2;intmin;inttemp;ptr1=head->next;while(ptr1){ptr2=ptr1->next;min=ptr1->data;while(ptr2){if(ptr2->datadata;ptr1->data=ptr2->data;ptr2->data=temp;}/*if*/ptr2=ptr2->next;}/*ptr2*/ptr1=ptr1->next;}show(head);}/*while*/main(){structNode*h,*p1,tail;intvar=0;h=(structNode*)malloc(sizeof(structNode));h->data=0;h->next=0;/*constructalinkedlist*/while(1){printf("PleaseinputaNode,enter-1end:");scanf("%d",&var);if(var==-1)break;p1=(structNode*)malloc(sizeof(structNode));p1->data=var;p1->next=h->next;h->next=p1;}show(h); sort(h);show(h);/*yesconstructed!*/free(h);return;}84符合堆的特性。9193426975675是一个堆先19出堆，调整75上来，得->197534269756,调整后2634759756，得->26调整56上来得56347597调整得34567597出->34调整97上来得975675调整得569775出56最后出75和97105667594198472638755216L=15667415947982638527516L=24156596726384798165275L=41626384147525659677598结果原因是r是一次归并结果，放在r2里临时存放，最后放回r以便下次再处理。第七章1．有一个有序文件，其中各记录的关键字为：{3,4,5,6,7,8,10,17,19,20,27,32,43,54,65,76,87}，当用折半查找算法查找关键字为4,20,65时，其比较次数分别为多少?解：K=46571110128213151416491317K=20K=65判定树该有序文件长度为17，根据折半查找算法画出判定树如下图所示。从图中可得出：当关键字为4,20,65时，其比较次数分别为3，4，3。 ２、若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找，试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同?(1)查找失败；(2)查找成功；(3)查找成功，表中有多个关键字等于给定值的记录，一次查找要求找出所有记录。解：(1)平均查找长度不相同。有序顺序表小于等于无序顺序表。(2)平均查找长度相同。(3)平均查找长度不相同，有序顺序表小于等于无序顺序表。３、试按下列次序将各关键字插入到二叉平衡树中，画出重新平衡的情况。关键字依次为：8、9、12、2、1、5、3、6、7、11解：生成并调整成平衡二叉排序树的过程如下图(a)～(j)所示。89128RR89(b)不调整1289(c)调整(a)初始912821LL912281(e)调整91282(d)不调整9122815LR9128251LL9825112(f)调整39825112(g)不调整39825112(h)不调整6 3982511267RR1985621273(i)调整9111856212731211985621173111985621273RRRL(j)调整４、已知长度为12的表：（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）。(1)试按表中元素的顺序，依次插入一棵初始为空的二叉树；试画出插入完成之后的二叉排序树，并求其在等查找概率情况下查找成功的平均查找长度。(2）若对表中元素先进行排序构成有序表，试求在等查找概率情况下对此有序表进行二分查找时查找成功的平均查找长度。JanonFebMarAugJulDecMayAprJunNovOctSep解：(1)二叉排序树如下图所示。平均查找长度SAL=(1*1+2*2+3*3+3*4+2*5+1*6)/12=42/12=3.5 (2)对有序表（Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep）进行二分查找时，其判定树如下图所示,JulnonDecMayAugMarOctAprJunFebNovSepJan所以平均查找长度SAL=(1*1+2*2+4*3+5*4)/12=35/125.在题图7-1所示的3阶B-树中，删除关键字37，试画出删除过程。解：45115261937810128(a)删除374511523761937810128题图7-145112852619378101(b)双亲28下移 61112878529310145(c)向右兄弟借关键字616.已知一个线性表(38，25，74，63，52，48)，采用的散列函数为H(Key)=Keymod7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为多少？若利用链地址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为多少？解：（1）用线性探测的开放定址法解决冲突的哈希表:H(38)=38%7=3比较1次H(25)=25%7=4比较1次H(74)=74%7=4(冲突)H1(74)=(H(74)+1)%7=(4+1)%7=5(成功)比较2次H(63)=63%7=0比较1次H(52)=52%7=3(冲突)H1(52)=(H(52)+1)%7=(3+1)%7=4(冲突)H2(52)=(H(52)+2)%7=(3+2)%7=5(冲突)H3(52)=(H(52)+3)%7=(3+3)%7=6(成功)比较4次H(48)=48%7=6(冲突)H1(48)=(H(48)+1)%7=(6+1)%7=7(成功)比较2次地址01234567关键字633825745248比较次数111242 (2)平均查找长度ASL=（3*1+2*2+1*4）/6=11/6（3）用链地址法解决冲突的哈希表:∧∧∧0123456763∧382548∧52∧74∧H(38)=38%7=3比较1次H(25)=25%7=4比较1次H(74)=74%7=4(冲突)比较2次H(63)=63%7=0比较1次H(52)=52%7=3(冲突)比较2次H(48)=48%7=6比较1次(4)平均查找长度ASL=（4*1+2*2）/6=8/67.设有关键字序列{22,41,53,46,30,13,01,67}，选取哈希函数H（k）=3k%11，试用下列两种处理冲突的方法分别在0~10的散列地址空间中构造哈希表。（1）线性探测法；（2）线性补偿探测法（取Q=5）。解：线性探测法构造哈希表过程如下：（1）H(22)=3*22%11=0比较1次（2）H(41)=3*41%11=2比较1次（3）H(53)=3*53%11=5比较1次（4）H(46)=3*46%11=6比较1次（5）H(30)=3*30%11=2(冲突)H1(30)=(H(30)+1)%11=(2+1)%11=3(成功)比较2次（6）H(13)=3*13%11=6(冲突)H1(13)=(H(13)+1)%11=(6+1)%11=7(成功)比较2次（7）H(01)=3*1%11=3(冲突)H1(01)=(H(01)+1))%11=4(成功)比较2次（8）H(67)=3*67%11=3(冲突)H1(67)=(H(67)+1))%11=(3+1)%11=4(冲突)H2(67)=(H(67)+2))%11=(3+2)%11=5(冲突)H3(67)=(H(67)+3))%11=(3+3)%11=6(冲突)H4(67)=(H(67)+4))%11=(3+4)%11=7(冲突)H5(67)=(H(67)+5))%11=(3+5)%11=8(成功)比较6次地址012345678910关键字2204130015346136700比较次数10122112600查找成功时的平均查找长度为：ASL=(4*1+3*2+1*6)/8=18/8线性补偿探测法（取Q=5）构造哈希表过程如下：(1)H(22)=3*22%11=0比较1次(2)H(41)=3*41%11=2比较1次 (3)H(53)=3*53%11=5比较1次(4)H(46)=3*46%11=6比较1次(5)H(30)=3*30%11=2(冲突)H1(30)=(H(30)+5)%11=(2+5)%11=7(成功)比较2次(6)H(13)=3*13%11=6(冲突)H1(13)=(H(13)+5)%11=(6+5)%11=0(冲突)H2(13)=(0+5)%11=(0+5)%11=5(冲突)H3(13)=(5+5)%11=10(成功)比较4次(7)H(01)=3*1%11=3(成功)比较1次(8)H(67)=3*67%11=3(冲突)H1(67)=(H(67)+5))%11=(3+5)%11=8(成功)比较2次地址012345678910关键字2204101053463067013比较次数10110112204查找成功时的平均查找长度为：ASL=(5*1+2*2+1*4)/8=13/8上机实习题针对某班级的名单设计一个哈希表(30人)，使得平均查找长度不超过２。请编出相应的建表和查表程序。要求用除留余数法，用补偿性线性探测处理冲突。解：设姓名长度不超过20个字符，可先把20个字符相加，用平方取中法。因为线性探测法的平均查找次数为：（1+1/（1-α））/2取α=0.6，则哈希表长m=30/0.6≈50。#include#includevoidCreatHash(charHt[][20],intn);/*建立哈希表*/intmid(charname[]);/*平方取中法*/voidsearch(charHt[][20],charname[]);/*查找*/main(){charsname[20],htbl[50][20];clrscr();CreatHash(htbl,30);printf("Enterthenameforsearch:");gets(sname);search(htbl,sname);getch(); }voidCreatHash(charHt[][20],intn){inti,j,d;charname[20];for(i=0;i<50;i++)strcpy(Ht[i],NULL);for(i=0;id)d*=10;d/=10;while(d!=0){temp[i++]=s%d;/*分离s的各位*/s/=10;d/=10;}return(temp[3]*10+temp[4]);/*取中间的第4,5为返回*/}voidsearch(charHt[][20],charname[]){unsignedlongd;d=mid(name)%47;if(strcmp(Ht[d],name)==0){printf("Found!at%dn",d);return;}while((strcmp(Ht[d],name)!=0)&&(strcmp(Ht[d],NULL)!=0)) d=(d+17)%47;if(strcmp(Ht[d],name)==0)printf("Found!at%dn",d);elseprintf("Notfoundn");}'