数据结构---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、算法如下：int Linser(SeqList *L,int X){ int i=0,k;if(L->last>=MAXSIZE-1){ printf(“表已满无法插入”)；return(0);}while(ilastk>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(1);}5、算法如下：#define OK 1#define ERROR 0Int LDel(Seqlist *L,int i,int k){ int j;if(i(L->last+2)){ printf(“输入的 i，k 值不合法 ”);return ERROR;}if((i+k)==(L->last+2)){ L->last=i-2;ruturn OK;}else{for(j=i+k-1;jlast;j++)elem[j-k]=elem[j];L->last=L->last-k;return OK;}}6、算法如下：#define OK 1#define ERROR 0Int Delet(LInkList L,int mink,int maxk){ Node *p,*q;p=L;while(p->next!=NULL)p=p->next;if(minknext->data>=mink)||(p->datanext-datanext;while(q->datanext=q->next;free(q);q=p->next;}return OK;}}9、算法如下：int Dele(Node *S){ Node *p;P=s->next;If(p= =s){printf(“只有一个结点，不删除”)；return 0;}else{if((p->next= =s){s->next=s;free(p);return 1;}Else{ while(p->next->next!=s)P=p->next;P->next=s;Free(p);return 1;}}}第三章 习题答案2、 (1)3、栈有顺序栈和链栈两种存储结构。在顺序栈中，栈顶指针 top=-1时，栈为空；栈顶指针 top=Stacksize-1时，栈为满。在带头结点链栈中，栈顶指针 top-〉next=NULL，则代表栈空；只要系统有可用空间，链栈就不会出现溢出，既没有栈满。5、#include#include “stdio.h“void main( ){char ch,temp;SeqStack s;InitStack(scanf(“%c“,while(ch!= @ scanf(“%c“,}while(ch!= @ scanf(“%c“,if(ch!=temp)break;}if(!IsEmpty(else{scanf(“%c“,if(ch== @ ) printf(“yes!\n“);else printf(“no!\n“);}}12、 (1)功能：将栈中元素倒置。(2)功能：删除栈中的 e 元素。(3)功能：将队列中的元素倒置。 第四章习题答案1、StrLength(s) 操作结果为14；SubString(sub1,s,1,7)操作结果为 sub1=’I AM A ’；SubString(sub2,s,7,1)操作结果为 sub2=’ ’；StrIndex(s,’A’ ,4) 操作结果为5；StrReplace(s,’STUDENT’,q) 操作结果为’I AM A WORKER’；StrCat(StrCat(sub1,t), StrCat(sub2,q)) 操作结果为’I AM A GOOD WORKER’；2、int StrReplace(SString S,Sstring T,SString V){int i=1; //从串 S 的第一个字符起查找串 Tif(StrEmpty(T)) //T 是空串return ERROR;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);return OK;}第五章习题答案1、 (1)数组 A 共占用48*6=288个字节；(2)数组 A 的最后一个元素的地址为 1282；(3)按行存储时 loc(A 36) =1000+[(3-1)*8+6-1]*6=1126(4)按列存储时 loc(A 36) =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、证明：分支数=n 1+2n2+…+knk (1)n= n0+n1+…+nk (2)∵n=分支数+1 (3)将(1) (2)代入(3)得n0= n2+2n3+3n4+…+(k-1)n k+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.07 00100.19 100.02 000000.06 00010.32 010