数据结构---C语言描述(耿国华)课后习题答案

第一章习题答案2、××√3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽（3）数据对象、对象间的关系、一组处理数据的操作（4）指针类型（5）集合结构、线性结构、树形结构、图状结构（6）顺序存储、非顺序存储（7）一对一、一对多、多对多（8）一系列的操作（9）有限性、输入、可行性4、（1）A（2）C（3）C5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）第二章习题答案1、（1）一半，插入、删除的位置（2）顺序和链式，显示，隐式（3）一定，不一定（4）头指针，头结点的指针域，其前驱的指针域2、（1）A（2）A：E、AB：H、L、I、E、AC：F、MD：L、J、A、G或J、A、G（3）D（4）D（5）C（6）A、C3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。首元素结点：线性表中的第一个结点成为首元素结点。4、算法如下：intLinser(SeqList*L,intX){inti=0,k;if(L-last=MAXSIZE-1){printf(“表已满无法插入”)；return(0);}while(i=L-last&&L-elem[i]X)i++;for(k=L-last;k=I;k--)L-elem[k+1]=L-elem[k];L-elem[i]=X;L-last++;return(1);}5、算法如下：#defineOK1#defineERROR0IntLDel(Seqlist*L,inti,intk){intj;if(i1||(i+k)(L-last+2)){printf(“输入的i，k值不合法”);returnERROR;}if((i+k)==(L-last+2)){L-last=i-2;ruturnOK;}else{for(j=i+k-1;j=L-last;j++)elem[j-k]=elem[j];L-last=L-last-k;returnOK;}}6、算法如下：#defineOK1#defineERROR0IntDelet(LInkListL,intmink,intmaxk){Node*p,*q;p=L;while(p-next!=NULL)p=p-next;if(minkmaxk||(L-next-data=mink)||(p-data=maxk)){printf(“参数不合法”);returnERROR;}else{p=L;while(p-next-data=mink)p=p-next;while(q-datamaxk){p-next=q-next;free(q);q=p-next;}returnOK;}}9、算法如下：intDele(Node*S){Node*p;P=s-next;If(p==s){printf(“只有一个结点，不删除”)；return0;}else{if((p-next==s){s-next=s;free(p);return1;}Else{while(p-next-next!=s)P=p-next;P-next=s;Free(p);return1;}}}第三章习题答案2、（1）3、栈有顺序栈和链栈两种存储结构。在顺序栈中，栈顶指针top=-1时，栈为空；栈顶指针top=Stacksize-1时，栈为满。在带头结点链栈中，栈顶指针top-〉next=NULL，则代表栈空；只要系统有可用空间，链栈就不会出现溢出，既没有栈满。5、#includeseqstack1.h#includestdio.hvoidmain(){charch,temp;SeqStacks;InitStack(&s);scanf(%c,&ch);while(ch!='@'&&ch!='&'){Push(&s,ch);scanf(%c,&ch);}while(ch!='@'&&!IsEmpty(&s)){Pop(&s,&temp);scanf(%c,&ch);if(ch!=temp)break;}if(!IsEmpty(&s))printf(no!\n);else{scanf(%c,&ch);if(ch=='@')printf(yes!\n);elseprintf(no!\n);}}12、（1）功能：将栈中元素倒置。（2）功能：删除栈中的e元素。（3）功能：将队列中的元素倒置。第四章习题答案1、StrLength(s)操作结果为14；SubString(sub1,s,1,7)操作结果为sub1=’IAMA’；SubString(sub2,s,7,1)操作结果为sub2=’’；StrIndex(s,’A’,4)操作结果为5；StrReplace(s,’STUDENT’,q)操作结果为’IAMAWORKER’；StrCat(StrCat(sub1,t),StrCat(sub2,q))操作结果为’IAMAGOODWORKER’；2、intStrReplace(SStringS,SstringT,SStringV){inti=1;//从串S的第一个字符起查找串Tif(StrEmpty(T))//T是空串returnERROR;do{i=Index(S,T,i);//结果i为从上一个i之后找到的子串T的位置if(i)//串S中存在串T{StrDelete(S,i,StrLength(T));//删除该串TStrInsert(S,i,V);//在原串T的位置插入串Vi+=StrLength(V);//在插入的串V后面继续查找串T}}while(i);returnOK;}第五章习题答案1、（1）数组A共占用48*6=288个字节；（2）数组A的最后一个元素的地址为1282；（3）按行存储时loc（A36）=1000+[（3-1）*8+6-1]*6=1126（4）按列存储时loc（A36）=1000+[（6-1）*6+3-1]*6=11929、（1）（a，b）（2）（（c，d））（3）（b）（4）b（5）（d）10、D第六章习题答案1、三个结点的树的形态有两个；三个结点的二叉树的不同形态有5个。2、略3、证明：分支数=n1+2n2+…+knk（1）n=n0+n1+…+nk（2）∵n=分支数+1（3）将（1）（2）代入（3）得n0=n2+2n3+3n4+…+（k-1）nk+14、注：C结点作为D的右孩子（画图的时候忘记了，不好意思）5、n0=50，n2=n0-1=49，所以至少有99个结点。6、（1）前序和后序相同：只有一个结点的二叉树（2）中序和后序相同：只有左子树的二叉树（3）前序和中序相同：只有右子树的二叉树7、证明：∵n个结点的K叉树共有nk个链域，分支数为n-1（即非空域）。∴空域=nk-（n-1）=nk-n+18、对应的树如下：9、（答案不唯一）哈夫曼树如下图所示：哈夫曼编码如下：频率编码0.0700100.19100.02000000.0600010.32010.03000010.21110.10001111、对应的二叉树如下：12、求下标分别为i和j的两个桔点的最近公共祖先结点的值。typedefintElemType;voidAncestor(ElemTypeA[],intn,inti,intj){while(i!=j)if(ij)i=i/2;elsej=j/2;printf(所查结点的最近公共祖先的下标是%d,值是%d,i,A[i]);}15、编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。voidDel_Sub(BiTreeT){if(T-lchild)Del_Sub(T-lchild);if(T-rchild)Del_Sub(T-rchild);free(T);}voidDel_Sub_x(BiTreeT,intx){if(T-data==x)Del_Sub(T);else{if(T-lchild)Del_Sub_x(T-lchild,x);if(T-rchild)Del_Sub_x(T-rchild,x);}}22、intWidth(BiTreebt){if(bt==NULL)return(0);else{BiTreep,Q[50];intfront=1,rear=1,last=1;inttemp=0,maxw=0;Q[rear]=bt;while(front=last){p=Q[front++];temp++;if(p-lchild!=NULL)Q[++rear]=p-lchild;if(p-rchild!=NULL)Q[++rear]=p-rchild;{last=rear;if(tempmaxw)maxw=temp;temp=0;}}return(maxw);}}第七章习题答案1、（1）顶点1的入度为3，出度为0；顶点2的入度为2，出度为2；顶点3的入度为1，出度为2；顶点4的入度为1，出度为3；顶点5的入度为2，出度为1；顶点6的入度为2，出度为3；（2）邻接矩阵如下：000000100100010001001011100000110010（3）邻接表（4）逆邻接表2、答案不唯一（2）深度优先遍历该图所得顶点序列为：1，2，3，4，5，6边的序列为：（1，2）（2，3）（3，4）（4，5）（5，6）（3）广度优先遍历该图所得顶点序列为：1，5，6，3，2，4边的序列为：（1，5）（1，6）（1，3）（1，2）（5，4）3、（1）每个事件的最早发生时间：ve(0)=0,ve(1)=5,ve(2)=6,ve(3)=12,ve(4)=15,ve(5)=16,ve(6)=16,ve(7)=19,ve(8)=21,ve(9)=23每个事件的最晚发生时间:：vl(9)=23,vl(8)=21,vl(7)=19,vl(6)=19,vl(5)=16,vl(4)=15,vl(3)=12,vl(2)=6,vl(1)=9,vl(0)=0（2）每个活动的最早开始时间：e(0,1)=0,e(0,2)=0,e(1,3)=5,e(2,3)=6,e(2,4)=6,e(3,4)=12,e(3,5)=12,e(4,5)=15,e(3,6)=12,e(5,8)=16,e(4,7)=15,e(7,8)=19,e(6,9)=16,e(8,9)=21每个活动的最迟开始时间：l(0,1)=4,l(0,2)=0,l(1,3)=9,l(2,3)=6,l(2,4)=12,l(3,4)=12,l(3,5)=12,l(4,5)=15,l(3,6)=15,l(5,8)=16,l(4,7)=15,l(7,8)=19,l(6,9)=19,l(8,9)=21（3）关键路径如下图所示：4、顶点1到其余顶点的最短路经为：1-〉3最短路经为1，3；长度为151-〉2最短路经为1，3，2；长度为191-〉5最短路经为1，3，5；长度为251-〉4最短路经为1，3，2，4；长度为291-〉6最短路经为1，3，2，4，6；长度为4413、A(7)B(3)C(2)D(11)E(8)14、略15、略第八章查找1、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。解：ASL=(1+2*2+4*3+3*4)/10=2.95、解：（1）插入完成后的二叉排序树如下：ASL=(1+2*2+3*3+3*4+2*5+1*6)/12=3.5(2)ASL=(1+282+3*4+4*5)=37/12(3)12、解：哈希表构造如下：0123456789102241300153461367H(22)=(22*3)%11=0H(41)=(41*3)%11=2H(53)=(53*3)%11=5H(46)=(46*3)%11=6H(30)=(30*3)%11=2与(41)冲突H1(30)=(2+1)%11=3H(13)=(13*3