2021版王道《数据结构》编程题汇总

第二章 线性表P19

1

​ 1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

​ 算法思想：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填空出的原最小值元素的位置。

​ 代码：

bool Del_Min(sqList &L, EleType &value)
{//删除顺序表L中最小值元素节点，并通引用性参数value返回其值//若删除成功，则返回true；否则返回falseif(L.length==0)return false;					//表空，终止操作返回value=L.data[0];					//假定0号元素的值最小for(int i=1;i<L.length;i++)		//循环，寻找具有最小值的元素if(L.data[i]<value)		//让value记忆当前具有最小值的元素{Value=L.data[i];pos=i;}L.data[pos]=L.data[L.length-1];	//空出的位置由最后一个元素填补L.length--;return true;					//	此时，value即为最小值	
}

2

2.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O（1）。

算法思想：扫描顺序表L的前半部分元素，对于元素L.data[i]（0<=i<L.1 ength/2），将其与后半部分的对应元素L.data[L.1 ength-i-1]进行交换。

代码:

void Reverse(Sqlist &L)
{Elemtype temp;  	//辅助变量for(i=0;i<L.length/2;i++){temp=L.data[i];			//交换L.[data]与L.data[L.length-i-1]L.data[i]=L.data[L.length-i-1];L.data[L.length-i-1]=temp;}
} 

3

​ 3.对长度为n的顺序表L，编写一个时间复杂度为O(m）、空间复杂度为O（1）的算法，该算法删除线性表中所有值为x的数据元素。

​ 解法一：用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数），边扫描L边统计k，并将不等于x的元素向前移动k个位置，最后修改L的长度

​ 本题代码如下：

void del_x_1(Sqlist &l,Elemtype x)
{
//本算法实现删除顺序表中所有值为x的数据元素int k=0;					//记录值不等于x的元素个数for(i=0;i<L.length;i++)if(L.data[i]!=x){L.data[k]=L.data[i];k++;				//不等于x的元素增1}L.length=k;				//顺序表L的长度等于k;
}

​ 解法二：用k记录顺序表L中等于x的元素个数，边扫描L边统计k，并将不等于x的元素前移k个位置，最后修改L的长度。

​ 本题代码如下:

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++;					elseL.data[i-k]=L.data[i];	//当前元素前移k个位置i++;}L.length=L.length-k;			//顺序表L的长度递减
}

4

4.从有序顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素，如果s或t不合理或顺序表为空，则显示出错信息并退出运行。

注意：本题与上一题的区别。因为是有序表，所以删除的元素必然是相连的整体。

​ 算法思想：先寻找值大于等于s的第一个元素（第一个删除的元素），然后寻找值大于t的第个元素（最后一个删除的元素的下一个元素），要将这段元素删除，只需直接将后面的元素前移

​ 本题代码如下:

bool Del_s_t2(SqList &L,ElemType s, ElemType t)
{//删除有序表L中值在给定值s与t之间的所有元素int i,j;if(s>=t||L.length==0)return false;for(i=0;i<L.length&&L.data[i]<s;i++);//寻找大于等于s的第一个元素if(i>=L.length)return false;					 //所有元素均小于s，返回for(j=i;j<L.length&&L.data[j]<=t;j++)//寻找值大于t的第一个元素for(;j<L.length;i++,j++)L.data[i]=L.data[j];			 //前移，填补被删除元素位置L.length=i;return true;
}

5

5.从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，如果s或t不合理或顺序表为空，则显示出错信息并退出运行

算法思想:从前向后扫描顺序表L,用k记录下元素值在s到t之间元素的个数(初始时k=0).对于当前扫描的元素,若其值不在s到t之间,则前移k个位置;否则执行k++.由于这样每个不在s到t之间的元素仅移动一次,所以算法效率高.

本题代码如下:

bool Del_s_t(SqList &L, ElemType s, ElemType t){//删除顺序表L中值在给定值s与t之间(要求s<t)的所有元素int i, k=0;if(Llength==0||s>=t)return false;		//线性表为空或s、t不合法,返回for(i=0;i<L length i++){if(L data[i]>=s&&L data[i]<=t)k++;elseL.data[i-k]=L.data[i];	//当前元素前移k个位置}//for L, length-=k;				//长度减小return true;
}

注意:本题也可从后向前扫描顺序表,每遇到一个值在s到t之间的元素,则删除该元素,其后的所有元素全部前移.但移动次数远大于前者,效率不够高.

6

6.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同

算法思想:注意是有序顺序表,值相同的元素一定在连续的位置上,用类似于直接插入排序的思想,初始时将第一个元素视为非重复的有序表.之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同,若相同则继续向后判断,若不同则插入到前面的非重复有序表的最后,直至判断到表尾为止.

本题代码如下:

bool. Delete Same(SeqList& L){if (L.length==0)return fals;int i,j;					//i存储第一个不相同的元素,j为工作指针for (1-0,j=1:j<L, length:j++)if(L.data[i]!=L,data[j])	//查找下一个与上个元素值不同的元素L.data[++i]=L.data[j];	//找到后,将元素前移L.length=i+1;		return true;
}

7

7.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

算法思想:首先,按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中.然后,看哪个表还有剩余,将剩下的部分加到新的顺序表后面.

本题代码如下:

注意:本算法的方法非常典型,需牢固掌握.

bool Merga(SeqList A, SeqList B, SeqList &C){//将有序顺序表A与B合并为一个新的有序顺序表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)				//还剩一个没有比较完的顺序表while(j<B length)C.data[k++]=B.data[j++]C.length=k;return true;
}

8

8.已知在一维数组A[m+n]中依次存放两个线性表（a1,a2,a3,…，am）和（b1，b2,b3,…，bn）。试编写一个函数，将数组中两个顺序表的位置互换，即将（b1，b2b3，…，bn）放在（a1，a2a3，…，an的前面。

算法思想:先将数组A[m+n]中的全部元素(a1,a2a3…,am,b1,b2b3;…,bn)原地逆置为(bnbn-1, n2,",D1,m,m-1,am-2, a1),再对前n个元素和后m个元素分别使用逆置算法,即可得到(b,b2, b3,…,bn、a1,a2,a3,…,an),从而实现顺序表的位置互换.

本题代码如下:

typedef int DataType;
void Reverse(DataType A[],int left, int right, int arraysize){//逆转(a1eft, aleft+1, aleft+2… aright)为( aright, aright-1,…, aleft)if (left>=righti lright>=arraysize)return int mid=(left+right)/2i for(int 1=0ii<=mid-leftii++){Datatype temp=A[left+i]; A[left+i]=A[right-i]; A[right-i]=temp}
}
void Exchange(DataType A[, int m, int n, int arraysize){/*数组A[m+n]中,从0到m-1存放顺序表(a1,a2,a3,…,am),从m到m+n-1存放顺序表(b1,b2,b3…,bn),算法将这两个表的位置互换*/ Reverse(A, 0, m+n-1, arraysize);Reverse(A, 0, n-l, arraysize);Reverse(A, n, m+n-l, arraysize);
}

9

9.线性表(a1a2a，…，an）中的元素递增有序且按顺序存储于计算机内。要求设计一算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相交换，若找不到则将其插入表中并使表中元素仍递增有序

算法思想:顺序存储的线性表递增有序,可以顺序査找,也可以折半査找.题目要求"用最少的时间在表中查找数值为x的元素",这里应使用折半查找法

本题代码如下:

void SearchExchangeInsert(ElemType A[], ElemType x){int low=0, high=n-1, mid;		 //1ow和high指向顺序表下界和上界的下标while(low<=high){mid=(low+high)/2;			 //找中间位置if(A[mid]==x) break; 		 //找到x,退出 while循环else if(A[mid]<x) low=mid+1; //到中点mid的右半部去查else high=mid-1;			 //到中点mid的左半部去查}//下面两个if语句只会执行一个if(A[mid]==x&&mid!=n-1){		//若最后一个元素与x相等,//则不存在与其后继交换的操作t=A[mid]; A[mid]=A[mid+l]; A[mid+l]=t;}if(low>high){					//查找失败，插入数据元素for(i=n-1;i>high;i--) A[i+1]=A[i];	//后移元素A[i+1]=x;							//插入x}										//结束插入
}

本题的算法也可写成三个函数:查找函数、交换后继函数与插入函数.写成三个函数的优点是逻辑清晰、易读.

10

10.【2010统考真题】设将n（n>1）个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据由（X0,X1…，Xn-1变换为（Xp,Xp+1,…，Xn-1,X0,X1,…,Xp-1）.要求：

1）给出算法的基本设计思想

2）根据设计思想，采用C或C艹或JaⅦa语言描述算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度和空间复杂度

解答:

1)算法的基本设计思想:可将这个问题视为把数组ab转换成数组ba(a代表数组的前p个元素,b代表数组中余下的n-p个元素),先将a逆置得到a-1b,再将b逆置得到a-1b-1,最后将整个a-1b-1逆置得到(a-1b-1)-1=ba.设 Reverse函数执行将数组元素逆置的操作,对abcdefgh向左循环移动3(p=3)个位置的过程如下：

Reverse(0,p-1)得到 cbadefgh

Reverse(p,n-1)得到 cbahgfed

Reverse(0,n-1)得到 defghabc;

注: Reverse中,两个参数分别表示数组中待转换元素的始末位置

2)使用C语言描述算法如下:

void Reverse (int RU, int from, int to){for(i=0; i<(to-from +1)/2;i++){temp=R[from+i];R[from+i]=R[to-il;R[to-i]=temp;}
} 
void Converse(int R[], int n, int p){Reverse(R,0, p-1);Reverse(R,p, n-1);Reverse(R,0, n-1);
}

3)上述算法中三个 Reverse函数的时间复杂度分别为O（p/2)、O(n-p)/2)和O(n/2),故所设计的算法的时间复杂度为O(n),空间复杂度为O()

另解,借助辅助数组来实现.算法思想:创建大小为p的辅助数组S,将R中前p个整数依次暂存在S中,同时将R中后n-p个整数左移,然后将S中暂存的p个数依次放回到R中的后续单元.时间复杂度为O(n),空间复杂度为O§

11

11.【2011统考真题】一个长度为L（L21）的升序序列S，处在第「L2个位置的数称为S的中位数。例如，若序列S1=（1l，13,15,17,19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2,4,6,8,20），则S1和S2的中位数是11现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求:

1）给出算法的基本设计思想

2）根据设计思想，采用C或++或Java语言描述算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度和空间复杂度

解答：

1)算法的基本设计思想如下.

分别求两个升序序列A、B的中位数,设为a和b,求序列A、B的中位数过程如下:

① a=b,则a或b即为所求中位数,算法结束.

② a<b,则舍弃序列A中较小的一半,同时舍弃序列B中较大的一半,要求两次舍弃的长度相等

③若a>b,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求两次舍弃的长度相等在保留的两个升序序列中,重复过程①、②、③,直到两个序列中均只含一个元素时为止,较小者即为所求的中位数.

2）本题代码如下：

int M Search(int A[], int b[],int n)
{int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;//分别表示序列A和B的首位数、末位数和中位数whi1e(s1!=d1|s2!=d2){m1=(s1+d1)/2; m2=(s2+d2)/2; if(A[m1]==B[m2])return AIml]	//满足条件①if(A[m1]<B[m2])		//满足条件②{if((s1+d1)82=0) //若元素个数为奇数{s1=m1;		//舍弃A中间点以前的部分且保留中间点d2=m2;		//舍弃B中间点以后的部分且保留中间点}else(			//元素个数为偶数s1=m1+1;	//舍弃A中间点及中间点以前部分d2=m2;		//舍弃B中间点以后部分且保留中间点}}else(				//满足条件③if((s2+d2)2=0)	//若元素个数为奇数{				d1=m1		//含弃A中间点以后的部分且保留中间点S2=m2		//舍弃B中间点以前的部分且保留中间点}else{			//元素个数为偶数d1=m1;		//舍弃A中间点以后部分且保留中间点s2=m2+1;	//舍弃B中间点及中间点以前部分}}}return A[s1]<B[s2]?A[s1]:B[s2];
}

3）算法的时间复杂度为O（log2n),空间复杂度为O(1).

12

12.【2013统考真题】上知一个整数序列A=（a0,a1…，an-1），其中0≤ai<n（0≤1<n）若存在ap1=ap2=…=apm=x且m>n/2（0≤pk<n，1≤k≤m）则称x为A的主元素。例如A=（0,5,5,3,5,7,5,5），则5为主元素；又如A=（0,5,5,3,5,1,5,7），则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1.要求：

1）给出算法的基本设计思想

2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度和空间复杂度。

解答：

1）给出算法的基本设计思想：算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。

算法可分为以下两步：

① 取候选的主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1;当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

② 判断c中元素是否是真正的主元素。再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素

2）算法实现如下：

int Majority(int A[],int n)
{int i,c,count=1;					//c用来保存候选主元素，count用来计数c=A[0];								//设置A[0]为候选主元素for(i<1;i<n;i++)					//查找候选主元素if(A[i]==c)	count++;					//对A中的候选主元素计数elseif(count>0)					//处理不是候选主元素的情况count--；else{						//更换候选主元素，重新计数c=A[i];count=1;}if(count>0)for(i=count=0;i<n;i++)			//统计候选主元素的实际出现次数if(A[i]==c)count++;if(count>n/2) return c;				//确认候选元素else return-1； 					//不存在主元素
}

3）实现的程序的时间复杂度为O（n），空间复杂度为O（1）

说明：本题如果采用先排好序再统计的方法【时间复杂度可为 O（nlog2n）】，只要解答正确，最高可拿11分。即便是写出O（n2）的算法，最高也能拿10分，因此对于统考算法题，花费大量时间去思考最优解法是得不偿失的。

13

13.【2018统考真题】给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4.要求

1）给出算法的基本设计思想

2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释

3）说明你所设计算法的时间复杂度和空间复杂度。

解答：

1）要求在时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组B[n]

用来记录A中是否出现了1_{n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0.由于A中含有n个整数，因此可能返回的值是1}n+1，当A中n个数恰好为1_{n时返回n+1。当数组A中出现了小于等于0或大于n的值时，会导致1}n中出现空余位置，返回结果必然在1~n中，因此对于A中出现了小于等于0或大于n的值可以不采取任何操作。

经过以上分析可以得出算法流程：从A[0]开始遍历A，若0<A[i]<=n，则令B[A[i]-1]=1;否则不做操作。对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]==0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1~n之间。若B[i]全部不为0，返回i+1（跳出循环时i=n,i+1等于n+1），此时说明A中未出现的最小正整数是n+1。

2）算法实现：

int findMissMin(int A[],int n)
{int i,*B;						//标记数组B=(int *)malloc(sizeof(int)*n); //分配空间memset(B,0,sizeof(int)*n);		//赋初值为0for(i=0;i<n;i++)if(A[i]>0&&A[i]<=n)			//若A[i]的值介于1~n，则标记数组BB[A[i]-1]=1;for(i=0;i<n;i++)				//扫描数组B，找到目标值if(B[i]==0) break;return i+1;						//返回结果
}

3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O（1）量级，因此时间复杂度为O（n）。空间复杂度：额外分配了B[n]，空间复杂 度为O（n）.