c语言数据结构题集解答集.doc

佳构文档你我共享天佑自助者，你要你就能。第1章绪论1.1简述以下术语：数据数据元素、数据工具、数据结构、存储结构、数据范例跟笼统数据范例解：数据是对客不雅事物的标记表现在盘算机迷信中是指一切能输入到盘算机中并被盘算机次序处置的标记的总称数据元素是数据的根本单位在盘算机次序中平日作为一个全体进展思索跟处置数据工具是性子一样的数据元素的聚集是数据的一个子集数据结构是互相之间存在一种或多种特定关联的数据元素的聚集存储结构是数据结构在盘算机中的表现数据范例是一个值的聚集跟界说在那个值集上的一组操纵的总称笼统数据范例是指一个数学模子以及界说在该模子上的一组操纵是对普通数据范例的扩年夜1.2试描绘数据结构跟笼统数据范例的不雅点与次序计划言语中数据范例不雅点的区不解：笼统数据范例包含普通数据范例的不雅点但含意比普通数据范例更广、更笼统普通数据范例由详细言语零碎外部界说直截了当供给应编程者界说用户数据因而称它们为预约义数据范例笼统数据范例平日由编程者界说包含界说它所运用的数据跟在这些数据上所进展的操纵在界说笼统数据范例中的数据部分跟操纵部分时请求只界说到数据的逻辑结构跟操纵阐明不思索数据的存储结构跟操纵的详细实现如斯笼统档次更高更能为其余用户供给精良的运用接口1.3设有数据结构(DR)此中AAAAAA佳构文档你我共享试按图论中图的画法常规画出其逻辑结构图解：1.4试模仿三元组的笼统数据范例分不写出笼统数据范例单数跟有理数的界说有理数是其分子、分母均为天然数且分母不为零的分数解：ADTComplex数据工具：D=ri|ri为实数数据关联：R=根本操纵：InitComplex(&Creim)操纵后果：结构一个单数C事实上部跟虚部分不为re跟imDestroyCmoplex(&C)操纵后果：烧毁单数CGet(Ck&e)操纵后果：用e前往单数C的第k元的值Put(&Cke)操纵后果：改动单数C的第k元的值为eIsAscending(C)操纵后果：假如单数C的两个元素按升序陈列那么前往1否那么前往0IsDescending(C)操纵后果：假如单数C的两个元素按落序陈列那么前往1否那么前往0Max(C&e)操纵后果：用e前往单数C的两个元素中值较年夜的一个Min(CAAAAAA佳构文档你我共享&e)操纵后果：用e前往单数C的两个元素中值较小的一个ADTComplexADTRationalNumber数据工具：D=sm|sm为天然数且m不为0数据关联：R=根本操纵：InitRationalNumber(&Rsm)操纵后果：结构一个有理数R其分子跟分母分不为s跟mDestroyRationalNumber(&R)操纵后果：烧毁有理数RGet(Rk&e)操纵后果：用e前往有理数R的第k元的值Put(&Rke)操纵后果：改动有理数R的第k元的值为eIsAscending(R)操纵后果：假设有理数R的两个元素按升序陈列那么前往1否那么前往0IsDescending(R)操纵后果：假设有理数R的两个元素按落序陈列那么前往1否那么前往0Max(R&e)操纵后果：用e前往有理数R的两个元素中值较年夜的一个Min(R&e)操纵后果：用e前往有理数R的两个元素中值较小的一个ADTRationalNumber1.5试画出与以下次序段等价的框图AAAAAA佳构文档你我共享(1)product=1;i=1;while(i=n)product*=i;i+;(2)i=0;doi+;while(i!=n)&(ai!=x);(3)switchcasexy:z=y-x;break;casex=y:z=abs(x*y);break;default:z=(x-y)/abs(x)*abs(y);1.6在次序计划中常用以下三种差其余犯错处置方法：(1)(2)(3)用exit语句停止履行并讲演过错；以函数的前往值区不准确前往或过错前往；设置一个整型变量的函数参数以区不准确前往或某种过错前往试探讨这三种办法各自的优缺陷解：(1)exit常用于异样过错处置它能够强行中缀次序的履行前往操纵零碎(2)以函数的前往值推断准确与否常用于子次序的测试便于实现次序的部分操纵(3)用整型函数进展过错处置的长处是能够给犯过错范例便于敏捷断定过错1.7在次序计划中可采纳以下三种办法实现输入跟输入：(1)(2)(3)经过scanf跟printf语句；经过函数的参数显式通报；经过全局变量隐式通报试探讨这三种办法的优缺陷解：(1)用scanf跟printf直截了当进展输入输入的益处是笼统、直不雅但缺陷是需求对其进展格局操纵AAAAAA佳构文档你我共享较为繁缛假如呈现过错那么会惹起全部零碎的解体(2)经过函数的参数通报进展输入输入便于实现信息的荫蔽增加犯错的能够(3)经过全局变量的隐式通报进展输入输入最为便利只要修正变量的值即可但过多的全局变量使次序的保护较为艰苦1.8设n为正整数试断定以下各次序段中前置以暗号(1)i=1;k=0;while(i=n-1)k+=10*i;i+;的语句的频度：(2)i=1;k=0;dok+=10*i;i+;while(i=n-1);(3)i=1;k=0;while(i=n-1)i+;k+=10*i;(4)k=0;for(i=1;i=n;i+)for(j=i;j=n;j+)k+;(5)for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x+=delta;(6)i=1;j=0;while(i+jj)j+;elsei+;AAAAAA佳构文档你我共享(7)x=n;y=0;/nwhile(x=(y+1)*(y+1)y+;是不小于1的常数(8)x=91;y=100;while(y0)if(x100)x-=10;y-;elsex+;解：(1)n-1(2)n-1(3)n-1(4)n+(n-1)+(n-2)+.+1=(5)1+(1+2)+(1+2+3)+.+(1+2+3+.+n)=(6)n(7)向下取整(8)11001.9假设n为2的乘幂同时n2试求以下算法的时间庞杂度及变量count的值以n的函数方法表现intTime(intn)count=0;x=2;while(x438时1.14推断以下各对函数跟事先哪个函数增加更快？(1)(2)(3)(4)解：(1)g(n)快(2)g(n)快(3)f(n)快(4)f(n)快1.15试用数学归结法证实：(1)(2)(3)AAAAAA佳构文档你我共享(4)1.16试写一算法自卑至小顺次输入次序读入的三个整数XY跟Z的值解：intmax3(intxintyintz)if(xy)if(xz)returnx;elsereturnz;elseif(yz)returny;elsereturnz;1.17曾经明白k阶斐波那契序列的界说为.；试编写求k阶斐波那契序列的第m项值的函数算法k跟m均以值挪用的方法在函数参数表中呈现解：k0为阶数n为数列的第n项intFibonacci(intkintn)if(k1)exit(OVERFLOW);int*px;p=newintk+1;if(!p)exit(OVERFLOW);intij;for(i=0;ik+1;i+)if(ik-1)pi=0;elsepi=1;AAAAAA佳构文档你我共享for(i=k+1;in+1;i+)x=p0;for(j=0;jk;j+)pj=pj+1;pk=2*pk-1-x;returnpk;1.18假设有ABCDE五个初等院校进展田径对破赛各院校的单项成果均已存入盘算机并形成一张表表中每一行的方法为工程称号性不校名成果得分编写算法处置上述表格以统计各院校的男、女总分跟集团总分并输入解：typedefenumABCDESchoolName;typedefenumFemaleMaleSexType;typedefstructcharevent3;/SexTypesex;SchoolNameschool;intscore;工程Component;typedefstructintMaleSum;/男团总分intFemaleSum;intTotalSum;/女团总分/集团总分AAAAAA佳构文档你我共享Sum;SumSumScore(SchoolNamesnComponentaintn)Sumtemp;temp.MaleSum=0;temp.FemaleSum=0;temp.TotalSum=0;inti;for(i=0;iarrsize或对某个使时maxint应按犯错处置留意选择你认为较好的犯错处置办法解：#include#include#defineMAXINT65535#defineArrSize100intfun(inti);intmain()intik;intaArrSize;coutk;if(kArrSize-1)exit(0);for(i=0;iMAXINT)exit(0);elseai=2*i*ai-1;for(i=0;iMAXINT)exit(0);elsecoutai;return0;1.20试编写算法求一元多项式的值的值并断定算法中每一语句的履行次数跟全部算法的时间庞杂度留意选择你认为较好的输入跟输入办法此题的输入为跟输入为解：#include#include#defineN10doublepolynomail(intaintidoublexintn);intmain()doublex;intni;intaN;coutx;coutn;if(nN-1)exit(0);cout输入多项式的系数a0-an:;for(i=0;iai;AAAAAA佳构文档你我共享coutThepolynomailvalueispolynomail(anxn)0)returnan-i+polynomail(ai-1xn)*x;elsereturnan;本算法的时间庞杂度为o(n)第2章线性表2.1描绘以下三个不雅点的区不：头指针头结点首元结点第一个元素结点解：头指针是指向链表中第一个结点的指针首元结点是指链表中存储第一个数据元素的结点头结点是在首元结点之前附设的一个结点该结点不存储数据元素其指针域指向首元结点其感化要紧是为了便利对链表的操纵它能够对空表、非空表以及首元结点的操纵进展一致处置2.2填空题解：(1)在次序表中拔出或删除一个元素需求均匀挪动表中一半元素详细挪动的元素个数与元素在表中的地位有关(2)次序表中逻辑上相邻的元素的物理地位肯定紧邻单链表中逻辑上相邻的元素的物理地位不必定紧邻(3)在单链表中除了首元结点外AAAAAA佳构文档你我共享任一结点的存储地位由其先驱结点的链域的值唆使(4)在单链表中设置头结点的感化是拔出跟删除首元结点时不必进展专门处置2.3在什么状况下用次序表比链表好？解：当线性表的数据元素在物理地位上是延续存储的时分用次序表比用链表好其特色是能够进展随机存取2.4对以下单链表分不履行以下各次序段并画出后果表现图解：2.5画出履行以下各行语句后各指针及链表的表现图L=(LinkList)malloc(sizeof(LNode);for(i=1;inext=(LinkList)malloc(sizeof(LNode);P=P-next;P-data=i*2-1;P-next=NULL;for(i=4;i=1;i-)Ins_LinkList(Li+1i*2);for(i=1;inext=S;(2)P-next=P-next-next;(3)P-next=S-next;(4)S-next=P-next;(5)S-next=L;(6)S-next=NULL;(7)Q=P;(8)while(P-next!=Q)P=P-next;(9)while(P-next!=NULL)P=P-next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;解：a.(4)(1)b.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)2.7曾经明白L是带表头结点的非空单链表且P结点既不是首元结点也不是尾元结点试从以下供给的谜底当选择适合的语句序列a.b.c.d.删除P结点的直截了当后继结点的语句序列是删除P结点的直截了以后驱结点的语句序列是_删除P结点的语句序列是_删除首元结点的语句序列是删除尾元结点的语句序列是_e.(1)P=P-next;(2)P-next=P;AAAAAA佳构文档你我共享(3)P-next=P-next-next;(4)P=P-next-next;(5)while(P!=NULL)P=P-next;(6)while(Q-next!=NULL)P=Q;Q=Q-next;(7)while(P-next!=Q)P=P-next;(8)while(P-next-next!=Q)P=P-next;(9)while(P-next-next!=NULL)P=P-next;(10)Q=P;(11)Q=P-next;(12)P=L;(13)L=L-next;(14)free(Q);解：a.(11)(3)(14)b.(10)(12)(8)(3)(14)c.(10)(12)(7)(3)(14)d.(12)(11)(3)(14)e.(9)(11)(3)(14)2.8曾经明白P结点是某双向链表的两头结点试从以下供给的谜底当选择适合的语句序列a.b.c.d.e.在P结点后拔出S结点的语句序列是_在P结点前拔出S结点的语句序列是_删除P结点的直截了当后继结点的语句序列是删除P结点的直截了以后驱结点的语句序列是_删除P结点的语句序列是_(1)P-next=P-next-next;(2)P-priou=P-priou-priou;(3)P-next=S;(4)P-priou=S;(5)S-next=P;(6)S-priou=P;(7)S-next=P-next;(8)S-priou=P-priou;(9)P-priou-next=P-next;(10)P-priou-next=P;(11)P-next-priou=P;(12)P-next-priou=S;(13)P-priou-next=S;AAAAAA佳构文档你我共享(14)P-next-priou=P-priou;(15)Q=P-next;(16)Q=P-priou;(17)free(P);(18)free(Q);解：a.(7)(3)(6)(12)b.(8)(4)(5)(13)c.(15)(1)(11)(18)d.(16)(2)(10)(18)e.(14)(9)(17)2.9简述以下算法的功用(1)StatusA(LinkedListL)/L是无表头结点的单链表if(L&L-next)Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;returnOK;(2)voidBB(LNode*sLNode*q)p=s;while(p-next!=q)p=p-next;p-next=s;voidAA(LNode*paLNode*pb)/pa跟pb分不指向单轮回链表中的两个结点BB(papb);pa);BB(pb解：(1)假如L的长度不小于2将L的首元结点酿成尾元结点(2)将单轮回链表拆成两个单轮回链表2.10指出以下算法中的过错跟低效之处并将它改写为一个既准确又高效的算法StatusDeleteK(SqList&aAAAAAA佳构文档你我共享intiintk)/本进程从次序存储结构的线性表a中删除第i个元素起的k个元素if(i1|ka.length)returnINFEASIBLE;/else参数分歧法for(count=1;count=i+1;j-)a.elemj-i=a.elemj;a.length-;returnOK;解：StatusDeleteK(SqList&aintiintk)/从次序存储结构的线性表/留意i的编号从0开场intj;a中删除第i个元素起的k个元素if(ia.length-1|ka.length-i)returnINFEASIBLE;for(j=0;j0xB.lengthA.length:B.length;for(i=0;iB.elemi)j=1;if(A.elemik)j=1;if(B.lengthk)j=-1;if(A.length=B.length)j=0;returnj;2.13试写一算法在带头结点的单链表结构上实现线性表操纵Locate(Lx);解：intLocateElem_L(LinkList&LElemTypex)inti=0;LinkListp=L;while(p&p-data!=x)p=p-next;i+;AAAAAA佳构文档你我共享if(!p)return0;elsereturni;2.14试写一算法在带头结点的单链表结构上实现线性表操纵Length(L)解：/前往单链表的长度intListLength_L(LinkList&L)inti=0;LinkListp=L;if(p)p=p-next;while(p)p=p-next;i+;returni;2.15曾经明白指针ha跟hb分不指向两个单链表的头结点同时曾经明白两个链表的长度分不为m跟n试写一算法将这两个链表衔接在一同假设指针hc指向衔接后的链表的头结点并请求算法以尽能够短的时间实现衔接运算请剖析你的算法的时间庞杂度解：voidMergeList_L(LinkList&haLinkList&hbLinkList&hc)LinkListpapb;pa=ha;pb=hb;while(pa-next&pb-next)pa=pa-next;pb=pb-next;if(!pa-next)hc=hb;while(pb-next)pb=pb-next;pb-next=ha-next;AAAAAA佳构文档你我共享elsehc=ha;while(pa-next)pa=pa-next;pa-next=hb-next;2.16曾经明白指针la跟lb分不指向两个无头结点单链表中的首元结点以下算法是从表la中删除自第i个元素起共len个元素后将它们拔出到表lb中第i个元素之前试咨询此算法是否准确？假设有错请矫正之StatusDeleteAndInsertSub(LinkedListlaLinkedListlbintiintjintlen)if(i0|j0|len0)returnINFEASIBLE;p=la;k=1;while(knext;q=p;k+;while(knext;k+;s=lb;k=1;while(knext;s-next=p;q-next=s-next;returnOK;k+;解：StatusDeleteAndInsertSub(LinkList&laLinkList&lbintiintjintlen)LinkListpqsprev=NULL;intk=1;if(i0|j0|len0)returnINFEASIBLE;/在la表中查寻第i个结点p=la;AAAAAA佳构文档你我共享while(p&knext;k+;if(!p)returnINFEASIBLE;/在la表中查寻第i+len-1个结点q=p;k=1;while(q&knext;k+;if(!q)returnINFEASIBLE;/实现删除留意i=1的状况需求专门处置if(!prev)la=q-next;elseprev-next=q-next;/将从la中删除的结点拔出到lb中if(j=1)q-next=lb;lb=p;elses=lb;k=1;while(s&knext;k+;if(!s)returnINFEASIBLE;q-next=s-next;s-next=p;/实现拔出returnOK;2.17试写一算法在无头结点的静态单链表上实现线性表操纵Insert(Lib)并跟在带头结点的静态单链表上实现一样操纵的算法进展比拟2.18试写一算法实现线性表操纵Delete(LAAAAAA佳构文档你我共享i)并跟在带头结点的静态单链表上实现一样操纵的算法进展比拟2.19曾经明白线性表中的元素以值递增有序陈列并以单链表作存储结构试写一高效的算法删除表中一切值年夜于mink且小于maxk的元素假设表中存在如斯的元素同时开释被删结点空间并剖析你的算法的时间庞杂度留意mink跟maxk是给定的两个参变量它们的值能够跟表中的元素一样也能够差别解：StatusListDelete_L(LinkList&LElemTypeminkElemTypemaxk)LinkListpqprev=NULL;if(minkmaxk)returnERROR;p=L;prev=p;p=p-next;while(p&p-datadatanext;elseprev-next=p-next;q=p;p=p-next;free(q);returnOK;2.20同2.19题前提试写一高效的算法删除表中一切值一样的过剩元素使得操纵后的线性表中一切元素的值均纷歧样同时开释被删结点空间AAAAAA佳构文档你我共享并剖析你的算法的时间庞杂度解：voidListDelete_LSameNode(LinkList&L)LinkListpqprev;p=L;prev=p;p=p-next;while(p)prev=p;p=p-next;if(p&p-data=prev-data)prev-next=p-next;q=p;p=p-next;free(q);2.21试写一算法实现次序表的当场逆置即应用原表的存储空间将线性表逆置为解：/次序表的逆置StatusListOppose_Sq(SqList&L)inti;ElemTypex;for(i=0;inext;L-next=NULL;while(p)q=p;p=p-next;q-next=L-next;L-next=q;returnOK;2.23设线性表试写一个按以下规那么兼并B为线性表C的算法即便得A事先；事先线性表AB跟C均以单链表作存储结构且C表应用A表跟B表中的结点空间形成留意：单链表的长度值m跟n均未显式存储解：/将兼并后的后果放在C表中并删除B表StatusListMerge_L(LinkList&ALinkList&BLinkList&C)LinkListpapbqaqb;pa=A-next;pb=B-next;C=A;AAAAAA佳构文档你我共享while(pa&pb)qa=pa;qb=pb;pa=pa-next;pb=pb-next;qb-next=qa-next;qa-next=qb;if(!pa)qb-next=pb;pb=B;free(pb);returnOK;2.24假设有两个按元素值递增有序陈列的线性表A跟B均以单链表作存储结构请编写算法将A表跟B表合并成一个按元素值递加有序即非递增有序同意表中含有值一样的元素陈列的线性表C并请求应用原表即A表跟B表的结点空间结构C表解：/将兼并逆置后的后果放在并删除B表C表中StatusListMergeOppose_L(LinkList&ALinkList&BLinkList&C)LinkListpapbqaqb;pa=A;pb=B;qa=pa;qb=pb;/保管pa的先驱指针/保管pb的先驱指针pa=pa-next;pb=pb-next;A-next=NULL;C=A;while(pa&pb)if(pa-datadata)qa=pa;pa=pa-next;qa-next=A-next;A-next=qa;/将以后最小结点拔出A表表头AAAAAA佳构文档你我共享elseqb=pb;pb=pb-next;qb-next=A-next