数据结构-C语言描述课后答案

1、第一章绪论一、问答题什么是数据结构？叙述四类基本数据结构的名称与含义。叙述算法的定义与特性。叙述算法的时间复杂度。叙述数据类型的概念。叙述线性结构与非线性结构的差别。叙述面向对彖程序设计语言的特点。在面向对彖程序设计中，类的作用是什么？叙述参数传递的主要方式及特点。叙述抽象数据类型的概念。二、判断题(在各题后填写“Q”或“x”)线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。()算法就是程序。()在高级语言(如C或PASCAL)中，指针类型是原子类型。()三、计算下列程序段中X=X+1的语句频度fdi(i=l;i=n;i+)fol-(j=l;j=lj+)fbr(k=l;k=j;

2、k+)x=x+l;【解答】1=1时:1=(l+l)xl/2=(l+12)/21=2时：1+2=(l+2)x2/2=(2+22)/21=3时:1+2+3=(l+3)x3/2=(3+32J/2i=n时:1+2+3+n=(l+n)xn/2=(n+n2)/2x=x+l的语句频度为：f(n)=(1+2+3+n)+(12+22+32+n2)/2=(l+ii)xn/2+n(n+l)(2n+l)/6/2=n(n+l)(n+2)/6=n3/6+ii2/2+n/3区分语句频度和算法复杂度：O(f(n)=O(n3)四、试编写算法，求一元多项式Pn(x)=a0+alx+a2x2+a3x3+.aiixn的值Pn(xO)

3、,并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幕函数。注意：本题中的输入ai(i=0,l,.,n),x和n,输出为Pn(xO)o通常算法的输入和输出可采用下列两种方式之一：通过参数表中的参数显式传递。通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出【解答】通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时

4、的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValueQiiiti,n；floatx,a,p;piintf(“nn=”)；scanf(“f&n);scanf(“f&x);for(i=0;in;i+)scanf(“f,&ai);/*执行次数：n次*/p=a0;for(i=l;i=n;i+)p=p+a1*x;/*执行次数：ii次*/x=x*x;pmitf(“f,p);算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata,floatx,mtn)floatp,s；inti;P=x；s=a0;for(i=l;ine

5、xt=S;(2)P-next=P-next-next;P-next=S-next;S-next=P-next;S-next=L;S-next=NULL;Q=P;while(P-next!=Q)P=P-next;while(P-next!=NULL)P=P-next;P=Q;TOC o 1-5 h zP=L;L=S;L=P;2.4已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。StatusInsert_SqList(SqList&x)把x插入递增有序表va中if(va.length-r1va.listsize)returnERROR;va.leng

6、th+;fbi(i=va.length-l;va.elemix&i=0;i)va.elemi+1=va.elemi;va.elemi+l=x;returnOK;/IiiserCSqList2.5写一算法，从顺序表中删除自第1个元素开始的k个元素。提示:注意检查1和k的合法性。(集体搬迁，“新房”、“旧房”)以待移动元素下标m(“旧房号”)为中心，计算应移入位置(“新房号”)：for(m=i1+k;mlast;111-H-)Lelemmk=Lelemm;同时以待移动元素卞标m和应移入位置j为中心：以应移入位置j为中心，计算待移动元素下标：2.6已知线性表中的元素(整数)以值递增有序排列，并以单链

7、表作存储结构。试写一高效算法，删除表中所有人于mink且小于maxk的元素(若表中存在这样的元素)，分析你的算法的时间复杂度(注意：mink和maxk是给定的两个参变量，它们的值为任意的整数)。StatusDelete_Between(Linklist&L,mtmaxk)/删除元素递增排列的链表L中值大于imiik且小于maxk的所有元素P=L；xvlule(p-next-datanext;/p是最后一个不人于nuiik的元素if(p-next)如果还有比mink更大的元素q=p-next;xvlule(q-datanext;/q是第一个不小于niaxk的元素p-next=q;/Delete_

8、Between2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表(al,a2，an)逆置为(an,an-lv.,al)o以一维数组作存储结构，设线性表存于a(l:airsize)的前elenum个分屋中。以单链表作存储结构。方法1:在原头结点后重新头插一遍方法2:可设三个同步移动的指针p,q,r,将q的后继I改为p2.8假设两个按元素值递增有序排列的线性表A和E,均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C,并要求利用原表(即A表和E表的)结点空间存放表C.提示:参P.28例21voidmerge(LuikListA;

9、LnikListB:LnikList*C)pa=Anext;pb=Bnext;*C=A;(*C)-next=NULL;wlule(pa!=NULL&pb!=NULL)if(padatadata)smallei-pa;pa=panext;smallernext=(*C)next;/*头插法*/(*C)next=smaller;elsesmallei-pb;pb=pbnext;smallernext=(*C)next;(*C)next=smaller;wliile(pa!=NULL)sniallei-pa;pa=panext;smallernext=(*C)next;(*C)next=smalle

10、r;wliile(pb!=NULL)sniallei-pb;pb=pbnext;smallernext=(*C)next;(*C)next=smaller;LinkListmerge(LiiikListA;LnikListB)LinkListC:pa=Anext;pb=Bnext;C=A;Cnext=NULL;returnC;while(pa|pb)if(pa-datadata|!pb)pc=pa;q=pa-next;pa-next=pre;pa=q;将A的元素插入新表elsepc=pb;q=pb-next;pb-next=pie;pb=q;/B的元素插入新表pre=pc;C=A;A-next

11、=pc;构造新表头/ieverse_meige分析:本算法的思想是，按从小到人的顺序依次把A和E的元素插入新表的头部pc处,最后处理A或E的剩余元素.2.9假设有一个循坏链表的长度人于1,且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趙结点。提示:设指针p指向S结点的前趋的前趋，则p与S有何关系？StatusDelete_Pre(CiLNode*s)/删除单循环链表中结点s的直接前驱p=s;wliile(p-next-next?=s)p=p-next;/找到s的前驱的前驱pp-next=s;returnOK;/Delete_Pre2.10已

12、知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符)，试编写算法来构造三个以循坏链表表示的线性表，使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。StatusLnikList_Divide(LiiikList&L,CiList&A,CiList&B,CiList&C)/把单链表L的元素按类型分为三个循坏链表.CiList为带头结点的单循坏链表类型.s=L-next;A=(CiList*)nialloc(sizeof(CiLNode);p=A;B=(CiList*)malloc(sizeof(CiLNode);q=B;C=(

13、CiList*)malloc(sizeof(CiLNode);r=C;/建立头结点wliile(s)if(isalphabet(s-data)next=s;p=s;elseif(isdigit(s-data)q-next=s;q=s;elser-next=s;r=s;/whilep-next=A;q-next=B:r-next=C;完成循环链表/LuikList_Divide2.11设线性表A=(al,a2,am),B=(bl,b2,.,bn),试写一个按卞列规则合并A、B为线性表C的算法，使得：C=(al,bl,.,ani,bm,bm+1,.,bn)当mn时。线性表A、B、C均以单链表作为存

14、储结构，且C表利用A表和E表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。提示:voidmerge(LuikListA;LnikListB:LnikList*C)或：LuikListmerge(LinkListA;LuikListB)voidmerge1(LuikList&A,LuikList&B.LuikList&C)把链表A和E合并为C.A和B的元素间隔排列，且使用原存储空间p=A-next;q=B-next;C=A;wliile(p&q)s=p-next;p-next=q;将B的元素插入lf(s)t=q-next:q-next=s;如A非空，将A的元素插入p=s;q=t;/w

15、hile/mergel2.12将一个用循坏链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。提示:注明用头指针还是尾指针。voidDivide_LinkedPoly(LnikedPoly&L.&A,&E)/把循环链表存储的棉疏多项式L拆成只含奇次项的A和只含偶次项的Ep=L-next;A=(PolyNode*)inalloc(sizeof(PolyNode);B=(PolyNode*)inalloc(sizeof(PolyNode);pa=A;pb=B;wliile(p!=L)if(p-data.exp!=2*(p-da

16、ta.exp/2)pa-next=p;pa=p;elsepb11亡xt=p;pb=p;p=p-next;/whilepa-next=A;pbiiext=E:/Divide_LinkedPoly2.13建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的da也域存放一个二进制位。并在此链表上实现对二进制数加1的运算。提示:可将低位放在前面。2.14设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。提示:floatPolyVhlue(Polylistp;floatx)第三章栈和队列按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答

17、：如进站的车厢序列为123,则可能得到的出站车厢序列是什么？如进站的车厢序列为123456,能否得到435612和135426的出站序列，并说明原因。(即写出以表示进栈、以“X”表示出栈的栈操作序列)。【解答】可能得到的出站车厢序列是:123、132、213、231、321。不能得到435612的出站序列。因为有SSQ)S(3)S(4)X(4)X(3)S(5)X(5)SS(6),此时按照“后进先出”的原则，出栈的顺序必须为XX(l)。能得到135426的出站序列。因为有S(l)X(l)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(l)o设队列中有A、B、C、D、E这5个元

18、素，其中队首元素为A。如果对这个队列重复执行下列4步操作：直到队列成为空队列为止,(1)(3)提示:A、C、EC、CA、C、直到队列成为空队列为止,(1)(3)提示:A、C、EC、CA、C、C、则是否可能得到输出序列：(2)A、C、E(4)A.C、E、CA、E、A、E、B、C、C、DxC、C、D、E、D、D、E、AEE、A(输出队首元素A)A(把队首元素A插入到队尾)(删除队首元素A)(再次删除队首元素E)C.C、D、DxD、E、E、A、E、E、A、C(输出队首元素C)C(把队首元素C插入到队尾)(删除队首元素C)(再次删除队首元素D)AA、C(1)输出队首元素；(2)把队首元素值插入到队尾;

19、(3)删除队首元素；(4)再次删除队首元素。给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？按照四则运算加、减、乘、除和幕运算(T)优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：AE*C/D+EfF【解答】试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如，序列1&序列2,模式的字符序列。其中序列1和序列2中都不含字符,&，,且序列2是序列1的逆序列。例如，W+b&b+a，是属该模式的字符序列，而T+3&31，则不是。提示:边读边入栈，直到&边读边出栈边比较，直到mtIsReverseQ/判断输入的字符串中&前和&方部分是否为逆串

20、，是则返回1,否则返回0LutStack(s);xvlule(e=getchai()!=&Jpush(s,e);xvlule(e=getchai()!=)if(StackEmpty(s)return0;pop(s、c);if(e!=c)retuin0;if(!StackEmpty(s)return0:return1;/IsReveise假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式(中缀)且书写正确的表达式转换为逆波兰式(后缀)。voidNiBoLan(chai-*str,char*new)/把中缀表达式str转换成逆波兰式newp=su；q=new;为方便起见

21、，设str的两端都加上了优先级最低的特殊符号LutStack(s);/s为运算符栈while(*p)if(*p是字母)*q+=*p；直接输出elsec=gettop；if(*p优先级比c高)push(s,*p);elsewhile(gettop(s)优先级不比*p低)pop(s,c);*(q+)=c;/wlulepush(s,*p);运算符在栈内遵循越往栈顶优先级越高的原则/else/else叶/whileJ.WiBoLan/参见编译原理教材假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。voidInitCiQ

22、ueue(CiQueue&Q)初始化循环链表表示的队列QQ=(CiLNode*)malloc(sizeof(CiLNode);Q-next=Q;/IiiitCiQueuevoidEnCiQueue(CiQueue&Q,mtx)把元素x插入循坏链表表示的队列Q,Q指向队尾元素,Q-next指向头结点,Q-next-next指向队头元素p=(CiLNode*)malloc(sizeof(CiLNode);p-data=x;p-next=Q-next;/直接把p加在Q的后面next=p;Q=p;修改尾指针_StatusDeCiQueue(CiQueue&Qintx)从循坏链表表示的队列Q头部删除元素

23、xif(Q=Q-next)returnINFEASIBLE:队列已空p=Q-next-next;x=p-data;Qanext-next=pnext;仕ee(p);returnOK;/DeCiQueue要求循坏队列不损失一个空间全部都能得到利用，设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。提示:初始状态：fiont=0.ea尸=0,tag=O队空条件：fiont=reaitag=O队满条件：fiont=reaitag=l其它状态：front!=reai;tag=O(或1、2)入队操作：.(入队)if(fiont=rear)t

24、ag=l；(或直接tag=l)出队操作:.(出队)tag=O；问题:如何明确区分队空、队满、非空非满三种情况？简述以下算法的功能(其中栈和队列的元素类型均为int)：voidproc_l(StackS)iiiti，n,A255;n=0;while(?EmptyStack(S)n+;Pop(&S&An);fbr(i=l;i=n;i+)Push(&S,Ai);将栈s逆序。voidproc_2(StackS,inte)StackT;intd;IiutStack(&T);while(?EmptyStack(S)Pop(&S,&d);if(d!=e)Push(&T,d);wliile(!EmptySta

25、ck(T)Pop(&T,&d);Push(&S,d);删除栈s中所有等于e的元素。voidproc_3(Queue*Q)StackS;iiitd;IiutStack(&S);wliile(!EmptyQueue(*Q)DeleteQiieue(Q.&d);Push(&S、d);while(?EmptyStack(S)Pop(&S,&d);EnterQueue(Q,d)将队列Q逆序。第四章串设s=TAMASTUDENT,t=5GOODq=?WORKERS给出下列操作的结果StrLength(s);SubStrmg(subl,s,lJ);SubStnng(sub2,s,7,1);StilndexG

26、A,4);StrReplace(s,STUDENT,q);StrCat(StrCat(sub1,t)5StrCat(StrCat(sub1,t)5StrCat(sub2,q);参考答案StrLength(s)=14;SubString(sub1是1,7)SubString(sub2,s亿1)Strlndex(s,4/A,)=6;StrReplace(s；SITOENTq);StrCat(StiIAMA,;sub2=s=YAMAWORKER：subl=7IAMAGOODWORKER。编写算法，实现串的基本操作StiReplace(SXV)oStiCat(S.T)；SubStrmg(Sub,S,p

27、osJen)omtStrmg_Replace(Striiigtype&SStiingtypeT.StiiiigtypeV);/将串S中所有子串T替换为V，并返回置换次数for(n=0,i=l;iTO)/找到了与T匹配的子串:分三种情况处理lf(T0=V0)for(l=1;1=TO;1卄)/新子串长度与原子串相同时:直接替换Si+l-l=Vl;elseif(T0=i+TO;l-)Sl+V0-T0=Sl;fbr(l=l;l=VO;l+)Si+l-l=Vl;else/新子串长度小于原子串时:先将后部左移fbr(l=i+V0;l=S0+V0-T0;l+)Sl=Sl-V0+T0;fbi(l=l;lnext;p;p=p-next)i-(LStrNode*)malloc(sizeof(LStrNode);r-ch=p-ch;q-next=i:q=r;q-next=NULL;/StimgAssignvoidStiuigCopy(LStiing&s,LStimgt)把