数据结构课后习题答案(耿国华版.docx

《数据结构课后习题答案(耿国华版.docx》由会员分享，可在线阅读，更多相关《数据结构课后习题答案(耿国华版.docx（17页珍藏版）》请在优知文库上搜索。

1、第1章绪论2、(1)(2)(3)3、(1)A(2)C(3)Cf*骷下3中“日得语句频度for(j=ly=i;j+)for(k=l;k=j;k+)x=x+l;【解答】=+l得语句频度为：T(n)=1+(1+2)+(1+2+3)+.+(1+2+n)=n(n+l)(n2)6编写算法，求一元多项式p。(X)=a。+a,x+azX2+aXn得值P(X)并确定算法中每一语句得执行次数与整个算法得时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幕函数.注意：本题中得输入为a,(i=01,n)、X与n,输出为P。(x)。算法得输入与输出采用下列方法(1)通过参数表中得参数显式传递(2)通过全局变量隐式

2、传递。讨论两种方法得优缺点，并在算法中以您认为较好得一种实现输入输出.【解答】(1)通过参数表中得参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。(2)通过全局变量隐式传递优点：减少实参预形参得个数，从而减少内存空间以及传递数据时得时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(int,in;floatx,alp;printf(hn=,3;scanff%fj(fen);PrintfrX=;)seanf(tt%fx);for(i=0;in;i+)scanf

3、(%f,&ai;/*执行次数：n次P=aO;for(i=1;i=n;i+)p=p+ai*x;/*执行次数：n次*/X=x*x;)printf(%f,p);)算法得时间复杂度：T(nMXn)通过参数表中得参数显式传递fIoatPolyValue(floata,floatx,intn)f1oatp,s;int;i9;for(=l;inext=S;BP-next=Pnext-next;CP-next=Snext;DSneXt=P-next;ES-nexl=L;FS-neXt=NULL;GQ=P;Hwhile(P-next!=Q)P=P-next;Iwhile(Pnext!=NULL)P=Pnext;

4、JP=Q;KP=L:1.L=S;ML=P;(3)D(5)D(6)A试分别以不同得存储结构实现单线表得就地逆置算法，即在原表得存储空间将线性表a,a)逆置为(a,a-,.,a)。【解答】(1)用一维数组作为存储结构voidinvert(SeqList*L,int*num)i11tj;ElemTyPe【mp;for(j=0;jnext=NULL)return;*链表为空*/p=L-next;q=p-next;pnext=NULL;/*摘下第一个结点，生成初始逆置表*/whik(q!=NULL)/*从第二个结点起挨次头插入当前逆置表*/r=q-next;q-neXt=L-next;1.-next=q

5、;q=r;将线性表A=(al,a2,am),B=(bl,b2,bn)合并成线性表C,C=(al,bl,am,bm,bm+l,、bn)当mn时，线性表A、B、C以单链表作为存储结构，且C表利用A表与B表中得结点空间构成.注意：单链表得长度值m与n均未显式存储.【解答】算法如下：1.inkListmerge(LinkListA,LinkListBLinkListC)Node*pa,*qa,*pb,*qb,*p;pa=Anext;*pa表示A得当前结点*/pb=B-next;p=A;/利用P来指向新连接得表得表尾，初始值指向表A得头结点*/while(pa!=NULL&pb!=NULL)/利用尾插法

6、建立连接之后得链表*/qa=pa-nextqb=qbnext;p-next=pa;/咬替选择表A与表B中得结点连接到新链表中；*/P=P也pnext=pb;P=Pb;pa=qa;pb=qb;if(p!=NULDpnext=p；*A得长度大于B得长度*/if(pb!=NULL)p-next=pb;*B得长度大于A得长度*/C=A;Return(C)；实习题约瑟夫环问题约瑟夫问题得一种描述为:编号1,2,n得n个人按顺时针方向围坐一圈,每一个人持有一个密码(正整数)。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时住手报数.报m得人出列，将她得密码作为新得m值，从她在顺时

7、针方向上得下一个人开始重新从1报数，如此下去，直至所有得人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构摹拟此过程，按照出列顺序打印出各人得编号。例如m得初值为20；n=7,7个人得密码挨次就是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,35【解答】算法如下：typfcfstroctNode(irtpesswOhiitnum；stnictNode*next；No*Liribtvet!JCSephis0(1.irtfctLNOde*p,*r,*q;intm,n,C,j；1.=(Node*)ma11oc(sizeof(Node);/*初始化单向循环链表*/

8、if(L=NULL)Pintfr链表申请不到空间！)；return；=NULL;r=Lrint请输入数据n得值(n)0):今SCanf(%d”,&nKfor(j=l：j=n：j+)*建立链表*/(p=(Node*)malloc(sizeof(Node)；ifp(!=MUL)(Printf(请输入第d个人得密码：scanf(%,&C)；ppassWord=C;p-nUm=j；next=r=p;p)next=L-next；print请输入第一个报数上限值m(m0):;) sc a n R%d.&m);n)；printf,出列得顺序为：nq=L;P=Lnext;while(n!=l)/针算出列得顺序

9、*/(j=LWhilenext;j+;)printf(dnum);m=ppassword;/获得新密码*/n-,qnext=pnext;*p出列r=p;p=p-next;free(r);printf(n-num);第3章限定性线性表一栈与队列第三章答案按3、1(b)所示铁道(两侧铁道均为单向行驶道)进行车箱调度，回答：(1)如进站得车箱序列为123,则可能得到得出站车箱序列就是什么？(2)如进站得车箱序列为123456,能否得到435612与135426得出站序列，并说明原因(即写出以“表示进栈、“表示出栈得栈序列操作)。【解答】(1)可能得到得出站车箱序列就是：123、132、213、231

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

11、头结点)判断栈空：如果Iop-next=NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈得元素，此时栈满。4照四则运算加、减、乘、除与基运算得优先惯例，画出对下列表达式求值时操作数栈与运算符栈得变化过程：A-B*CD+ETF【解答】写一个算法，判断挨次读入得一个以为结束符得字母序列，就是否形如，序列1&序列2,得字符序列.序列1与序列2中都不含，且序列2就是序列1得逆序列.例如，,a+bfeba,就是属于该模式得字符序列，而1+&3-1，则不就是。【解答】算法如下：intIsHuiWenOStack*S;Charch,temp;InitStack(&S);PrintH”

12、请输入字符序列：0Ch=getchar();While(ch!=&)Push(feS,ch);ch=getchar();do1得逆序列*/ch=getchar(),Pop(&S,&temp);if(ch!=temp)序列1得逆序列*/retum(FALSE);while(ch!=if(ch=&return(TRUE);是序列1得逆序列3*序列1入栈*/删断序列2就是否就是序列printf(nNO);&!IsHmpty(&S)IsEmpty(&S)Printf(“YES”);/*序列2不就是/*序列2就e1sereturn(FALSE);printfnNo,);*IsHuiWen(*/8要求循环队列不