数据结构综合复习题.pdf

该【数据结构综合复习题 】是由【小屁孩】上传分享，beplayapp体育下载一共【5】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【数据结构综合复习题 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。:..?有关数据结构的讨论涉及哪三个方面?【解答】数据结构是指数据以及相互之间的关系。记为:数据结构={D,R}。其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。有关数据结构的讨论一般涉及以下三方面的内容:①数据成员以及它们相互之间的逻辑关系,也称为数据的逻辑结构,简称为数据结构;②数据成员及其关系在计算机存储器内的存储表示,也称为数据的物理结构,简称为存储结构;③施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储不是一码事,是与计算机存储无关的。因此,数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型,是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像),它是依赖于计算机的,是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算,每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。,分析下列各程序段中加下划线的语句的程序步数。(1)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){c[i][j]=;for(intk=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}(2)x=0;y=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+y;(3)i=1;j=1;while(i<=n&&j<=n){i=i+1;j=j+i;}(4)i=1;do{for(j=1;j<=n;j++)i=i+j;}while(i<100+n);【解答】nnn(1)???1?n3i?1j?1k?1(2)nijnin?i(i?1)?1n1n???1???j??????i2??i??2?22i?1j?1k?1i?1j?1i?1i?1i?11n(n?1)(2n?1)1n(n?1)n(n?1)(n?2)???26226:..(3)i=1时,i=2,j=j+i=1+2=2+1,i=2时,i=3,j=j+i=(2+1)+3=3+1+2,i=3时,i=4,j=j+i=(3+1+2)+4=4+1+2+3,i=4时,i=5,j=j+i=(4+1+2+3)+5=5+1+2+3+4,……i=k时,i=k+1,j=j+i=(k+1)+(1+2+3+4+…+k),kj??k?1???i?n?nn(n?1)次数x?1时,i?1??j?1?i?1??2kk?1kj?21?3k?3??k?1????n?n(n?1)?n?n(n?1)?n(n?1)?n(n?1)?22?x?2时,i??1???j??1????1?2???2??2?2?2?j?1解出满足上述不等式的k值,即为语句i=i+1的程序步数。(4)??n(n?1)??n?n(n?1)?x?3时,i?1?2??j?1?3????????2???2??n(n?1)?j?1x?k时,i?1?k???100?n?2?求出满足此不等式的k值,即为语句i=i+j的程序步数。。设在等概率情形下,对有150个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?[1..m+n]中依次存放着两个向量(a,a,….a)和(b,b,….b),编写算12m12n法将两个向量的位置互换,即把(b,b,….b)放到(a,a,….a)之前。12n12m[题目分析]题目要求将两个向量逆置,可以先将两个向量分别逆置,再将整个向量逆置。(也可以先将整个向量逆置,再将两个向量分别逆置)申请额外的存储空间移动大量的数据元素,时间复杂度为m*nvoidreverse(ElemTypeA[])//数组A中有m+n个元素,本算法将两个向量逆置,即将前m个元素移至n个元素之后{inti;for(i=1;i<=m/2;i++)//将前m个元素逆置A[i]<-->A[m-i+1]for(i=1;i<=n/2;i++)//将后n个元素逆置A[m+i]<-->A[m+n-i+1]for(i=1;i<=(m+n)/2;i++)//将前m+n个元素逆置A[i]<-->A[m+n-i+1]}//算法结束:..【算法讨论】题目中下标从1开始,若用C语言的从0开始,则可写为:for(i=0;iA[m-i-1]for(i=0;iA[m+n-i-1]for(i=0;i<(m+n)/2;i++)//将前m+n个元素逆置A[i]<-->A[m+n-i-1],编写计算此链表长度的算法。[题目分析]计算单链表的长度,即求单链表中元素个数。intnumber(LinkedListla)//求不带头结点的单链表的长度{i=0;p=la;//p为工作指针while(p){i++;p=p->next;}returni;}//,试设计一个算法,将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。[题目分析]因为两链表已按元素值递增次序排列,将其合并时,均从第一个结点起进行比较,将小的链入链表中,同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时,将链表结点逆置。LinkedListUnion(LinkedListha,hb)∥ha,hb分别是带头结点的两个单链表的头指针,链表中的元素值按递增序排列,本算法将两链表合并成一个按元素值递减次序排列的单链表。{pa=ha->next;pb=hb->next;∥pa,pb分别是链表ha和hb的工作指针ha->next=null;∥ha作结果链表的头指针,先将结果链表初始化为空。while(pa!=null&&pb!=null)∥当两链表均不为空时作if(pa->data<=pb->data){r=pa->next;∥将pa的后继结点暂存于r。pa->next=ha->next;∥将pa结点链于结果表中,同时逆置。ha->next=pa;pa=r;∥恢复pa为当前待比较结点。}else{r=pb->next;∥将pb的后继结点暂存于r。pb->next=ha->next;∥将pb结点链于结果表中,同时逆置。ha->next=pb;pb=r;∥恢复pb为当前待比较结点。}if(pa)pb=pa;//为了下面算法统一,不再单独处理pawhile(pb!=null):..{r=pb->next;pb->next=ha->next;ha->next=pb;pb=r;}free(hb);return(ha);}∥算法Union结束。,实现以下的函数。(1)从顺序表中删除具有最小值的元素并由函数返回被删元素的值,空出的位置由最后一个元素填补。(2)从顺序表中删除具有给定值x的所有元素。(3)从有序顺序表中删除其值在给定值s与t之间(要求s小于t)的所有元素。[题目分析]在顺序表中查找指定值,要从头到尾的查,若为有序的顺序表,则可采用对分(折半)查找.(1)ElemTypeMiniDelete(SeqLists)//在顺序表中删除最小值元素,空出的位置由最后一个元素填补,返回最小值元素{ElemTypemin;//min记最小值元素k=0;//k记最小值元素下标,先假定第一个元素最小for(i=1;i<;i++)if([i]<[k]k=i;min=[k];[k]=[-1];--;returnmin;}//算法结束(3)voidDeleteST(SeqListl)//在顺序存储的有序表l中删除在给定值在s与t之间的所有元素{i=0;while(i<&&[i]=s的元素if(i==){printf(“表中元素都小于s,无s与t间的元素”);exit(0);}k=i;//k是第一个值>=s的元素的下标while(i<&&[i]<=t)i++;//查找第一个值>t的元素for(j=i;j<;j++)//元素前移,[k++]=[j]=k;//置线性表的长度}//算法结束voidDeleteST(SeqListl)//在顺序存储的有序表s中删除在给定值在s与t之间的所有元素{k=0;for(i=0;i<;i++){if([i]>=s&&[i]<=t)k++;[i-k]=[i];}=-k;//置线性表的长度}//算法结束(2)voidDeleteAllX(SeqLists,ElemTypex)//在顺序表s中删除所有值为x的元素:..{i=0;j=;//i,j是数组元素下标while(i

数据结构综合复习题 来自beplayapp体育下载www.apt-nc.com转载请标明出处.