耿国华数据结构习题答案完整版
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)/6
1. 4试编写算法，求p n(x)=a o+a i x+a2X2+ ................ .+a n x n的值P n(x o),并确定算法中每一语句的
执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幕函数。注意：本题中的输入为a i(i=0,1,…n) x和n,输出为P n(x o)。算法的输入和输
出采用下列方法( 1)通过参数表中的参数显式传递( 2)通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。
【解答】
( 1)通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。
缺点：形参须与实参对应，且返回值数量有限。
( 2)通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差
算法如下：通过全局变量隐式传递参数
PolyValue()
{ int i,n;
float x,a[],p;
printf( “nn=” );
scanf( “%f”,&n);
printf( “nx=” );
scanf( “ %f” ,&x);
for(i=0;i scanf( “%f ”,&a[i]); /*执行次数：n 次*/ p=a[0]; for(i=1;i<=n;i++) { p=p+a[i]*x; /*执行次数：n 次*/ x=x*x;} printf( “%f”,p); } 算法的时间复杂度：T(n)=O(n) 通过参数表中的参数显式传递 float PolyValue(float a[ ], float x, int n) { float p,s; int i; p=x; s=a[0]; for(i=1;i<=n;i++) {s=s+a[i]*p; /* 执行次数:n 次*/ p=p*x;} return(p); } 算法的时间复杂度：T(n)=O(n) 2.7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表 (a i ,a 2,…,a )逆置为(a n ,a n-1,…,ai)o 【解答】(1)用一维数组作为存储结构 void in vert(SeqList *L, int *num) { int j; ElemType tmp; for(j=0;j<=(* nu m-1)/2;j++) { tmp=L[j]; L[j]=L[* nu m-j-1]; L[* num-j-1]=tmp;} } (2 )用单链表作为存储结构 L) return; /*链表为空*/ /*摘下第一个结点，生成初始逆置表 */ /*从第二个结点起依次头插入当前逆置表 */ C=(a1,b1, an,bn,an+1, a m)当m>n 时,线性表 A 、B 、C 以单链表作为存储结构， 且C 表利用A 表和B 表中的结点空间构成。 注意：单链表的长度值 m 和n 均未显式存储。 【解答】算法如下： Lin kList merge(Li nkList A, Li nkList B, Li nkList C) { Node *pa, *qa, *pb, *qb, *p; pa=A->next; /*pa 表示A 的当前结点*/ pb=B->n ext; p=A; / *利用p 来指向新连接的表的表尾，初始值指向表 A 的头结点*/ while(pa!=NULL && pb!=NULL) /*利用尾插法建立连接之后的链表 */ { qa=pa->n ext; qb=qb->n ext; p->next=pa; /*交替选择表A 和表B 中的结点连接到新链表中； */ p=pa; p->n ext=pb; p=pb; pa=qa; pb=qb; } if(pa!=NULL) p->next=pa; /*A 的长度大于 B 的长度 */ if(pb!=NULL) p->next=pb; /*B 的长度大于 A 的长度 */ void in vert(L in kList { Node *p, *q, *r; if(L-> next ==NULL) p=L->n ext; q=p->n ext; p-> next=NULL; while(q!=NULL) { r=q->n ext; q->n ext=L->n ext; L->n ext=q; q=r; } } 2.11 将 线 性 表 A=(a1,a2, am), C=(a1,b1, ........am,bm,bm+1, ........ .bn) B=(b1,b2,……bn) 当 m<=n 合并成线性表 时 ， C, 或 C=A; Return(C); } 第三章答案 3.1按3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答： (1) 如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？ (2) 如进站的车厢序列为 123456，能否得到435612和135426的出站序列，并说 明原因(即写出以“ S ”表示进栈、“ X ”表示出栈的栈序列操作)。 【解答】 (1 )可能得到的出站车厢序列是： 123、132、213、231、321。 ⑵不能得到435612的出站序列。 因为有 S(1)S(2)S(3)S(4)X(4)X(3)S(5)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 表示栈空。 判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。 3. 4照四则运算加、减、乘、除和幕运算的优先惯例，画出对下列表达式求值时操作数栈 和运算符栈的变化过程： A-B*C/D+E f F 【解答】 3. 5写一个算法，判断依次读入的一个以 @为结束符的字母序列，是否形如‘序列 1&序 列2 '的字符序列。序列 1和序列2中都不含‘ & 且序列2是序列1的逆序列。例 C B A 生成日弋 I ------------------------- 运篦菇果T(1) D T ⑴ A - OVS ■+M =OPTR ：＜ 生康 运筐结果T(3) T(3) F E T(3) + OVS OPTR OVS OPTR 右边界 f F ' 圭咸EtF 1 ---------------------- ----- . 右边畀第8PT 尺:十, 主咸 T ⑶+T ⑷ r — ------------ ----------------------- 1-—―- 运直结果T(4) T ⑷ + 這倉结果T(5) T ⑸ □VS OPT 口 OVS OPTR '+,^OPTR ,/1 生成 运算拮杲 OVS OPTR OVS OPTR OPTR^T 空进腹 【解答】算法如下: int IsHuiWe n() { Stack *S; Char ch,temp; In itStack(&S); Printf( “请输入字符序列：”); 3.8要求循环队列不损失一个空间全部都能得到利用，设置一个标志 tag,以tag 为0或1 来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。 【解答】入队算法： tag==1) /* 队满 */ tag==0) /*x 入队前队空，x 入队后重新设置标志 tag=1; Q->elememt[Q->rear]=x; Q->rear=(Q->rear+1)%MAXSIZE; Return(TRUE); } 出队算法： int DeleteQueue( SeqQueue *Q , QueueEleme ntType *x) { /*删除队头元素，用 x 返回其值*/ if(Q->front==Q->rear && tag==0) /*队空 */ return(FALSE); *x=Q->eleme nt[Q->fro nt]; Q->fro nt=(Q->fro nt+1)%MAXSIZE; /* 重新设置队头指针 */ if(Q->fro nt==Q->rear) tag=0; /*队头元素出队后队列为空，重新设置标志域 */ Return(TUUE); } 编写求解Hanoi 问题的算法，并给出三个盘子搬动时的递归调用过程。 【解答】算法： void hano i (i nt n ,char x, char y, char z) 如，’a+b&b+a 是属于该模式的字符序列，而 '1+3&31'则不是。 Ch=getchar(); While( ch!=&) { Push(&S,ch); ch=getchar(); } do { ch=getchar(); Pop(&S, &temp); if(ch!= temp) { re turn(FALSE); /*序列 printf( nNO );} } while(ch!=@ if(ch = = @ && { return(TRUE); else {return(FALSE); }/*lsHuiWe n()*/ && !IsEmpty (&S)) IsEmpty (&S)) printf( n'YES' );} printf( nNO );} 1入栈*/ /*判断序列2是否是序列1的逆序列*/ /*序列2不是序列1的逆序列*/ /*序列2是序列1的逆序列*/ int En terQueue(SeqQueue { /*将元素x 入队*/ *Q, QueueEleme ntType x) if(Q->fro nt==Q->fro nt && return(FALSE); if(Q->fro nt==Q->fro nt && */ /*设置队尾指针*/ { /*将塔座X 上按直径由小到大且至上而下编号为 1到n 的n 个圆盘按规则搬到塔座 Z 上，Y 可用做辅助塔座*/ if(n = =1) move(x,1,z); else { Han oi( n-1,x,z,y); move(x, n, z); Han oi( n-1, y,x,z); } } Han oi(3,A,B,C)的递归调用过程: 第四章答案 4.2编写算法，实现串的基本操作 StrReplace(S,T,V)。 【解答】算法如下： int strReplace(SStri ng S,SStri ng T, SStri ng V) {/*用串V 替换S 中的所有子串T */ int pos,i; pos=strIndex(S,1,T); /*求S 中子串T 第一次出现的位置*/ if(pos = = 0) return(O); while(pos!=0) /*用串V 替换S 中的所有子串 T */ { switch(T.le n-V.le n) { case 0: /*串T 的长度等于串V 的长度*/ for(i=0;i<=V 」en ;i++) /*用V 替换T*/ S->ch[pos+i]=V.ch[i]; case >0: /*串T 的长度大于串V 的长度*/ for(i=pos+t.ie n;i /*将S 中子串T 后的所有字符 置*/ S->ch[i-t.le n+v.le n]=S->ch[i]; 前移T.len-V.len 个位 for(i=0;i<=V 」en ;i++) /*用V 替换T*/ Ha noi(2,A,C,B): Ha noi(1,A,B,C) Move(A->B) Ha noi(1,C,A,B) Move(A->C) Ha noi(2,B,A,C) Ha noi(1,B,C,A) move(A->C) move(C->B) move(B->A) move(A->C) 1号搬到C 2号搬到B 1号搬到B 3号搬到C 1号搬到A 2号搬到C 1号搬到C 4.1 设 s=' I AM A STUDENT', t= ' GOOD, 【解答】StrLe ngth(s)=14; SubStri ng(sub1,s,1,7) SubStri ng(sub2,s,7,1) StrIndex(s,4, ' A )=6; StrReplace(s, ' STUDENT ,q); StrCat(StrCat(sub1,t),StrCat(sub2,q)) WORKER 。 q=' WORKER 。给出下列操作的结果: sub 仁'I AM A sub2=''; s=' I AM A WORKER ; sub 仁'I AM A GOOD