王道计算机数据结构考研——线性表

题目

线性表的定义和基本操作

单项选择题

线性表是具有()的有限序列

A. 数据表
B. 字符
C. 数据元素
D. 邻接表

答案：C。线性表是由具有相同数据类型的有限数据元素组成的，数据元素是由数据项组成的。

以下()是一个线性表

A. 由$n$个实数组成的集合
B. 由100个字符组成的序列
C. 所有整数组成的序列
D. 邻接表

答案：B。线性表定义的要求为：相同数据类型、有限序列。选项C的元素个数是无穷个，错误；选项A集合中的元素没有前后驱关系，错误；选项D属于存储结构，线性表是一种逻辑结构，不要将二者混为一谈。只有选项B符合线性表定义的要求。

在线性表中，除开始元素外，每个元素().

A. 只有唯一的前驱元素
B. 只有唯一的后继元素
C. 有多个前驱元素
D. 有多个后继元素

答案：A。线性表中，除最后一个(或第一不)元素外，每个元素都只有一个后继(或前驱)元素。

线性表的顺序表示

单项选择题

下述()是顺序存储结构的优点

A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 方便地运用于各种逻辑结构的存储表示

答案：A。顺序表不像链表那样要在结点中存放指针域，因此存储密度较大，A正确。B和C是链表的优点。D是错误的，比如对于树形结构，顺序表显然不如链表表示起来方便。

线性表的顺序存储结构是一种()

A. 随机存取的存储结构
B. 顺序存取的存储结构
C. 索引存取的存储结构
D. 散列存取的存储结构

答案：A。本题易误选B。注意，存取方式是指读写方式。顺序表是一种支持随机存取的存储结构，根据起始地址加上元素的序号，可以很方便地访问任意一个元素，这就是随机存取的概念

一个顺序表所占用的存储空间大小与()无关

A. 表的长度
B. 元素的存放顺序
C. 元素的类型
D. 元素中各字段的类型

答案：B。顺序表所占的存储空间=表长*sizeof (元素的类型)，表长和元素的类型显然会影响存储空间的大小。若元素为结构体类型，则元素中各字段的类型也会影响存储空间的大小

若线性表最常用的操作是存取第$i$个元素及其前驱和后继元素的值，为了提高效率，应采用()的存储方式

A. 单链表
B. 双向链表
C. 单循环链表
D. 顺序表

答案：D。题干实际要求能最快存取第$i-1$，$i$和$i+1$个元素值。A、B、C都只能从头结点依次顺序查找，时间复杂度为$O(n)$。只有顺序表可以按序号随机存取，时间复杂度为$O(1)$。

一个线性表最常用的操作是存取任意一个指定序号的元素并在最后进行插入、删除操作，则利用()存储方式可以节省时间。

A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表

答案：A。只有顺序表可以按序号随机存取，且在最后进行插入和删除操作时不需要移动任何元素。

在$n$个元素的线性表的数组表示中，时间复杂度为$O(1)$的操作是()

I. 访问第$i (1 \leq i \leq n)$个结点和求第$i (2 \leq i \leq n)$个结点的直接前驱
II. 在最后一个结点后插入一个新的结点
III. 删除第1个结点
IV. 在第$i (1 \leq i \leq n)$个结点后插入一个结点

A. I
B. II、III
C. I、II
D. I、II、III

答案：C。 I解析略；II中，在最后位置插入新结点不需要移动元素，时间复杂度为$O(1)$； III中，被删结点后的结点需依次前移，时间复杂度为$O(n)$。(〃)；IV中，需要后移$n-i$个结点，时间复杂度为$O(n)$。

设线性表有$n$个元素，严格说来，以下操作中，()在顺序表上实现要比在链表上实现的效率高

I. 输出第$i (1\leq i \leq n)$个元素值
II. 交换第3个元素与第4个元素的值
III. 顺序输出这$n$个元素的值

A. I
B. I、III
C. I、II
D. II、III

答案：C。对于II，顺序表仅需3次交换操作(a=b,b=c,a=c)；链表则需要分别找到两个结点前驱，第4个结点断链后再插入到第2个结点后，效率较低。对于III，需依次顺序访问每个元素，时间复杂度相同。

在一个长度为$n$的顺序表中删除第$i(1 \leq i \leq n)$个元素时，需向前移动()个元素

A. $n$
B. $i - 1$
C. $n - i$
D. $n - i + 1$

答案：C。需要将$a_{i+1}-a_n$元素依次前移一位，共移动$n-(i+1)+1=n-i$个元素

对于顺序表，访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为()

A. $O(n), O(n) $
B. $O(n), O(1) $
C. $O(1), O(n) $
D. $O(1), O(1)$

答案：C。在第$i$个位置插入一个元素，需要移动$n-i+1$个元素，时间复杂度为$O(n)$。

若长度为$n$的非空线性表采用顺序存储结构，在表的第$i$个位置插入一个数据元素，则$i$的合法值应该是()

A. $1 \leq i \leq n$
B. $1 \leq i \leq n+1$
C. $0 \leq i \leq n-1$
D. $0 \leq i \leq n$

答案：B。线性表元素的序号是从1开始，而在第$n+1$个位置插入相当于在表尾追加。

在顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有()可分配的存储空间。

A. $m$个
B. $m$个连续
C. $n + m$个
D. $n + m$个连续

答案：D。顺序存储需要连续的存储空间，在申请时需申请$n + m$个连续的存储空间，然后将线性表原来的$n$个元素复制到新申请的$n + m$个连续的存储空间的前$n$个单元。

综合应用题

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

答案：

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

bool Del_Min(SqList &L,ElemType &value)(
//删除顺亩表L中最小值元素结点，并通过引用型参数value返回其值
//若删除成功，则返回true；否则返回false
    if(L.length==0)
    	return false;					//表空，中止操作返回
    value=L.data[0]; 					
    int pos=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即为最小值
}

设计一个高效算法，将顺序表Z的所有元素逆置，要求算法的空间复杂度为$O(1)$。

答案：

算法思想：扫描顺序表 Z 的前半部分元素，对于元素 L.data[i](0 <= i < L.length / 2)，将其与后半部分的对应元素 L.data[L.length - i - 1] 进行交换。本题代码如下：

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

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

答案：

解法1：用$k$记录顺序表$L$中不等于x的元素个数(即需要保存的元素个数)，扫描时将不等于x的元素移动到下标左的位置，并更新k值。扫描结束后修改$L$的长度。本题代码如下：

void del_x_l(Sqlist &L,ElemType x){
//本算法茹潮除顺序表L中所有值为x的数据元
	int k=0,i;								//记录不等于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
}

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

此外，本题还可以考虑设头、尾两个指针$i=1,j=n$，从两端向中间移动，在遇到最左端$x$的元素时，直接将最右端值非$x$的元素左移至值为$x$的数据元素位置，直到两指针相遇。但这种方法会改变原表中元素的相对位置。

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

答案：

在很多教材中(包括本书)指的“有序”，如无特别说明，通常是指"递增有序”。注意本题与上题的区别，因为是有序表，所以删除的元素必然是相连的整体。算法思想：先寻找值大于或等于s的第一个元素(第一个删除的元素)，然后寻找值大于f的第一个元素(最后一个删除的元素的下一个元素)，要将这段元素删除，只需直接将后面的元素前移。本题代码如下：

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

从顺序表中删除其值在给定值$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 &LrElemType s,ElemType t){
//删除顺序表L中值在给定值s与t (要求s<t)之间的所有元素
    int i,k=0;
 	if(L・length==0||s>=t)
        return false;. 				//线性表为空或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;
}

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

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

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

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

对于本题的算法，请读者用序列 1,2,2,2,2,3,3,3,4,4,5来手动模拟算法的执行过程，在模拟过程中要标注i和i所指示的元素。思考：如果将本题的有序表改为无序表，你能想到时间复杂度为$O(n)$的方法吗？（提示：使用散列表。）

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

答案： 算法思想：首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。本题代码如下:

bool Merge(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)				//还剩一个没有比较完的顺序表
        C.data[k++]=A.data[i++];
    while(j<B.length)
        C.data[k++]=B.data[j++];
    C.length=k;
	return true;
}

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

已知在一维数组$A[m+n]$中依次存放两个线性表$(a_1,a_2,a_3······a_m)$和$(b_1,b_2,b_3······b_n)$。编写一个函数，将数组中两个顺序表的位置互换，即将$(b_1,b_2,b_3······b_n)$放在$(a_1,a_2,a_3······a_m)$的前面。

答案： 算法思想：先将数组$A[m+n]$中的全部元素$(a_1,a_2, a_3,···,a_m, b_1,b_2,b_3,···,b_n,)$原地逆置为$(b_n,b_{n-1},b_{n-2},···,b_1,a_{m},a_{m-1}, a_{m-2},···,a_1)$，$(a_1,a_2, a_3,···,a_m, b_1,b_2,b_3,···,b_n,)$再对前n个元素和后m个元素分别使用逆置算法，即可得到$(b_1,b_2,b_3,···,b_n,a_1,a_2, a_3,···,a_m, )$，从而实现顺序表的位置互换。本题代码如下:

typedef int DataType;
void Reverse(DataType All,int left,int right,int arraySize){
//逆转(aleft,aleft+l,aleft+2…,aright)为(aright,aright-l,… aleft)
	if(left>=right || right>=arraySize)	return false;
    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 xchange(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-l,arraySize);
	Reverse(A,0,n-l,arraySize);
	Reverse(A,n,m+n-l,arraySize);
}

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

答案： 算法思想：顺序存储的线性表递增有序，可以顺序查找，也可以折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找法。本题代码如下:

void SearchExchangeInsert(ElemType A{],ElemType x){
	int low=0,high=n-l,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-l;			//到中点mid的左半部去查
	//下面两个if语句只会执行一个
	if(A[mid]==x&&mid!=n-1){
	//若最后一个元素与x相等，则不存在与其后继交换的操作
		t=A{mid]; A[mid]=A[mid+l]; A[mid+1]=t;
	}
	//查找失败，插入数据元素x
	if(low>high){
		for(i=n-1;i>high;i--)	A[i+1]=A[i];	//后移元素
		//插入x
		A[i+1]=x;
	//结束插入
	}
}

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

【2010统考真题】设将$n$ $(n > 1 )$个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将$R$中保存的序列循环左移$p$ $(0<p<n)$个位置，即将$R$中的数据由$(X_0,X_1,X_2,X_3······X_{n-1})$换为$(X_p,X_{p+1},X_{p+2}······X_{n-1},X_0,X_1······X_{p-1})$，要求：

给出算法的基本设计思想。
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。

答案： 1)算法的基本设计思想: 可将问题视为把数组ab转换成数组 ba(a代表数组的前p个元素，b代表数组中余下的n-p个元素)，先将a逆置得到a'b，再将b逆置得到a'b'，最后将整个a'b'逆置得到(a'b')' = 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 Rll,int from,int to){
	int i,temp;
	for(i=0:i<(to-from+1)/2;i++)
	{
		temp=R[from+i];
		R[from+i]=R{to-i];R[to-i]=temp;
	}//Reverse
}
void Converse(int R[]rint n,int p){
	Reverse(R,0,p-1);
	Reverse(R,p,n-1);
	Reverse(R,0,n-l);
}

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

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

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

给出算法的基本设计思想。
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。

答案： 1)算法的基本设计思想如下。分别求两个升序序列 A、B的中位数，设为a和b，求序列A、B的中位数过程如下：

若a=b，则a或b即为所求中位数，算法结束。
若a<b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等。
若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等。

在保留的两个升序序列中，重复过程1、2、3，直到两个序列中均只含一个元素时为止较小者即为所求的中位数。 2)本题代码如下:

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

3)算法的时间复杂度为$O(log_2n)$，空间复杂度为$O(1)$。

【2013统考真题】已知一个整数序列$A=(a_0,a_1,···,a_{n-1})$，其中$0 \leq a_i \leq n(0 \leq i <n)$，若存在$a_{p1}=a_{p2}=···=a_{pm}=x$且$m>n/2(0 \leq p_k < n, 1 \leq k \leq 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。要求：

给出算法的基本设计思想。
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。

答案： 1)算法的基本设计思想：算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。算法可分为以下两步:

选取候选的主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到c中，记录 Num 的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
判断c中元素是否是真正的主元素。再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。

2)算法实现如下:

int Majority(int A[],int n){
	//c用来保存候选主元素，count用来计数
	//设置A[0]为候选主元素	
    int i，c,count=l;
	c=A[0];
	//查找候选主元素
	for(i=1;i<n;i++)
		if(A[i]==c)	count++;		//对A中的候选主元素计数
		else						
			if(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(nlog_2n)$]，只要解答正确,最高可拿 11 分。即便是写出$O(n^2)$的算法，最高也能拿10分，因此对于统考算法题，花费大量时间去思考最优解法是得不偿失的。

【2018统考真题】给定一个含$n (n \geq1)$个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。

示例：数组 [-5, 3, 2, 3] 中未出现的最小正整数是 1。数组 [1, 2, 3] 中未出现的最小正整数是 4。要求：

给出算法的基本设计思想。
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。
答案： 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);		//分配空间 
		//赋初值为0
		memset(B,0,sizeof(int)*n);
		for(i=0;i<n;i++)
			if(A[i]>0&&A[i]<=n)				//若A[i]的值介于1~n，则标记数组B
				B[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)$。

【2020统考真题】定义三元组 $(a, b, c)$（$a, b, c$ 均为整数）的距离 $D = |a - b| + |b - c| + |c - a|$。给定 3 个非空整数集合 $S1、S2$ 和 $S3$，按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a, b, c) (a ∈ S1, b ∈ S2, c ∈ S3)$ 中的最小距离。

示例：S1 = [-1, 0, 9] ，S2 = [-25, -10, 10, 11] ，S3 = [2, 9, 17, 30, 41]，则最小距离为 2，对应的三元组为 (9, 10, 9)。

要求：

给出算法的基本设计思想。
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。

答案： 分析。由$D=|a-b|+|b-c|+|c-a| \geq0$有如下结论。

当a=b=c时，距离最小。
其余情况。不失一般性，假设 $a \leq b \leq c$，观察下面的数轴: \[ L_1=|a-b| \\ L_2=|b-c| \\ L_3=|c-a| \\ D=|a-b|+|b-c|+|c-a|=2L_3 \] 由D的表达式可知，事实上决定D大小的关键是a和c之间的距离，于是问题就可以简化为每次固定c找一个a，使得$L_3=|c-a|$最小。

1)算法的基本设计思想

使用$D_{min}$记录所有已处理的三元组的最小距离，初值为一个足够大的整数。
集合 $S_1,S_2,S_3$，分别保存在数组 A、B、C中。数组的下标变量i=j=k=0，当$i<|S_1|,j<|S_2|,k<|S_3|$时($|S|$表示集合$S$中的元素个数)，循环执行下面的 a)~c)。

a)计算(A[i],B[J]],C[k])的距离D。(计算 D) b)若$D<D_{min}$，则$D_{min}=D$。(更新 D)

c)将 A[i]、B[j]、C[k]中的最小值的下标+1; (对照分析:最小值为a，最大值为c，这里c不变而更新a，试图寻找更小的距离 D)
输出 $D_{min}$结束。

2)算法实现：

#define INT MAX 0x7fffffff
int abs(int a){	//计算绝对值if(a<0)
    return -a;
    else return a;
}
bool xls_min(int a,int b,int c){//a是否是三个数中的最小值
    if(a<=b&&a<=c)	return true;
    return false;
}
int findMinofTrip(int Al,,int n,int Bll,int m,int c{],int p){
    //D min用于记录三元组的最小距离，初值赋为INT_MAX
    int i=0,j=0,k-0,Dmin=INT_MAX,D;
    while(i<n&&j<m&&k<p&&D min>0){
        D=abs(A[i]-B[j])+abs(B[j]-C[k])+abs(c[k]-A[i]);			//计算D
        if(D<Dmin)Dmin=D;//更新Dmin
        if(xls_min(A[i],B[j],C[k]))	i++;//更新a
        else if(xls+min(B{j],Cfk],Ali])) j++;
        else k++;
    }
	return Dmin;
}

3)设$n=(|S_1|+|S_2|+|S_3|)$，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。