数据结构 - C语言描述（耿国华）课后习题答案 - 图文

第一章 习题答案2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽

（3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型

（5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作

（9）有限性、输入、可行性 4、（1）A（2）C（3）C

5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章 习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定

（4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A

B：H、L、I、E、A C：F、M

D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C

3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下：

int Linser(SeqList *L,int X) { int i=0,k;

if(L->last>=MAXSIZE-1)

{ printf(“表已满无法插入”)； return(0); }

while(i<=L->last&&L->elem[i]

for(k=L->last;k>=I;k--) L->elem[k+1]=L->elem[k]; L->elem[i]=X; L->last++; return(1); }

5、算法如下： #define OK 1 #define ERROR 0

Int LDel(Seqlist *L,int i,int k) { int j;

if(i<1||(i+k)>(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;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } }

6、算法如下： #define OK 1 #define ERROR 0

Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L;

while(p->next!=NULL) p=p->next;

if(minknext->data>=mink)||(p->data<=maxk)) { printf(“参数不合法”); return ERROR; } else

{ p=L;

while(p->next-data<=mink) p=p->next;

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 \void main( ) {

char ch,temp; SeqStack s; InitStack(&s); scanf(\

while(ch!='@'&&ch!='&') {

Push(&s,ch); scanf(\ }

while(ch!='@'&&!IsEmpty(&s)) {

Pop(&s,&temp); scanf(\ if(ch!=temp) break; }

if(!IsEmpty(&s))

printf(\ else {

scanf(\

if(ch=='@') printf(\ else printf(\ } } 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的第一个字符起查找串T if(StrEmpty(T)) //T是空串 return ERROR; do {

i=Index(S,T,i); //结果i为从上一个i之后找到的子串T的位置 if(i) //串S中存在串T {

StrDelete(S,i,StrLength(T)); //删除该串T

StrInsert(S,i,V); //在原串T的位置插入串V i+=StrLength(V); //在插入的串V后面继续查找串T } }while(i); return OK; }

第五章习题答案 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=1192 9、（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+1 4、

注：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+1 8、对应的树如下：

9、（答案不唯一） 哈夫曼树如下图所示：

本文来源：https://www.bwwdw.com/article/wymh.html