第一章答案
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试编写算法，求pn(x)=a o+aix+a2X2+ ................ .+a nxn的值Pn(xo),并确定算法中每一语句的
执行次数和整个算法的时间复杂度， 要求时间复杂度尽可能小， 规定算法中不能使用求 幕函数。注意：本题中的输入为
ai(i=0,1,…n) x和n,输出为Pn(xo)。算法的输入和输
出采用下列方法( 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; p=p*x;} return(p); } /* 执行次数 :n 次*/ 算法的时间复杂度： T(n)=O(n) 第二章答案 2.7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表 (ai,a2,…,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 )用单链表作为存储结构 void in vert(L in L) kList { Node *p, *q, *r; return; /*链表为空*/ if(L-> next ==NULL) p=L->n ext; q=p->n ext; /*摘下第一个结点，生成初始逆置表 */ p-> next=NULL; /*从第二个结点起依次头插入当前逆置表 */ while(q!=NULL) C=(a1,b1, an,bn,an+1, am)当m>n时,线性表 A、B、C以单链表作为存{ 储结构， r=q->n ext; q->n 且C表利用A表和B表中的结点空间构成。 注意：单链表的长度值 m和ext=L->n ext; n均未显式存储。 L->n ext=q; q=r; 【解答】算法如下： } Lin kList merge(Li nkList A, Li nkList B, Li nkList C) } { Node *pa, *qa, *pb, *qb, *p; 2.11 将 线 性 表 A=(a1,a2, am), B=(b1,b2,……bn) 合并成线性表 C, C=(a1,b1, ........am,bm,bm+1, ........ .bn) 当 m<=n 时 ， 或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 的长度 */ 欢迎下载 2 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 【解答】 OVS OPTR OVS OPTR OVS OPTR '+,^OPTR,/1 生成 C 生成日弋 I ------------------------- B D T⑴ A 运篦菇果T(1) A - 运算拮杲 □VS OPT 口 ■+M=OPTR：＜ 生康 OPTR^T空进腹 OVS F 运筐结果T(3) T(3) E T(3) OPTR + OPTR OVS 右边界 fF ' OVS 圭咸EtF 1 ---------------------- ----- . ----------------------- 1-—―- 运直结果T(4) 右边畀第8PT尺:十, 主咸T⑶+T⑷ r— ------------ T⑷ + 這倉结果T(5) T⑸ 1&序 3. 5写一个算法，判断依次读入的一个以 @为结束符的字母序列，是否形如‘序列 列2 '的字符序列。序列 1和序列2中都不含‘ & 且序列2是序列1的逆序列。例 欢迎下载 3
耿国华数据结构习题答案完整版
