数据结构-2.2.3做题记录

博主：彼岸花露
发布时间：2024 年 04 月 17 日
1684 次浏览
暂无评论
509字数
分类：习题

一

1. A
2. C ?A：顺序表可以用一维数组表示，因此顺序表与一维数组在逻辑结构上是相同的（X）
 
 	顺序表是顺序储存的线性表，表中所有的元素类型必须相同，且必须连续存放。一维数组的元素可以不连续存放；此外栈，队列，树等逻辑结构也可以用一维数组表示，但他与顺序表不属于相同的逻辑结构（顺序表也不一定都用一维数组实现）
3. B A **线性表的顺序储存结构是一种随机存取的储存结构** （√）顺序存取（X 更偏向与线性结构的单链表）
 
 	存取方式是指读/写方式，顺序表是一种支持随机存取的储存结构，根据起始地址加上元素号，可以很方便的访问任意一个元素，这就是随机存取的概念
4. C
5. B
6. B D //快速存期第i-1个 第i个 和第i+1个 考点：随机存取（如果考双向链表表述：若线性表最常用的操作是获得当前节点的前驱和后继）
7. A
 
 	![1](https://photo.w-4.cn/typora/202404162007334.svg)
8. C
9. A/ C 1输出第i（1<=i<=n）个元素值 2：交换第三个元素与第四个元素的值 3：顺序输出这n个元素
 
 1：顺序表可以随机存取，效率比链表高 2： 顺序表由于随机存取特性，可以直接对3、4号元素的数据进行更改；链表：要依次读取1，2号元素的指针 3：顺序输出，二者时间复杂度相等O（n）即效率相同
10. D C 长度n顺序表 删除第i个元素 需向前移动（？） 第i+1 到n需要向前移动 （1到n共n个 n-1+1）
11. C 复杂度指最坏复杂度
12. C
13. B
14. D
15. D 顺序储存的有序表（长度n）有序表：数据元素按元素值大小顺序排列的线性表
 
 A查找包含指定元素的算法 ：折半查找O(logn)
 
 B插入包含指定值元素的算法 1）折半查找找到插入位置 O(logn) 2)将该位置后的所有元素后移并放入元素O(n)
 
 C删除第i(1<=i<=n)个元素的算法 ，将 i之后的元素前一位 O(n)
 
 D 读出a[i] ,O(1)

**错误3，6，9，10**

二

1. 从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删除的值，空出的位置由最后一个元素填补，若顺序表为空则显示错误信息并停止运行。
 
 ```c++
 ElemType ListDeleteMin (Sqlist &L)
 {
 if (0==L.length)
 {
 printf("error\n");
 return 0;
 }
 int num=0;
 ElemType min=L.data[0];
 for (int i=1 ;i<L.length;i++)
 {
 if (L.data[i]<min)
 {
 min=L.data[i];
 num=i;
 }
 }
 L.data[num]=L.data[L.length-1];
 L.length--;
 return min;
 
 }//基本正确
 ```
 
 答案
 
 算法思想：先搜索整个顺序表，查找最小元素并记住其位置，搜索结束后用最后一个元素补空出来原最小值元素的位置。
 
 ```c
 bool Del_Min (Sqlist &L,ElemType &value)
 //删除顺序表L中最小值元素的节点，并通过引用型参数value返回其值
 //若删除成功，则返回ture 否则返回false
 {
 if (L.length==0)
 return false;
 value=L.data[0];
 int pos=0;
 for (int i=1 ;i<L.length;i++)
 {
 if (L.data[i]<value)
 {
 value=L.data[i];
 pos=i;
 }
 }
 L.data[pos]=L.data[L.length-1];
 L.length--;
 return true;
 
 }
 ```
 
 注：本题也可以使用返回值返回二者区别：函数返回值只能返回一个值，而参数返回（引用传参）可以返回多个值
2. 设计一个高效的算法，将顺序表L的所有元素逆置，要求算法空间复杂度为 O(1)
 
 首次
 
 ```c++
 没思路
 ```
 
 看完讲解 注意审题 要求的是空间复杂度不是时间复杂度
 
 ```c++
 void ListReverse(Sqlist &L)
 {
 int temp;
 for (i=1;i<L.length/2;i++)//少int i=0
 {
 temp=L.data[i];
 L.data[i]=L.data[L.length-1-i];
 L.data[L.length-1-i]=temp;
 }
 
 }
 ```
 
 答案
 
 算法思想：扫描顺序表L的前半部分元素，对于元素L.data\[i\]\(0<=i<L.length/2\)将于其后半部分的对应元素L.data[L.length-i-1]进行交换
 
 ```c
 void Reverse(Sqlist &L)
 {
 ElemType temp;//辅助变量
 for (int i=0;i<L.length/2;i++)
 {
 temp=L.data[i];
 L.data[i]=L.data[L.length-1-i];
 L.data[L.length-1-i]=temp;
 }
 }
 ```
3. 对于长度为n的顺序表L，编写一个时间复杂度为O（n），空间复杂度为O（1）的算法，该算法删除顺序表中所有值为x的数据元素
 
 初做
 
 ```c
 void DeleteX(Sqlist &L)
 {
 int j=0;
 for (int i=0;i<L.length;i++)
 {
 if (x==L.data[i])
 {
 j++;//不会了
 }
 }
 }
 ```
 
 讲解思路：为保证O(n)要一次结束 ，设立标记，前面有几个就前移几个
 
 ```c
 void DeleteX(Sqlist &L)
 {
 int mark=0;
 for (int i=0;i<L.length;i++)
 {
 L.data[i-mark]=L.data[i];
 if (x==L.data[i])
 {
 mark++;
 }
 }
 L.length-=mark;
 }
 ```
 
 答案
 
 解法一：用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数），扫描时将不等于x的元素移动到下标k的位置，并更新k值。扫描结束后修改L的长度。
 
 ```c
 void del_x_1(Sqlist &L ,ElemType x) //别忘了传入x
 {
 int k=0，i; //记录不等于x的个数
 for (i=0;i<L.length;i++)
 {
 if(x!=L.data[i])
 {
 L.data[k]=L.data[i];//注意这里
 k++;
 }
 }
 L.length=k; //顺序表L的长度等于k //想错过
 }
 ```
 
 解法二：用k记录顺序表L中等于x的元素个数，一边扫描L，一边统计k，并将不等于x的元素前移K个位置。扫描结束修改L的长度
 
 ```c
 void del_x_2(Sqlist &L ,ElemType x)
 {
 int k=0,i=0; //k记录值等于x的元素个数
 while(i<L.length)
 {
 if (L.data[i]==x)
 k++;
 else
 L.data[i-k]=L.data[i]; //当前元素前移k个位置
 i++;
 }
 L.length=L.length-k;
 }
 ```
4. 从顺序表中删除其值在给定值s和t之间（包含s和t，要求s<t）的所有元素。若s或t不合理或顺序表为空，则显示错误信息并退出运行。
 
 初次尝试
 
 ```c
 bool ListDelete(Sqlist &L)
 {
 if (s>=t || L.length==0)
 {
 printf("error\n");
 return 0;
 }
 int mark =0;
 for (int i=0;i<L.length;i++)
 {
 L.data[i-mark]=L.data[i];
 if (s<=L.data[i] && t>=L.data[i])
 {
 mark++;
 }
 
 }
 L.length-=mark;
 return true;
 }
 ```
 
 没有传入所需s，t参数值，删除逻辑有一点问题（测试貌似没问题）
 
 答案
 
 算法思想：从前向后扫描顺序表L，用k记录在s和t之间的元素个数（初始k=0）。对于当前扫描的元素，若其值不在s和t之间，则前移k个位置；否则执行k++。由于每个不在s和t之间的元素仅移动一次，因此算法效率高
 
 ```c
 bool Del_s_t(Sqlist &L,ElemType s,ElemType t)//删除顺序表L中值在给定值s和t（要求s<t）之间的元素
 {
 int i,k=0;
 if (L.length==0 || s>=t)
 return 0; //线性表为空或s,t不合法,返回
 for (i=0;i<L.length;i++)
 {
 if(L.data[i]>=s&&L.data[i]<=t)
 K++;
 else
 L.data[i-k]=L.data[i];//当前元素前移k个位置
 }
 L.length-=k; //长度减小
 return true;
 }
 ```
 
 若有序表改为无序表，能想到时间复杂度O（n）的算法吗？（提示散列表）
5. 从有序顺序表中删除所有重复的元素，使表中所有元素值均不同
 
 初次尝试
 
 ```c
 bool ListDelete(Sqlist &L)
 {
 int mark =0;
 for (int i=0;i<L.length-1;i++)
 {
 L.data[i-mark]=L.data[i];
 if (L.data[i]==L.data[i+1])
 {
 mark++;
 }
 }
 L.data[L.length-1-mark]=L.data[L.length-1];
 L.length-=mark;
 }//测试好像没问题
 ```
 
 答案
 
 算法思想：注意是有序顺序表，值相同的元素一定在连续的位置上，用类似直接插入排序的思想，**初始时将第一个元素视为非重复的有序表，之后依次判断后面的元素是否与前面非重复有序表的最后一个是否相同，若相同则继续向后判断，若不同则插入前面非重复有序表的最后，直至判断到表尾**
 
 ```c
 bool Delete_Same(Sqlist &L)
 {
 if (L.length==0)
 return false;
 int i,j;
 for (i=0,j=1;j<L.length;j++)
 if (L.data[i]!=L.data[j])
 L.data[++1]=L.data[j]; //++i是一个前缀递增操作符，它首先将变量i增加1，然后返回增加后的值。
 L.length=i+1;
 return true;
 }
 ```
 
 注:也可借鉴之前mark方式，或最笨的方法 都能得到大部分分；
6. 将俩个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表
 
 初做
 
 ```c
 Sqlist CatList(Sqlist L1,Sqlist L2)
 {
 Sqlist L3;
 L3.length=L1.length+L2.length;
 int i,k;
 ElemType value ;
 int pos=0,flag=1,count1=0,count2=0;// 写不下去 没有正确思路。
 for (i=1 ;i<L1.length;i++)
 {
 if (L1.data[i]<value)
 {
 value=L.data[i];
 pos=i;
 }
 
 }
 ```
 
 答案
 
 算法思想：首先按顺序不断取下俩个顺序表表头较小的结点存入新的顺序表中，然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面；
 
 ```c
 bool Merge(Seqlist A,Seqlist B,Seqlist &C)
 {
 if(A.length+B.length>C.Maxsize) //大于顺序表的最大长度
 return false;
 int i=0,j=0,k=0;
 while (i<A.length&&j<B.length) //循环，俩俩比较，小者存入结果表
 {
 if(A.data[i]<=B.data[j])
 C.data[K++]=A.data[i++];
 else
 C.data[k++]=B.data[j++];
 }
 while (i<A.length) //还剩一个没比较完的表
 C.data[k++]=A.data[i++];
 while (j<B.length)
 C.data[k++]=B.data[j++];
 C.length=k;
 return true;
 }
 ```
 
 本算法的方法非常典型，需牢固掌握
7. 已知在一维数组A[m+n]中依次存放两个线性表(a1 ,a2,a3,…,am )和(b1 ,b2,b3,…,bn )编写一个函数将数组中两个顺序表的位置互换，即将(b1 ,b2,b3,…,bn )放在(a1 ,a2,a3,…,am )的前面
 
 初做
 
 ```c
 void ListChange(ElemType a[],int m,int n)
 {
 ElemType *p;
 p=(ElemType*)malloc((m+n)*sizeof(ElemType));
 for (int i=0;i<n;i++)
 {
 p[i]=a[m+i];
 }
 for (int k=0;k<m;k++) //忘记初始化了
 {
 p[n+k]=a[k] //条件第一个漏写k
 }
 for (int j;j<m+n;j++)
 {
 a[j]=p[j];
 }
 free (p);
 
 }//基本正确
 ```
 
 答案
 
 算法思想：将顺序表A[m+n]中的全部元素(a1 ,a2,a3,…,am,b1 ,b2,b3,…,bn)原地逆置为(bn ,bn-1,bn-2,…,b1,am ,am-1,am-2,…,a1),然后对前n个元素和后m个元素分别使用逆置算法，即可得到(b1 ,b2,b3,…,bn,a1 ,a2,a3,…,am)，从而实现顺序表的位置互换。
 
 AB->BA
 
 1. (AB)-1=B-1A-1
 2. (B-1)-1(A-1)-1=BA
 
 ![题目7](https://photo.w-4.cn/typora/202404171009242.jpg-sy)
 
 ```c
 typedef int DataType;
 void Reverse(DataType A[],int left,int right,int arraySize)
 {
 if (left>=right || right >=arraySize)
 return ;
 int mid = (left + right)/2;
 for (int i=0;i<=mid-left;i++) //注意理解结束条件
 {
 DataType temp=A[left+i];
 A[left+i]=A[right-i];
 A[right-i]=temp;
 
 }
 }
 void Exchange (DAtaType A[],int n,int m,int arraySize)
 {
 Reverse(A,0,m+n-1,arraySize);
 Reverse(A,0,n-1,arraySize);
 Reverse(A,n,m+n-1,arraySize);
 }
 ```
8. 线性表(a1 ,a2,a3,…,an)中的元素递增有序且按顺序储存于计算机内。要求设计一个算法，完成用最小时间在表中查找数值为x的元素，若找到，则将其与后继元素位置交换，若找不到，则将其插入表中并使表中元素仍然有序。
 
 1
 
 ```c
 void Find(Sqlist &L) //漏泄ElemType x
 {
 int mid=L.length/2;
 int left=0 ,right=L.length-1,flag=0,pos;
 while(left<=right)
 {
 if (left==right)
 {
 pos=left;
 break;
 }
 if(x=L.data[mid])
 {
 flag=1;
 pos= mid;
 break;
 }
 else if(x<L.data[mid])
 {
 right=mid;
 mid=(left+right)/2;
 
 }
 else 
 {
 left=mid;
 mid=(right+left)/2;
 }
 }
 if(flag)
 { //判断是不是最后一个
 ElemType temp;
 temp=L.data[pos];
 L.data[pos]=L.data[pos+1];
 L.data[pos+1]=temp;
 }else
 {
 这里想写在pos之后的元素依次后移一个 L.data[pos]等于x
 }
 }//感觉像对分查找不知道咋写
 ```
 
 答案
 
 算法思路：顺序储存的线性表递增有序，可以顺序查找也可以折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应用折半查找法。
 
 ```c
 void SearchExchangeInsert(ElenType A[],ElenType x)
 {
 int low=0,high=n-1,mid;//low 和 high指向顺序表下界和上界的下标
 While(low<=high)
 {
 mid=(low+higt)/2;//找到中间位置
 if(A[mid]==x) break;//找到x退出循环
 else if(A[mid]<x) low=mid+1;//到中点右半部分查找
 else high =mid-1;//到中点左半部分查找 
 }
 if (A[mid]==x&&mid!=n-1)//若最后一个元素与x相等，则不存在与其后继交换的操作
 {
 t=A[mid];A[mid]=A[mid+1];A[mid+1]=t;
 }
 if(low>high){
 for (i=n-1;i>high;i--) A[i+1]=A[i];
 A[i+1]=x;
 }
 }
 ```
 
 也可以写成三个函数：查找函数、交换后继函数与插入函数。
9. 给定三个数列A、B、C，长度均为n，且均为**无重复元素**的**递增数列**，请设计一个时间上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。例如，数组A为{1,2,3}，数组B为{2,3,4}，数组C为{-1,0,2},则输出2。要求：1）给出算法基础思想。2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。3）说明你的算法的时间复杂度与空间复杂度
 
 1
 
 ```c
 //1)依次遍历A中元素，每个元素逐个查看B数组内是否含有 若含有则遍历C数组，若都含有此元素则逐行输出
 //2）
 void PrintSame (ElemType A[] ,ElemType B[],ElemType c[]) //没有传入n
 {
 for (int i=0;i<n;i++)
 {
 for (int j=0;j<n;j++)
 {
 if (B[j]==A[i])
 {
 for (int k=0;k<n;k++)
 {
 if (C[k]==A[i])
 printf("%d\n",A[i]); //找到后加入break结束循环
 }
 }//找到后加入break结束循环
 }
 
 }
 }
 //3）时间复杂度O(n^3) 空间复杂度O(1)
 ```
 
 暴力解法（满分13 8-9分）
 
 归并，11分![归并解法](https://photo.w-4.cn/typora/202404171554426.png-sy)
 
 答案
 
 算法思路：使用三个下标量从小到大遍历数组。当三个下标量指向的元素相等时，输出并向前推进指针，否则仅移动小于最大元素的下标变量，直到某个下标量移除数组范围。
 
 ```c
 void samekey (int A[],int B[],int C[],int n)
 {
 int i=0,j=0,k=0;//定义三个工作指针
 while(i<n&&j<n&&k<n)//相同则输出，并集体后移
 {
 if(A[i]==B[j]&&B[j]==C[k]){
 printf("%d\n",A[i]);
 i++,j++,k++;
 }else
 {
 int maxNum=max(A[i],max(B[j],C[k]));
 if(A[i]<maxNum) i++;
 if(B[j]<maxNum) j++;
 if(C[k]<maxNum) k++;
 }
 }
 }
 ```
 
 每个指针移动次数不超过n次，且每次循环至少有一个指针后移，所以时间复杂度为O(n)，算法只用到了常数个变量，空间复杂度为O(1)。
10. [2010统考]设将n(n>1)个整数存放到一维数组R中，设计一个在时间和空间两方面都都尽可能高效的算法，将R中所存的数列循环左移p(0<p<n)个位置。
 
 作答
 
 ```c
 void LeftMove(int A[],int n,int p)
 {
 int *q;
 q=(int*)malloc(n*sizeof(int));
 for (i=0;i<n-p;i++)
 {
 p[i]=A[p+i];
 }
 for (int j=n-p,int k=0;j<n;j++,k++)
 {
 p[j]=A[k];
 }
 free(q);
 }
 ```
 
 答案：
 
 数组分成俩部分A|B 要变成BA （A-1B-1）-1 =>BA
 
 ![题目10](https://photo.w-4.cn/typora/202404171723225.png-sy)
11. 1
12. 1
13. 1
14. 1
15. 1
16. 1
17. 1
18. 1
19. 1
20. 1

End

本文作者：彼岸花露
文章标题：数据结构-2.2.3做题记录
本文地址：https://www.tianlei.work/archives/116/
版权说明：若无注明，本文皆悟思记原创，转载请保留文章出处。

最后修改：2024 年 04 月 17 日