数据结构(C语言版)第三版--清华大学出版社-习题参考答案.docx
附录习题参考答案习题1参考答案1.1.选择题(1).A.(2).A.(3).A.(4).B.,C.(5).A.(6).A.(7).C.(8).A.(9).B.(10.)A.1.2.填空题(1) .数据关系(2) .逻辑结构物理结构(3) .线性数据结构树型结构图结构(4) .顺序存储链式存储索引存储散列表(Hash)存储(5) .变量的取值范围操作的类别(6) .数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7) .关系网状结构树结构(8) .空间复杂度和时间复杂度(9) .空间时间(10) .O(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的根本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由假设千个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述，是指令的有限序列。1.4 语句的时间复杂度为：7 1 )/ - 7 2 2 2 3 n n n n z(x z( z( z(x Zfx Ooooo J 7 J )/ / I 2 3 4 5 f zrf1.5 参考程序：main()(intX,Y,Z;scanf(w%d,%d,%d”，&X,&Y,Z)；if(X>=Y)if(X>=Z)if(Y>=Z)printf(rt%d,%d,%dw,X,Y,Z)Jelseprintf(tt%df%d,%dw,X,Z,Y);)elseprintf(u%d,%d,%dw,Z,X,Y)Jelseif(Z>=X)if(Y>=Z)printf(w%d,%d,%dw,Y,Z,X)Jelseprintf(ii%dt%d,%d”，Z,Y,X);elseprintf(%(1,%d,%dw,Y,X,Z);)1.6 参考程序：main()inti,n;floatx,a,p;printf(unn=w);scanf("%f",&n);printf(unx=w)jscanf(%fw,&x);for(i=0;i<=n;i+)scanf(ii%fn,&ai);P=a0;for(i=l;i<=n;i+)p=p+ai*x;x=x*x;Printf("%f”，p),习题2参考答案2. 1选择题(1).C.(2).B.(3).B.(4).B.5.D.6.B.7.B.8.A.9.A.10.D.3. 2.填空题(1) .有限序列(2) .顺序存储和链式存储(3) .O(n)0(n)(4) .n-i+1n-i(5) .链式(6) .数据指针(7) .前驱后继(8) .O(I)0(n)(9) .s->next=p->next;p->next=s;(10) .s->next2. 3.解题思路:将顺序表A中的元素输入数组a,假设数组a中元素个数为n,将下标为0,1,2,，(nT)/2的元素依次与下标为n,nT,，InT)/2的元素交换，输出数组a的元素。参考程序如下：main()inti,n;floatt,a;Printf("nn=");SCanf("%f",&n);for(i=0;i<=n-l;i+)scanf(w%fn,&ai);for(i=0;i<=(n-l)/2;i+)t=ai;ai=a11-l-i;an-l-i=t;for(i=0;i<=n-l;i+)printf("%f",ai);2.4 算法与程序：main()inti,n;floatt,a;printf(unn=w);scanf(%fw,&n);for(i=0;i<n;i+)scanf(ii%fn,&ai);for(i=l;i<n;i+)if(ai>a0)t=ai;ai=a0;a0=t;)printf(%fw,a0);for(i=2;i<n;i+)if(ai>al)t=ai;ai=al;al=t;printf(u%fn,a0);2.5 算法与程序：main()inti,j,k,n;floatx,t,a;Printf("nx=");SCanf("%f",&x);printf(wnn=,);scanf(ii%fff,&n);for(i=0;i<n;i+)scanf("%f,&ai);/输入线性表中的元素for(i=0;i<n;i+)/对线性表中的元素递增排序k=i;for(j=i+l;j<n;j+)if(aj<ak)k=j;if(k<>j)t=ai;ai=ak;ak=t;for(i=0;i<n;i+)/在线性表中找到适宜的位置if(ai>x)break;for(k=n-l;k>=i;i-)/移动线性表中元素，然后插入元素Xak+l=ak;ai=x;for(i=0;i<=n;i+)/依次输出线性表中的元素Printf("%f",ai);2.6 算法思路：依次扫描A和B的元素，比拟A、B当前的元素的值，将较小值的元素赋给C,如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下局部赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。有序表的合并算法：voidmerge(SeqListA,SeqListB,SeqList*C)inti,j,k；i=0:j=0；k=0；while(i<=A.last&&j<=B.last)if(A.datai<=B.dataj)C->datak+=A.datai+；elseC->datak+=B.dataj+；while(i<=A.last)C->datak+三A.datai+；while(j<=B.last)C->datak+=B.dataj+；C->last=k-l;2.7 算法思路：依次将A中的元素和B的元素比拟，将值相等的元素赋给3如此直到线性表扫描完毕,线性表C就是所求递增有序线性表。算法：voidmerge(SeqListA,SeqListB,SeqList*C)inti,j,k；i=0:j=0；k=0；while(i<=A.last)while(j<=B.last)if(A.datai=B.dataj)C->datak+=A.datai+；C->last=k-l;习题3参考答案3. 1.选择题(I) .D(2).C(3).D(4).C(5).B(6).C(7).C(8).C(9).B(10).AB(II) .D(12).B(13).D(14).C(15).C(16).D(17).D(18).C(19).C(20).C3. 2.填空题(1) FILO,FIFO(2) -1,34X*+2Y*3-(3) stack,top,stack,sstack,top=x(4) p>llink->rlink=p->rlink,p->rlink->l1ink=p->r1ink(5) (R-F+M)%M(6) topl+l=top2(7) F=R(8) front=rear(9) front=(rear+l)%n(10) N-I(11) ：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表栈只能在线性表的一端插入(称为入栈,push)或者读取栈顶元素或者称为“弹出、出栈"(pop)。(12) ：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。不同点：栈只在一端(栈顶)进行插入，删除操作；队列在一端(top)删除，一端(rear)插入。(13) 答：可能序列有14种:ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA0(14) ：不能得到4,3,5,6,1,2,最先出栈的是4,那么按321的方式出，不可能得到1在2前的序列,可以得到L3,5,4,2,6,按如下方式进行PUSh(I),pop(),push(2),push(3),pop(),push(4),push(5),pop(),pop(),popO,push(6),pop()o(15) 答：stack(16) 递归：intvonvert(intno,inta)/将十进制数转换为2进制存放在a,并返回位数intr;SeStacks,*p;P=&s;Init_stack(p);while(no)push(p,no%2);no=10;r=0;while(!empty_stack(p)pop(p,a+r);r+;returnr;递归算法：voidconvert(intno)if(no2>0)Convert(no2);Printf(u%dn,no%2);)elsePrintf("%d”，no);(17) 考程序：voidview(SeStacks)SeStack*p;假设栈元素为字符型charc;P=&s;while(!empty_stack(p)c=pop(p);Printf("%c",c);)Printf("n");3. 10答：char3.11参考程序：voidout(linkqueueq)inte;while(q.rear!=q.front)dequeue(q,e);print(e);打印习题4参考答案4. 1选择题：(1) .A(2).D(3).C(4).C(5).B(6).B(7).D(8).A(9).B(10).D4.2填空题：(I)串长相等且对应位置字符相等(2) 不含任何元素的串，O(3) 所含字符均是空格，所含空格数(4) 10(5) “helloboy”(6) 13(7) 1066(8) 模式匹配(9)串中所含不同字符的个数(10) 36(11) StrLength(s)=14,StrLength(t)=4,SubStr(s,8,7)="STUDENTw,SubStr(t,2,1)二"0”，StrIndeX(S,"A”)=3,StrIndex(s,t)=0,StrRep(s,“STUDENT',q)="IAMAWORKER,4.4StrReP(s,“Y”，"+");StrReP(s,"+*"，"*Y");(12) 串：不含任何字符；空格串：所含字符都是空格串变量和串常量：串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的
