资源描述：
《数据结构综合复习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章综合练习2.什么是数据结构?有关数据结构的讨论涉及哪三个方面?【解答】数据结构是指数据以及相互之间的关系。记为：数据结构={D,R}。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。有关数据结构的讨论一般涉及以下三方面的内容：①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；②数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；③施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是
2、数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。5.设n为正整数,分析下列各程序段中加下划线的语句的程序步数。(1)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){c[i][j]=0.0;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
3、;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);【解答】(1)(2)(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)，解
4、出满足上述不等式的k值，即为语句i=i+1的程序步数。(4)求出满足此不等式的k值，即为语句i=i+j的程序步数。第二章综合题2.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有150个元素的顺序表进行插入，平均需要移动多少个元素?删除一个元素，又平均需要移动多少个元素?3.已知在一维数组A[1..m+n]中依次存放着两个向量（a1,a2,….am）和（b1,b2,….bn），编写算法将两个向量的位置互换，即把（b1,b2,….bn）放到（a1,a2,….am）之前。[题目分析]题目要求将两个向量逆置,可以先将两个向量分别逆置,再将整个向量逆置。(也可以先将整个
5、向量逆置,再将两个向量分别逆置)申请额外的存储空间移动大量的数据元素，时间复杂度为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开始,则
6、可写为: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]4.给定一个不带头结点的单链表，编写计算此链表长度的算法。[题目分析]计算单链表的长度,即求单链表中元素个数。intnumber(LinkedListla)//求不带头结点的单链表的长度{i=0;p=la;//p为工作指针while(p){i++;p=p->next;}returni;}//算法
7、结束5.设ha和hb分别是两个带头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。LinkedListUnion(
