《耿国华数据结构习题答案完整版》由会员分享，可在线阅读，更多相关《耿国华数据结构习题答案完整版（44页珍藏版）》请在金锄头文库上搜索。
1、 第一章答案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试编写算法，求pn(x)=a0+a1x+a2x2+.+anxn的值pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：此题中的输入为ai(i=0,1,n)、x和n,输出为Pn(x0)。算法的输入和输出采用以下方法1通过参数表中的参数显式传递2通过全局
2、变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】1通过参数表中的参数显式传递优点：当没有调用函数时，不占用存，调用完毕后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。2通过全局变量隐式传递优点：减少实参与形参的个数，从而减少存空间以与传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue() int i,n;float x,a,p; printf(“nn=); scanf(“%f,&n); printf(“nx=); scanf(“%f,&x);for(i=0;in;
3、i+) scanf(“%f ,&ai); /*执行次数：n次 */ p=a0; for(i=1;i=n;i+)p=p+ai*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=a0;for(i=1;i=n;i+)s=s+ai*p; /*执行次数:n次*/ p=p*x;return(p);算法的时间复杂度：T(n)=O(n)第二章答案2.7试分别以不同的存储结构实现单线表的就地逆置算法，
4、即在原表的存储空间将线性表a1,a2,an逆置为(an,an-1,a1)。【解答】1用一维数组作为存储结构 void invert(SeqList *L, int *num) int j; ElemType tmp;for(j=0;jnext =NULL) return; /*链表为空*/ p=L-next; q=p-next; p-next=NULL; /* 摘下第一个结点，生成初始逆置表 */while(q!=NULL) /* 从第二个结点起依次头插入当前逆置表 */ r=q-next;q-next=L-next;L-next=q;q=r; 2.11将线性表A=(a1,a2,am), B=
5、(b1,b2,bn)合并成线性表C, C=(a1,b1,am,bm,bm+1,.bn) 当mn时,线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。【解答】算法如下：LinkList merge(LinkList A, LinkList B, LinkList C) Node *pa, *qa, *pb, *qb, *p; pa=A-next; /*pa表示A的当前结点*/ pb=B-next; p=A; / *利用p来指向新连接的表的表尾，初始值指向表A的头结点*/ while(pa!=NULL & pb!=NULL) /*利
6、用尾插法建立连接之后的链表*/ qa=pa-next; qb=qb-next; p-next=pa; /*交替选择表A和表B中的结点连接到新链表中；*/p=pa;p-next=pb;p=pb; pa=qa;pb=qb;if(pa!=NULL) p-next=pa; /*A的长度大于B的长度*/ if(pb!=NULL) p-next=pb; /*B的长度大于A的长度*/C=A; Return(C);第三章答案3.1按3.1(b)所示铁道两侧铁道均为单向行驶道进展车厢调度，答复：（1） 如进站的车厢序列为123，那么可能得到的出站车厢序列是什么？（2） 如进站的车厢序列为123456，能否得到4
7、35612和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)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用来存放栈顶元素
8、的下标判断栈S空：如果S-top=-1表示栈空。判断栈S满：如果S-top=Stack_Size-1表示栈满。(2) 链栈top为栈顶指针，指向当前栈顶元素前面的头结点判断栈空：如果top-next=NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。3 4照四那么运算加、减、乘、除和幂运算的优先惯例，画出对以下表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+EF【解答】3 5写一个算法，判断依次读入的一个以为完毕符的字母序列，是否形如序列1&序列2的字符序列。序列1和序列2中都不含&，且序列2是序列1 的逆序列。例如，a+b&b+a是属于该模式
9、的字符序列，而1+3&3-1那么不是。【解答】算法如下： int IsHuiWen() Stack *S; Char ch,temp; InitStack(&S); Printf(“n请输入字符序列：); Ch=getchar();While( ch!=&) /*序列1入栈*/ Push(&S,ch); ch=getchar();do /*判断序列2是否是序列1的逆序列*/ ch=getchar(); Pop(&S,&temp); if(ch!= temp) /*序列2不是序列1的逆序列*/ return(FALSE); printf(“nNO); while(ch!= & !IsEmpty(
10、&S)if(ch = = & IsEmpty(&S) return(TRUE); printf(“nYES); /*序列2是序列1的逆序列*/else return(FALSE); printf(“nNO); /*IsHuiWen()*/3.8 要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针一样时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法：int EnterQueue(SeqQueue *Q, QueueElementType x) /*将元素x入队*/ if(Q-front=Q-front & tag=1) /*队满*
11、/ return(FALSE); if(Q-front=Q-front & tag=0) /*x入队前队空，x入队后重新设置标志*/ tag=1;Q-elememtQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /*设置队尾指针*/Return(TRUE); 出队算法： int DeleteQueue( SeqQueue *Q , QueueElementType *x) /*删除队头元素，用x返回其值*/if(Q-front=Q-rear & tag=0) /*队空*/return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front
12、+1)%MAXSIZE; /*重新设置队头指针*/if(Q-front=Q-rear) tag=0; /*队头元素出队后队列为空，重新设置标志域*/Return(TUUE); 编写求解Hanoi问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法： void hanoi (int n ,char x, char y, char z) /*将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规那么搬到塔座Z上，Y可用做辅助塔座*/ if(n = =1) move(x,1,z); else Hanoi(n-1,x,z,y); move(x, n, z);Hanoi(n-1, y,x,z); Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B): Hanoi(1,A,B,C) move(A-C) 1号搬到C Move(A-B)
