耿国华数据结构习题答案完整版

1、WORD格式第一章答案1.3 计算以下程序中x=x+1 的语句频度for(i=1;i<=n;i+)for(j=1;j<=i;j+)for(k=1;k<=j;k+)x=x+1;【解答】 x=x+1 的语句频度为：T(n)=1+(1+2)+1+2+3+1+2+ +n=n(n+1)(n+2)/61. 4 试编写算法， 求 p n(x)=a 0+a 1x+a 2 x2 + .+a n xn的值 p n (x 0), 并确定算法中每一语句的执行次数和整个算法的时间复杂度， 要求时间复杂度尽可能小， 规定算法中不能使用求幂函数。注意：此题中的输入为 ai(i=0,1, n)、x 和 n,

2、 输出为 Pn (x 0 )。算法的输入和输出采用以下方法 1通过参数表中的参数显式传递 2 通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】（ 1通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用完毕后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。（ 2通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue() int i,n;float x,a,p;专业资料整理WORD格式

3、printf(“nn= );专业资料整理WORD格式scanf(“ %f ,&n);专业资料整理WORD格式printf(“nx= );专业资料整理WORD格式scanf(“ %f ,&x);专业资料整理WORD格式for(i=0;i<n;i+)专业资料整理WORD格式scanf(“ %f ,&ai);/* 执行次数：n 次*/专业资料整理WORD格式p=a0;for(i=1;i<=n;i+)专业资料整理WORD格式p=p+ai*x;/* 执行次数：n 次 */专业资料整理WORD格式x=x*x;专业资料整理WORD格式printf(“ %f ,p);专业资

4、料整理WORD格式专业资料整理WORD格式算法的时间复杂度：T(n)=O(n)专业资料整理WORD格式通过参数表中的参数显式传递专业资料整理WORD格式floatPolyValue(floata ,floatx,intn)专业资料整理WORD格式float p,s;int i;p=x;s=a0;for(i=1;i<=n;i+)专业资料整理WORD格式s=s+ai*p;/* 执行次数:n次 */专业资料整理WORD格式p=p*x;return(p);专业资料整理WORD格式算法的时间复杂度：T(n)=O(n)专业资料整理WORD格式第二章答案2.7试分别以不同的存储构造实现单线表的就地逆置

5、算法，即在原表的存储空间将线性表（ a1 ,a2 , ,an逆置为 (a n ,a n-1 , ,a1 )。【解答】 1用一维数组作为存储构造专业资料整理WORD格式voidinvert(SeqList*L,int*num)专业资料整理WORD格式intj;ElemTypetmp;专业资料整理WORD格式for(j=0;j<=(*num-1)/2;j+) tmp=Lj; Lj=L*num-j-1; L*num-j-1=tmp; 2用单链表作为存储构造专业资料整理WORD格式voidinvert(LinkListL)专业资料整理WORD格式Node*p, *q, *r;专业资料整理WORD

6、格式if(L->next =NULL)return;/* 链表为空*/专业资料整理WORD格式p=L->next;q=p->next;专业资料整理WORD格式p->next=NULL;while(q!=NULL)/*/*摘下第一个结点，生成初始逆置表从第二个结点起依次头插入当前逆置表*/*/专业资料整理WORD格式专业资料整理WORD格式r=q->next;q->next=L->next;L->next=q;q=r;专业资料整理WORD格式2.11将线性 表A=(a1,a2, am),C=(a1,b1, am,bm,bm+1, .bn)C=(a1

7、,b1, an,bn,an+1, am)当 m>n且 C 表利用 A 表和 B 表中的结点空间构成。【解答】算法如下：B=(b1,b2, bn)合并成 线性表C,当m<=n时，或时 ,线性表 A 、 B 、 C 以单链表作为存储构造，注意： 单链表的长度值m 和 n 均未显式存储。专业资料整理WORD格式LinkListmerge(LinkListA,LinkList B,LinkList Node*pa, *qa, *pb, *qb, *p;pa=A->next;/*pa 表示 A 的当前结点 */pb=B->next;p=A;/ * 利用 p 来指向新连接的表的表尾

8、，初始值指向表C)A 的头结点*/专业资料整理WORD格式while(pa!=NULL&&pb!=NULL)/* 利用尾插法建立连接之后的链表*/专业资料整理WORD格式 qa=pa->next; qb=qb->next;专业资料整理WORD格式p->next=pa;/* 交替选择表A 和表B 中的结点连接到新链表中；*/专业资料整理WORD格式p=pa;p->next=pb;p=pb;pa=qa;pb=qb;专业资料整理WORD格式if(pa!=NULL)if(pb!=NULL)p->next=pa;p->next=pb;/*A/*B的长度

9、大于的长度大于B 的长度 A 的长度*/*/专业资料整理WORD格式C=A;Return(C);第三章答案3.1 按 3.1(b) 所示铁道两侧铁道均为单向行驶道进展车厢调度，答复： 1如进站的车厢序列为123 ，那么可能得到的出站车厢序列是什么？ 2如进站的车厢序列为123456 ，能否得到435612 和 135426 的出站序列，并说明原因即写出以“S表示进栈、 “ X表示出栈的栈序列操作。【解答】 1可能得到的出站车厢序列是：123 、 132 、 213 、 231 、 321 。(2) 不能得到 435612 的出站序列。因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5

10、)X(5)S(6)S(6)，此时按照“后进先出的原那么，出栈的顺序必须为X(2)X(1) 。能得到 135426 的出站序列。因为有 S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。3.3 给出栈的两种存储构造形式名称，在这两种栈的存储构造中如何判别栈空与栈满？【解答】 1顺序栈top 用来存放栈顶元素的下标判断栈 S 空：如果S->top=-1表示栈空。判断栈 S 满：如果S->top=Stack_Size-1表示栈满。(2) 链栈 top 为栈顶指针，指向当前栈顶元素前面的头结点判断栈空：如果 top->next=NULL 表示栈

11、空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。3 4 照四那么运算加、减、乘、除和幂运算的优先惯例，画出对以下表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+E F【解答】专业资料整理WORD格式3 5 写一个算法，判断依次读入的一个以 为完毕符的字母序列，是否形如序列1& 序列 2的字符序列。序列1 和序列 2 中都不含 & ，且序列2 是序列 1 的逆序列。例专业资料整理WORD格式如，a+b&b+a是属于该模式的字符序列，而1+3&3-1那么不是。【解答】算法如下：专业资料整理WORD格式intIsHuiWen()专

12、业资料整理WORD格式Stack*S;Charch,temp;InitStack(&S);Printf(n“请输入字符序列：);Ch=getchar();专业资料整理WORD格式While( ch!=&)/* 序列1 入栈*/专业资料整理WORD格式Push(&S,ch);ch=getchar();专业资料整理WORD格式do/* 判断序列 2 是否是序列1 的逆序列*/专业资料整理WORD格式 ch=getchar(); Pop(&S,&temp);专业资料整理WORD格式if(ch!= temp) re turn(FALSE);printf(“nNO

13、); while(ch!=&&!IsEmpty(&S)if(ch = = &&IsEmpty(&S) return(TRUE);printf(“nYES);elsereturn(FALSE);printf(“nNO);/*IsHuiWen()*/*序列 2 不是序列1 的逆序列 */* 序列 2 是序列 1 的逆序列 */专业资料整理WORD格式3.8 要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag, 以 tag为 0 或1专业资料整理WORD格式来区分头尾指针一样时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队

14、算法：专业资料整理WORD格式intEnterQueue(SeqQueue*Q,QueueElementTypex)专业资料整理WORD格式 /* 将元素 x 入队 */专业资料整理WORD格式if(Q->front=Q->frontreturn(FALSE);if(Q->front=Q->front&&tag=1)&&tag=0)/*队满 */*x 入队前队空，x 入队后重新设置标志专业资料整理WORD格式*/tag=1;Q->elememtQ->rear=x;专业资料整理WORD格式Q->rear=(Q->re

15、ar+1)%MAXSIZE;/* 设置队尾指针*/专业资料整理WORD格式Return(TRUE);出队算法：专业资料整理WORD格式intDeleteQueue( SeqQueue /* 删除队头元素，用x 返回其值*Q , */QueueElementType*x)专业资料整理WORD格式if(Q->front=Q->rear&&tag=0)return(FALSE);*x=Q->elementQ->front;Q->front=(Q->front+1)%MAXSIZE;if(Q->front=Q->rear)tag=0;/*

16、队空 */*重新设置队头指针*/*队头元素出队后队列为空，重新设置标志域*/专业资料整理WORD格式Return(TUUE);专业资料整理WORD格式编写求解Hanoi 问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法：voidhanoi (intn ,charx, chary, charz)专业资料整理WORD格式/* 将塔座 X 上按直径由小到大且至上而下编号为上， Y 可用做辅助塔座*/if(n = =1)move(x,1,z);elseHanoi(n-1,x,z,y);1 到n 的 n个圆盘按规那么搬到塔座Z专业资料整理WORD格式move(x, n, z);Hanoi(n

17、-1, y,x,z);专业资料整理WORD格式专业资料整理WORD格式Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B):Hanoi(1,A,B,C)move(A->C)Move(A->B)Hanoi(1,C,A,B)move(C->B)Move(A->C)Hanoi(2,B,A,C)Hanoi(1,B,C,A)move(B->A)Move(B->C)Hanoi(1,A,B,C)move(A->C)1号搬到 C2号搬到 B1号搬到 B3号搬到 C1号搬到 A2号搬到 C1号搬到 C专业资料整理WORD格式第四章答案4.1 设 s=

18、 I AM A STUDENT， t= GOOD， q= WORKER 。给出以下操作的结果：【解答】 StrLength(s)=14;SubString(sub1,s,1,7)sub1= I AM A ;SubString(sub2,s,7,1)sub2= ;StrIndex(s,4, A )=6;StrReplace(s, STUDENT ,q);s= I AM A WORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q)sub1= I AM A GOODWORKER 。4.2 编写算法，实现串的根本操作StrReplace(S,T,V)。【解答】算法如下：i

19、nt strReplace(SString S,SString T, SString V)/* 用串 V 替换 S 中的所有子串 T */int pos,i;pos=strIndex(S,1,T);/* 求 S 中子串 T 第一次出现的位置 */if(pos = = 0)return(0);while(pos!=0)/* 用串 V 替换 S 中的所有子串 T */switch(T.len-V.len)case0:/* 串 T 的长度等于串V 的长度 */for(i=0;i<=V.len;i+)/*用 V 替换 T*/S->chpos+i=V.chi;case>0:/*串 T

20、的长度大于串V 的长度 */for(i=pos+t.ien;i<S->len;i-)/* 将 S 中子串 T 后的所有字符置 */S->chi-t.len+v.len=S->chi;前移 T.len-V.len 个位for(i=0;i<=V.len;i+)/*用 V 替换 T*/专业资料整理WORD格式S->chpos+i=V.chi;专业资料整理WORD格式caseS->len=S->len-T.len+V.len; <0:/*串T 的长度小于串V 的长度专业资料整理WORD格式*/专业资料整理WORD格式if(S->len-T.l

21、en+V.len)<=MAXLEN/*插入后串长小于专业资料整理WORD格式MAXLEN*/专业资料整理WORD格式 /* 将 S 中子串 T 后的所有字符后移V.len-T.lenfor(i=S->len-T.len+V.len;i>=pos+T.len;i-)个位置*/专业资料整理WORD格式S->chi=S->chi-T.len+V.len;专业资料整理WORD格式for(i=0;i<=V.len;i+)/*用V 替换T*/专业资料整理WORD格式S->chpos+i=V.chi;S->len=S->len-T.len+V.len;

22、专业资料整理WORD格式else/*替换后串长 >MAXLEN, 但串 V 可以全部替换 */ if(pos+V.len<=MAXLEN)for(i=MAXLEN-1;i>=pos+T.len; i-) S->chi=s->chi-T.len+V.len专业资料整理WORD格式for(i=0;i<=V.len;i+)S->chpos+i=V.chi;S->len=MAXLEN;/*用V 替换T*/专业资料整理WORD格式else/* 串V 的局部字符要舍弃*/专业资料整理WORD格式 for(i=0;i<MAXLEN-pos;i+)S-&g

23、t;chi+pos=V.chi;/*switch()*/S->len=MAXLEN;*/pos=StrIndex(S,pos+V.len,T);/*求 S 中下一个子串T 的位置/*while()*/return(1);/*StrReplace()*/附加题：用链式构造实现定位函数。【解答】typedefstructNodechardata;structNode*next;Node,*Lstring;intstrIndex(LstringS, int pos,LstringT)/*从串 S 的 pos序号起，串 T 第一次出现的位置*/Node*p, *q, *Ppos;int i=0，

24、 ,j=0;if(T->next= =NULL| S->next = =NULL)return(0);p=S->next;q=T->next;while(p!=NULL&&j<pos)/*p 指向串 S 中第 pos 个字符 */p=p->next;j+;if(j!=pos)return(0);while(p!=NULL&&q!=NULL)Ppos=p;/*Ppos指向当前匹配的起始字符 */if(p->data = = q->data)p=p->next; q=q->next;else/* 从 Ppo

25、s指向字符的下一个字符起从新匹配*/专业资料整理WORD格式p=Ppos->next;q=T->head->next;i+;专业资料整理WORD格式if(q= =NULL)elsereturn(0);return(pos+i);/* 匹配成功/* 失败 */*/专业资料整理WORD格式第4章串习题1. 设 s= I AM A STUDENT , t= GOOD , q= WORKER 。给出以下操作的结果：StrLength(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s, A ,4);StrReplace(

26、s, STUDENT ,q);StrCat(StrCat(sub1,t), StrCat(sub2,q); 参考答案 StrLength(s)= 14;sub1= I AM A_; sub2= ; StrIndex(s, A ,4)=6;StrReplace(s, STUDENT ,q)= I AM A WORKER;StrCat(StrCat(sub1,t), StrCat(sub2,q)= I AM A GOOD WORKER ;2.编写算法，实现串的根本操作StrReplace(S,T,V) 。3.假设以块链构造表示串，块的大小为1，且附设头结点。试编写算法，实现串的以下根本操作：Str

27、Asign(S,chars)；StrCopy(S,T)； StrCompare(S,T)； StrLength(S)；StrCat(S,T) ； SubString(Sub,S,pos,len)。 说明 ：用单链表实现。4表达以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。5： S= (xyz)* ,T= (x+z)*y。试利用联接、求子串和置换等操作，将S 转换为T.6 S 和 T 是用结点大小为1 的单链表存储的两个串， 设计一个算法将串S 中首次与 T匹配的子串逆置。7 S 是用结点大小为4 的单链表存储的串,分别编写算法在第k 个字符后插入串T，

28、及从第 k 个字符删除len 个字符。以下算法用定长顺序串：8写以下算法： 1将顺序串r 中所有值为 ch1 的字符换成 ch2 的字符。 2将顺序串r 中所有字符按照相反的次序仍存放在r 中。 3从顺序串r 中删除其值等于 ch 的所有字符。 4从顺序串r1 中第 index 个字符起求出首次与串r2 一样的子串的起始位置。 5从顺序串r 中删除所有与串r1 一样的子串。9写一个函数将顺序串s1 中的第 i 个字符到第j 个字符之间的字符用s2 串替换。提示 ： 1 用静态顺序串2先移位，后复制10写算法，实现顺序串的根本操作StrCompare(s,t)。11写算法，实现顺序串的根本操作S

29、trReplace(&s,t,v)。提示 ：专业资料整理WORD格式 1被替换子串 定位相当于第9 题中 i（ 2被替换子串 后面的字符 左移 或右移 为 替换子串 准备房间（ 3替换子串 入住复制 4重复上述，直到 ,第五章答案5.2 设有三对角矩阵 An×n ,将其三条对角线上的元素逐行的存于数组 B1.3n-2 中，使得 Bk=a ij，求： 1 用 i,j 表示 k 的下标变换公式； 2 用 k 表示 i 、 j 的下标变换公式。【解答】 1 k=2(i-1)+j专业资料整理WORD格式(2) i=k/3+1, j=k/3+k%35.4 在稀疏矩阵的快速转置算法5.2

30、 取整， %取余中，将计算 positioncol的方法稍加改动，使算法只占专业资料整理WORD格式用一个辅助向量空间。【解答】算法一专业资料整理WORD格式FastTransposeTSMatrix(TSMartrixA,TSMatrix*B)专业资料整理WORD格式/* 把矩阵 A 转置到 B 所指向的矩阵中去，矩阵用三元组表表示int col,t,p,q;int positionMAXSIZE;B->len=A.len;B->n=A.m;B->m=A.n;if(B->len>0)*/专业资料整理WORD格式position1=1;for(t=1;t<=

31、A.len;t+)专业资料整理WORD格式positionA.datat.col+1+;/*positioncol存放第col-1列非零元素的个专业资料整理WORD格式数 , 即利用 poscol 来记录第 col-1 列中非零元素的个数 */* 求 col 列中第一个非零元素在 B.data 的位置，存放在 positioncol 中 */ for(col=2;col<=A.n;col+)positioncol=positioncol+positioncol-1;for(p=1;p<A.len;p+)col=A.datap.col;q=positioncol;B->data

32、q.row=A.datap.col;B->dataq.col=A.datap.row;B->dataq.e=A.datap.e;Positioncol+;算法 (二)FastTransposeTSMatrix(TSMartrixA,TSMatrix*B)int col,t,p,q;int positionMAXSIZE;B->len=A.len;B->n=A.m;B->m=A.n;if(B->len>0)for(col=1;col<=A.n;col+)positioncol=0;for(t=1;t<=A.len;t+)专业资料整理WORD格

33、式positionA.datat.col+;/*计算每一列的非零元素的个数*/*从最后一列起求每一列中第一个非零元素在B.data 中的位置，存放在positioncol中 */for(col=A.n,t=A.len;col>0;col-)t=t-positioncol;positioncol=t+1;for(p=1;p<A.len;p+)col=A.datap.col;q=positioncol;B->dataq.row=A.datap.col;B->dataq.col=A.datap.row;B->dataq.e=A.datap.e;Positioncol+;

34、5.6 画出下面广义表的两种存储构造图示：(a), b), ( ), d), (e, f)【解答】第一种存储构造专业资料整理WORD格式第二种存储构造专业资料整理WORD格式5.7 求以下广义表运算的结果： 1 HEAD(a,b),(c,d);(a,b) 2 TAIL(a,b),(c,d);(c,d) 3 TAILHEAD(a,b),(c,d);(b) 4 HEADTAILHEAD(a,b),(c,d);b 5 TAILHEADTAIL(a,b),(c,d);(d)第六章答案专业资料整理WORD格式6 1 分别画出具有3 个结点的树和【解答】具有 3 个结点的树3 个结点的二叉树的所有不同形态

35、。具有 3 个结点的二叉树专业资料整理WORD格式6.3 一棵度为 k 的树中有 n 1个度为 1 的结点， n 2个度为 2的结点，n k个度为 k的结点，那么该树中有多少个叶子结点？【解答】设树中结点总数为n, 那么 n=n 0 + n 1 + + n k树中分支数目为 B, 那么 B=n 1 + 2n 2 + 3n3 + + kn kn= B + 1因为除根结点外，每个结点均对应一个进入它的分支，所以有即 n 0 + n 1 + + n k = n 1 + 2n 2 + 3n 3 + + kn k + 1由上式可得叶子结点数为： n 0 = n 2 + 2n 3 + + (k -1)n

36、k + 16.5二叉树有 50 个叶子结点，那么该二叉树的总结点数至少应有多少个？【解答】 n 0表示叶子结点数， n 2表示度为 2 的结点数，那么 n 0 = n 2+1所以 n 2= n 01=49 ，当二叉树中没有度为1 的结点时，总结点数 n=n 0+n 2=996.6试分别找出满足以下条件的所有二叉树:(1) 前序序列与中序序列一样 ;(2) 中序序列与后序序列一样 ;(3) 前序序列与后序序列一样。【解答】(1) 前序与中序一样：空树或缺左子树的单支树；(2) 中序与后序一样：空树或缺右子树的单支树；(3) 前序与后序一样：空树或只有根结点的二叉树。6.9假设通讯的电文仅由8 个

37、字母组成，字母在电文中出现的频率分别为：0.07 ， 0.19 ， 0.02 ，0.06 ， 0.32 ， 0.03 ， 0.21 ， 0.10请为这 8 个字母设计哈夫曼编码。【解答】构造哈夫曼树如下：专业资料整理WORD格式哈夫曼编码为：I 1： 11111I 5： 1100I 2：11110I6： 10I3：1110I： 017I 4：1101I8：006.11 画出如以下列图所示树对应的二叉树。【解答】专业资料整理WORD格式6.15 分别写出算法，实现在中序线索二叉树继。在先序线索二叉树T 中，查找给定结点中，查找给定结点*p 在后序序列中的前驱。T 中查找给定结点 *p 在中序序列

38、中的前驱与后 *p 在先序序列中的后继。在后序线索二叉树T专业资料整理WORD格式 1找结点的中序前驱结点专业资料整理WORD格式BiTNode*InPre (BiTNode*p)/*在中序线索二叉树中查找p 的中序前驱结点，并用pre if (p->Ltag= =1)pre = p->LChild;/*直接利用线索else指针返回结果 */*/专业资料整理WORD格式/* 在 p 的左子树中查找“最右下端结点*/for ( q=p->LChild; q->Rtag= =0; q=q->RChild);pre = q;return (pre); 2找结点的中序后继

39、结点专业资料整理WORD格式BiTNode*InSucc (BiTNode*p)专业资料整理WORD格式/*在中序线索二叉树中查找p 的中序后继结点，并用succ if (p->Rtag= =1)succ = p->RChild;/*直接利用线索else/* 在 p 的右子树中查找“最左下端结点*/指针返回结果*/*/专业资料整理WORD格式for ( q=p->RChild; q->Ltag= =0; q=q->LChild);succ= q;return (succ);(3) 找结点的先序后继结点专业资料整理WORD格式BiTNode*PreSucc (BiT

40、Node*p)专业资料整理WORD格式/*在先序线索二叉树中查找p 的先序后继结点，并用succ指针返回结果*/专业资料整理WORD格式 if (p->Ltag= =0)succ = p->LChild;专业资料整理WORD格式elsesucc= p->RChild;专业资料整理WORD格式return (succ);(4) 找结点的后序前驱结点专业资料整理WORD格式BiTNode*SuccPre (BiTNode*p)专业资料整理WORD格式/*在后序线索二叉树中查找p 的后序前驱结点，并用pre指针返回结果*/专业资料整理WORD格式 if (p->Ltag= =

41、1)pre = p->LChild;专业资料整理WORD格式elsepre= p->RChild;专业资料整理WORD格式return (pre);6.21 二叉树按照二叉链表方式存储，利用栈的根本操作写出先序遍历非递归形式的算法。【解答】VoidPreOrder(BiTreeroot)/*先序遍历二叉树的非递归算法*/InitStack(&S);专业资料整理WORD格式p=root;while(p!=NULL | !IsEmpty(S) ) if(p!=NULL)Visit(p->data); push(&S,p);p=p->Lchild;elsePo

42、p(&S,&p);p=p->RChild;6.24 二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进展交换。【解答】算法 (一)Voidexchange ( BiTreeroot )p=root;if ( p->LChild != NULL | p->RChild != NULL )temp = p->LChild;p->LChild = p->RChild;p->RChild = temp;exchange ( p->LChild );exchange ( p->RChild );算法 (二)Voidexchange