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

第1章绪论2、(1)×(2)×(3)3、(1)A(2)C(3)C'f*骷下"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)(n÷2)6编写算法，求一元多项式p。(X)=a。+a,x+azX2+aXn得值P(X)并确定算法中每一语句得执行次数与整个算法得时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幕函数.注意：本题中得输入为a,(i=01,n)、X与n,输出为P。(x)。算法得输入与输出采用下列方法(1)通过参数表中得参数显式传递(2)通过全局变量隐式传递。讨论两种方法得优缺点，并在算法中以您认为较好得一种实现输入输出.【解答】(1)通过参数表中得参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。(2)通过全局变量隐式传递优点：减少实参预形参得个数，从而减少内存空间以及传递数据时得时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(int,in;floatx,alp;printf(hn=,3;scanff%fj(fen);PrintfrX=")seanf(tt%fx);for(i=0;i<n;i+)scanf(%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;i<=n;i+)s=s+a i* p;P=P*x;)re turn(p);算法得时间复杂度：T(n)=O(n)t行次数：n次*/第2章线性表习题1、填空：(1)在顺序表中插入或者删除一个元素，需要平均挪移二生元素，具体挪移得元素个数与捷或者删除得位置有关。线性表有顺序与链式两种存储结构,在顺序表中,线性表得长度在数组定义时就已经确定，就是静态保存,在链式表中，整个链表由“头指针”来表示，单链表得长度就是动态保存。(3)在顺序表中，逻辑上相邻得元素，其物理位置二一相邻.在单链表中，逻辑上相邻得元素，其物理位置不一定相邻。(4)在带头结点得非空单链表中，头结点得存储位置由头指针指示，首元素结点得存储位置由头结点指示，除首元素结点外，其它任一元素结点得存储位置由其直接前趋得neXt域指示.2、选择题(I)A(2)已知L就是无表头结点得单链表，且P结点既不就是首元素结点，也不就是尾元素结点。按要求从下列语句中选择合适得语句序列.a、 在P结点后插入S结点得语句序列就是：E、A。b、 在P结点前插入S结点得语句序列就是：H、L、I、E、A。c、在表首插入S结点得语句序列就是；F、M。d、在表尾插入S结点得语句序列就是：L、J、A、G。供选择得语句有：AP>next=S;BP->next=P>next->next;CP->next=S>next;DS>neXt=P->next;ES->nexl=L;FS->neXt=NULL;GQ=P;Hwhile(P->next!=Q)P=P->next;Iwhile(P>next!=NULL)P=P>next;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;j<=(*num-1)/2;+)tmp=Lj1.j毛*num-j-l;1.*num-j1=tmp;J(2)用单链表作为存储结构voidinvert(LinkListL)Node*p,*q,*r;if(L>next=NULL)return;*链表为空*/p=L->next;q=p->next;p>next=NULL;/*摘下第一个结点，生成初始逆置表*/whik(q!=NULL)/*从第二个结点起挨次头插入当前逆置表*/r=q->next;q->neXt=L->next;1.->next=q;q=r;将线性表A=(al,a2,am),B=(bl,b2,bn)合并成线性表C,C=(al,bl,am,bm,bm+l,、bn)当m<=n时，或者C=(al,bl,an,bn,an+l,am)当m>n时，线性表A、B、C以单链表作为存储结构，且C表利用A表与B表中得结点空间构成.注意：单链表得长度值m与n均未显式存储.【解答】算法如下：1.inkListmerge(LinkListA,LinkListBLinkListC)Node*pa,*qa,*pb,*qb,*p;pa=A>next;*pa表示A得当前结点*/pb=B->next;p=A;/利用P来指向新连接得表得表尾，初始值指向表A得头结点*/while(pa!=NULL&&pb!=NULL)/利用尾插法建立连接之后得链表*/qa=pa->nextqb=qb>next;p->next=pa;/咬替选择表A与表B中得结点连接到新链表中；*/P=P也p>next=pb;P=Pb;pa=qa;pb=qb;if(p!=NULDp>next=p；*A得长度大于B得长度*/if(pb!=NULL)p->next=pb;*B得长度大于A得长度*/C=A;Return(C)；实习题约瑟夫环问题约瑟夫问题得一种描述为:编号1,2,n得n个人按顺时针方向围坐一圈,每一个人持有一个密码(正整数)。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时住手报数.报m得人出列，将她得密码作为新得m值，从她在顺时针方向上得下一个人开始重新从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);/*初始化单向循环链表*/if(L=NULL)Pintfr链表申请不到空间！")；return；1.>net=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)；p>passWord=C;p->nUm=j；next=r=p;p)next=L->next；print请输入第一个报数上限值m(m>0):") sc a n R'%d''.&m);n)；printf,出列得顺序为：nq=L;P=L>next;while(n!=l)/针算出列得顺序*/(j=LWhile<m)/*计算当前出列得人选P*/(q=P；*q为当前结点P得前驱结点*/p=p->next;j+;)printf(d>num);m=p>password;/获得新密码*/n-,q>next=p>next;*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、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满：如果S>top=Stack_Size-1表示栈满。(2)链栈(top为栈顶指针，指向当前栈顶元素前面得头结点)判断栈空：如果Iop->next=NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈得元素，此时栈满。4照四则运算加、减、乘、除与基运算得优先惯例，画出对下列表达式求值时操作数栈与运算符栈得变化过程：A-B*CD+ETF【解答】写一个算法，判断挨次读入得一个以为结束符得字母序列，就是否形如，序列1&序列2,得字符序列.序列1与序列2中都不含，且序列2就是序列1得逆序列.例如，,a+b<feb÷a,就是属于该模式得字符序列，而'1+&3-1，则不就是。【解答】算法如下：intIsHuiWenOStack*S;Charch,temp;InitStack(&S);PrintH”请输入字符序列：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要求循环队列不