数据结构与算法分析c语言描述中文答案.pdf

该【数据结构与算法分析c语言描述中文答案 】是由【青山代下】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【数据结构与算法分析c语言描述中文答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..语言描述中文答案【篇一:数据结构(c语言版)课后****题答案完整版】选择题:。(1)o(1)(2)o(m*n)(3)o(n2)(4)o(log3n)(5)因为x++共执行了n-1+n-2+??+1=n(n-1)/2,所以执行时间为o(n2)(6)o(n)(6)设计一个算法,通过一趟遍历在单链表中确定值最大的结点。elemtypemax(linklistl){if(l-next==null)returnnull;pmax=l-next;//假定第一个结点中数据具有最大值p=l-next-next;while(p!=null){//如果下一个结点存在if(p-datapmax-data)pmax=p;p=p-next;}returnpmax-data;(7)设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。voidinverse(linklistl){//逆置带头结点的单链表lp=l-next;l-next=null;while(p){q=p-next;//q指向*p的后继p-next=l-next;l-next=p;//*p插入在头结点之后p=q;}}(10)已知长度为n的线性表a采用顺序存储结构,请写一时间复杂度为o(n)、空间复杂度为o(1)的算法,该算法删除线性表中所有值为item的数据元素。[题目分析]在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动(删第i个元素,第i+1至第n个元素要依次前移)。本题要求删除线性表中所有值为item的数据元素,并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(i=1,j=n),从两端向中间移动,凡遇到值item的数据元素时,直接将右端元素左移至值为item的数据元素位置。:..elemtypea[],intn)∥a是有n个元素的一维数组,本算法删除a中所有值为item的元素。{i=1;j=n;∥设置数组低、高端指针(下标)。while(ij){while(ija[i]!=item)i++;∥若值不为item,左移指针。if(ij)while(ija[j]==item)j--;∥若右端元素值为item,指针左移if(ij)a[i++]=a[j--];}[算法讨论]因元素只扫描一趟,算法时间复杂度为o(n)。删除元素未使用其它辅助空间,最后线性表中的元素个数是j。(2)回文是指正读反读均相同的字符序列,如和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈)根据提示,算法可设计为://以下为顺序栈的存储结构定义#definestacksize100//假定预分配的栈空间最多为100个元素typedefchardatatype;//假定栈元素的数据类型为字符typedefstruct{datatypedata[stacksize];inttop;}seqstack;intishuiwen(char*t){//判断t字符向量是否为回文,若是,返回1,否则返回0seqstacks;inti,len;chartemp;initstack(s);len=strlen(t);//求向量长度for(i=0;ilen/2;i++)//将一半字符入栈push(s,t[i]);while(!emptystack(s)){//每弹出一个字符与相应字符比较temp=pop(s);if(temp!=s[i])return0;//不等则返回0elsei++;}return1;//比较完毕均相等则返回1}(7)假设以数组q[m]存放循环队列中的元素,同时设置一个标志tag,以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列类定义#{public::..item);typedequeue();typegetfront();voidmakeempty(){front=rear=tag=0;}////判队列空否intisempty()const{returnfront==reartag==0;}private:intrear,front,tag;type*q;//队尾指针、队头指针和队满标志//存放队列元素的数组//循环队列的类定义intisfull()const{returnfront==reartag==1;}//判队列满否intm;}//队列最大可容纳元素个数构造函数templateclasstypequeuetype::queue(intsz):rear(0),front(0),tag(0),m(sz){//建立一个最大具有m个元素的空队列。q=newtype[m];assert(q!=0);}//创建队列空间//断言:动态存储分配成功与否插入函数templateclasstypevoidqueuetype::enqueue(typeitem){}assert(!isfull());rear=(rear+1)%m;q[rear]=item;tag=1;//判队列是否不满,满则出错处理//队尾位置进1,队尾指针指示实际队尾位置//进队列//标志改1,表示队列不空删除函数templateclasstypetypequeuetype::dequeue(){assert(!isempty());front=(front+1)%m;tag=0;returnq[front];//判断队列是否不空,空则出错处理//标志改0,表示栈不满//返回原队头元素的值//队头位置进1,队头指针指示实际队头的前一位置}:..templateclasstypetypequeuetype::getfront(){}assert(!isempty());//判断队列是否不空,空则出错处理//返回队头元素的值returnq[(front+1)%m];第4章串、(1)已知模式串写出用kmp法求得的每个字符对应的next和nextval函数值。模式串t的next和nextval值如下:(3)数组a中,每个元素a[i,j]的长度均为32个二进位,行下标从-1到9,列下标从1到11,从首地址s开始连续存放主存储器中,主存储器字长为16位。求:①存放该数组所需多少单元?②存放数组第4列所有元素至少需多少单元?③数组按行存放时,元素a[7,4]的起始地址是多少?④数组按列存放时,元素a[4,7]的起始地址是多少?每个元素32个二进制位,主存字长16位,故每个元素占2个字长,行下标可平移至1到11。(1)242(2)22(3)s+182(4)s+142(4)请将香蕉banana用工具h()—head(),t()—tail()从l中取出。l=(apple,(orange,(strawberry,(banana)),peach),pear)h(h(t(h(t(h(t(l)))))))(5)写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为a-z这26个字母和0-9这10个数字)。voidcount()//统计输入字符串中数字字符和字母字符的个数。{inti,num[36];charch;for(i=0;i36;i++)num[i]=0;//初始化while((ch=getchar())!=‘#’)//‘#’表示输入字符串结束。if(‘0’=ch=‘9’){i=ch-48;num[i]++;}//数字字符elseif(‘a’=ch=‘z’){i=ch-65+10;num[i]++;}//字母字符:..i=0;i10;i++)//输出数字字符的个数printf(数字%d的个数=%n”,i,num[i]);for(i=10;i36;i++)//求出字母字符的个数printf(“字母字符%c的个数=%n”,i+55,num[i]);}//算法结束。【篇二:数据结构****题集答案(c语言严版)】所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合,是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。::plex{数据对象:d={r,i|r,i为实数}数据关系:r={r,i}基本操作:plex(c,re,im)操作结果:构造一个复数c,其实部和虚部分别为re和imdestroycmoplex(c)操作结果:销毁复数cget(c,k,e)操作结果:用e返回复数c的第k元的值操作结果:改变复数c的第k元的值为e操作结果:如果复数c的两个元素按升序排列,则返回1,否则返回0操作结果:如果复数c的两个元素按降序排列,则返回1,否则返回0操作结果:用e返回复数c的两个元素中值较大的一个操作结果:用e返回复数c的两个元素中值较小的一个:..min(c,e)}plexd={s,m|s,m为自然数,且m不为0}数据关系:r={s,m}基本操作:initrationalnumber(r,s,m)操作结果:构造一个有理数r,其分子和分母分别为s和mdestroyrationalnumber(r)操作结果:销毁有理数rget(r,k,e)操作结果:用e返回有理数r的第k元的值adtrationalnumber{put(r,k,e)操作结果:改变有理数r的第k元的值为e操作结果:若有理数r的两个元素按升序排列,则返回1,否则返回0操作结果:若有理数r的两个元素按降序排列,则返回1,否则返回0操作结果:用e返回有理数r的两个元素中值较大的一个操作结果:用e返回有理数r的两个元素中值较小的一个isascending(r)isdescending(r)max(r,e)min(r,e)}:(1)exit常用于异常错误处理,它可以强行中断程序的执行,返回操作系统。(2)以函数的返回值判断正确与否常用于子程序的测试,便于实现程序的局部控制。(3)用整型函数进行错误处理的优点是可以给出错误类型,便于迅速确定错误。:(1)用scanf和printf直接进行输入输出的好处是形象、直观,但缺点是需要对其进行格式控制,较为烦琐,如果出现错误,则会引起整个系统的崩溃。(2)通过函数的参数传递进行输入输出,便于实现信息的隐蔽,减少出错的可能。(3)通过全局变量的隐式传递进行输入输出最为方便,只需修改变量的值即可,但过多的全局变量使程序的维护较为困难。:(1)n-1(2)n-1(3)n-1(4)n+(n-1)+(n-2)+...+1=n(n?1)2(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)==1n?i?1ni(i?1)21n1n21n2(i?i)??i??i?i(i?1)?2?2i?12i?12i?1i?1=111n(n?1)(2n?1)?n(n?1)?n(n?1)(2n?3)12412(6)n(7)n?向下取整n)count=log2n?2n=40n=16(8):o(:2nn?1012?101210:..n,在这个规模下,第二种算法所花费的代价要大得多。故在这个规模下,第一种算法更适宜。:(1)对(2)错(3)错(4)对(5):n的增长趋势快。但在n较小的时候,50nlog22n的值较大。当n438时,n2?:(1)g(n)快(2)g(n)快(3)f(n)快(4)f(n),自大至小依次输出顺序读入的三个整数x,y和z的值解:intmax3(intx,inty,intz){}:k0为阶数,n为数列的第n项i(intk,intn){}:typedefenum{a,b,c,d,e}schoolname;typedefenum{female,male}sextype;typedefstruct{charevent[3];//项目sextypesex;schoolnameschool;intscore;if(k1)exit(overflow);int*p,x;p=newint[k+1];if(!p)exit(overflow);inti,j;for(i=0;ik+1;i++){}for(i=k+1;in+1;i++){}returnp[k];x=p[0];for(j=0;jk;j++)p[j]=p[j+1];p[k]=2*p[k-1]-x;if(ik-1)p[i]=0;elsep[i]=1;if(xy)if(xz)returnx;elsereturnz;if(yz)returny;elsereturnz;else}component;typedefstruct{intmalesum;//男团总分intfemalesum;//女团总分inttotalsum;//团体总分}sum;sumsumscore(ponenta[],intn){}:##:..#definearrsize100intfun(inti);intmain(){}##,k;inta[arrsize];coutenterk:;cink;if(karrsize-1)exit(0);for(i=0;i=k;i++){}for(i=0;i=k;i++){}return0;if(a[i]maxint)exit(0);elsecouta[i];if(i==0)a[i]=1;else{}if(2*i*a[i-1]maxint)exit(0);elsea[i]=2*i*a[i-1];sumtemp;=0;=0;=0;inti;for(i=0;in;i++){}=+;returntemp;if(a[i].school==sn){}if(a[i].sex==male)+=a[i].score;if(a[i].sex==female)+=a[i].score;#definen10doublepolynomail(inta[],inti,doublex,intn);intmain(){doublex;}doublepolynomail(inta[],inti,doublex,intn){}本算法的时间复杂度为o(n)。:头指针,头结点,首元结点(第一个元素结点)。解:头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点,该结点不存储数据元素,其指针域指向首元结点,其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。。:..(1)在顺序表中插入或删除一个元素,需要平均移动表中一半元素,具体移动的元素个数与元素在表中的位if(i0)returna[n-i]+polynomail(a,i-1,x,n)*x;elsereturna[n];intn,i;inta[n];cout输入变量的值x:;cinx;cout输入多项式的阶次n:;cinn;if(nn-1)exit(0);cout输入多项式的系数a[0]--a[n]:;for(i=0;i=n;i++)cina[i];coutthepolynomailvalueispolynomail(a,n,x,n)endl;return0;置有关。(2)顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。(3)在单链表中,除了首元结点外,任一结点的存储位置由其前驱结点的链域的值指示。(4)在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。?解:当线性表的数据元素在物理位置上是连续存储的时候,用顺序表比用链表好,其特点是可以进行随机存取。:【篇三:数据结构c++版课后****题解析】.......................................................................................................................................................................................................................................................................................................................................................2第2章线性表..................................................................................................................................................................................................................................................9第3章栈和队列...................................................................................................................17:..学..........................................................................................................................................................................................................................................18第4章字符串和多维数组.............................................................................................................................................................................................................................................................................................................................................25第5章树和二叉树...........................................................................................................................................................................................................................................................................................................................................................31第6章图.............................................................................................................................................................................................................................................................................................................................................................................41第7章查找技术.....................................................................................................................53:..学............................................................................................................................................................................................................................................54第8章排序技术.................................................................................................................................................................................................................................................................................................................................................................64第9章索引技术.................................................................................................................................................................................................................................................................................................................................................................-1所示,其中第二层的椭圆代表本章的学****主线。图1-,一条主线是数据结构,包括数据结构的相关概念及含义,另一条主线是算法,包括算法的相关概念、描述方法以及时间复杂度的分析方法。在学****数据结构时要抓住两个方面:逻辑结构和存储结构,并注意把握二者之间的关系。在学****算法时,要以算法的概念和特性为基:..性能的分析,要将注意力集中在增长率上,即基本语句执行次数的数量级,在设计算法时,养成分析算法时间性能的****惯,进而有效地改进算法的效率。(1)()是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素(2)()是数据的最小单位,()是讨论数据结构时涉及的最小数据单位。【解答】数据项,数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。(3)从逻辑关系上讲,数据结构主要分为()、()、()和()。【解答】集合,线性结构,树结构、图结构(4)数据的存储结构主要有()和()两种基本方法,不论哪种存储结构,都要存储两方面的内容:()和()。【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系(5)算法具有五个特性,分别是()、()、()、()、()。【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性(6)算法的描述方法通常有()、()、()和()四种,其中,()被称为算法语言。【解答】自然语言,程序设计语言,流程图,伪代码,伪代码(7)在一般情况下,一个算法的时间复杂度是()的函数。【解答】问题规模(8)设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为(),若为2n*log25n+8n,则表示成数量级的形式为()。【分析】用大o记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。:..1)顺序存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中的数据元素之间的逻辑关系是由()表示的。a线性结构b非线性结构c存储位置d指针【解答】c,d【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示。(2)假设有如下遗产继承规则:丈夫和妻子可以相互继承遗产;子女可以继承父亲或母亲的遗产;子女间不能相互继承遗产。则表示该遗产继承关系的