Chapter2.2：线性表的顺序表示习题
该系列属于计算机基础系列中的《数据结构基础》子系列，参考书《数据结构考研复习指导》(王道论坛 组编)，完整内容请阅读原书。
2.线性表的顺序表示
2.3 线性表顺序表示的习题
2.3.1 单项选择题
-
下述( )是顺序存储结构的优点。
- 存储密度大；
- 插入运算方便；
- 删除运算方便；
- 方便地运用于各种逻辑结构的存储表示；
-
线性表的顺序存储结构是一种( )。
- 随机存取的存储结构；
- 顺序存取的存储结构；
- 索引存取的存储结构；
- 散列存取的存储结构；
-
一个顺序表所占用的存储空间大小与( )无关。
- 表的长度；
- 元素的存放顺序；
- 元素的类型；
- 元素中各字段的类型；
-
若线性表最常用的操作是存取第iii个元素及其前驱和后继元素的值，为了提高效率，应采用( )的存储方式。
- 单链表；
- 双向链表；
- 单循环链表；
- 顺序表；
-
一个线性表最常用的操作是存取任一指定序号的元素并在最后进行插入、删除操作，则利用( )存储方式可以节省时间。
- 顺序表；
- 双链表；
- 带头结点的双循环链表；
- 单循环链表；
-
在nnn个元素的线性表的数组表示中，时间复杂度为O(1)O(1)O(1)的操作是( )。
Ⅰ.访问第i(1≤i≤n)i(1≤i≤n)i(1≤i≤n)个结点和求第i(2≤i≤n)i(2≤i≤n)i(2≤i≤n)个结点的直接前驱；
Ⅱ.在最后一个结点后插入一个新的结点；
Ⅲ.删除第111个结点；
Ⅳ.在第i(1≤i≤n)i(1≤i≤n)i(1≤i≤n)个结点后插入一个结点；
- Ⅰ；
- Ⅱ、Ⅲ；
- Ⅰ、Ⅱ；
- Ⅰ、Ⅱ、Ⅲ；
-
设线性表有nnn个元素，严格来说，以下操作中，( )在顺序表上实现要比在链表上实现的效率高。
Ⅰ.输出第i(1≤i≤n)i(1≤i≤n)i(1≤i≤n)个元素值；
Ⅱ.交换第333个元素和第444个元素的值；
Ⅲ.顺序输出这nnn个元素的值；
- Ⅰ；
- Ⅰ、Ⅲ；
- Ⅰ、Ⅱ；
- Ⅱ、Ⅲ；
-
在一个长度为nnn的顺序表中删除第i(1≤i≤n)i(1≤i≤n)i(1≤i≤n)个元素时，需向前移动( )个元素。
- nnn；
- i−1i-1i−1；
- n−in-in−i；
- n−i+1n-i+1n−i+1；
-
对于顺序表，访问第iii个位置的元素和在第iii个位置插入一个元素的时间复杂度为( )。
- O(n),O(n)O(n),O(n)O(n),O(n)；
- O(n),O(1)O(n),O(1)O(n),O(1)；
- O(1),O(n)O(1),O(n)O(1),O(n)；
- O(1),O(1)O(1),O(1)O(1),O(1)；
-
若长度为nnn的非空线性表采用顺序存储结构，在表的第iii个位置插入一个数据元素，则iii的合法值应该是( )。
- 1≤i≤n1≤i≤n1≤i≤n；
- 1≤i≤n+11≤i≤n+11≤i≤n+1；
- 0≤i≤n−10≤i≤n-10≤i≤n−1；
- 0≤i≤n0≤i≤n0≤i≤n；
-
顺序表的插入算法中，当nnn个空间已满时，可再申请增加分配mmm个空间，若申请失败，则说明系统没有( )可分配的存储空间。
- mmm个；
- mmm个连续；
- n+mn+mn+m个；
- n+mn+mn+m个连续；
2.3.2 综合应用题
-
从顺序表中删除具有最小值的元素(假设唯一)，并由函数返回被删元素的值，空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
解：
算法思想：搜索整个顺序表，查找最小值并记住其位置，搜索结束后，用最后一个元素填补空出的原最小值元素的位置。
核心代码：
bool Del_Min(SqList &L,ElemType &value){// 删除顺序表L中最小值元素结点，并通过引用型参数value返回其值// 若删除成功，返回true；否则返回falseif(L.length == 0) // 表空，中止操作返回 return false;value=L.data[0]; // 假设0号元素值最小int pos=0;// 寻找最小值元素for(int i=1;i -
设计一个高效算法，将顺序表LLL的所有元素逆置，要求算法的空间复杂度为O(1)O(1)O(1)。
解：
算法思想：扫描顺序表LLL的前半部分元素，对于元素L.data[i](0<=i
核心代码：
void Reverse(SqList &L){Elemtype temp;// 交换L.data[i]与L.data[L.length-i-1]for(i=0;itemp=L.data[i]; L.data[i]=L.data[L.length-i-1];L.data[L.length-i-1]=temp;} } -
对长度为nnn的顺序表LLL，编写一个时间复杂度为O(n)O(n)O(n)、空间复杂度为O(1)O(1)O(1)的算法，该算法删除线性表中所有值为xxx的数据元素。
解：
【解法1】
算法思想：用kkk记录顺序表LLL中不等于xxx的元素个数，边扫描顺序表LLL边统计kkk，将不等于xxx的元素向前移动kkk个位置，最后修改LLL的长度。
核心代码：
void del_x_1(SqList &L,Elemtype x){int k=0; // 记录值不等于x的元素个数for(i=0;i【解法2】
算法思想：用kkk记录顺序表LLL中等于xxx的元素个数，边扫描顺序表LLL边统计kkk，将不等于xxx的元素向前移动kkk个位置，最后修改LLL的长度。
核心代码：
void del_x_2(SqList &L,Elemtype x){int k=0,i=0;while(i -
从有序顺序表中删除其值在给定值sss与ttt之间(要求s
解：
算法思想：先寻找大于等于sss的第一个元素，然后寻找大于ttt的第一个元素，要将这段元素删除，只需直接将后面的元素前移。
核心代码：
bool Del_s_t2(SqList &L,ElemType s,ElemType t){int i,j;if(s>=t || L.length == 0)return false;// 寻找值大于等于s的第一个元素for(i=0;i -
从顺序表中删除其值在给定值sss与ttt之间(包含sss与ttt，要求s
解：
算法思想：从前往后扫描顺序表LLL，用kkk记录元素值在sss到ttt间元素的个数，对于当前扫描的元素，若其值不在sss到ttt间，则前移kkk个位置，否则执行k++k++k++。
核心代码：
bool Del_s_t(SqList &L,ElemType s,ElemType t){int i,k=0;if(L.length==0 || s>=t)return false; // 线性表为空或s、t不合法，返回for(i=0;i -
从有序顺序表中删除所有值重复的元素，使表中所有元素的值均不同。
解：
算法思想：题设中是有序顺序表，因此，值相同的元素一定在连续的位置上，初始时将第一个元素视为非重复的有序表，后依次判断后面的元素是否与前面的非重复有序表的最后一个元素相同，若相同，则继续向后判断，若不同，则插入前面的非重复有序表的最后，直至判断到表尾为止。
核心代码：
bool Delete_Same(SeqList &L){if(L.length == 0)return false;int i,j; // i存储第一个不相同的元素，j为工作指针for(i=0,j=1;j -
将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
解：
算法思想：先按顺序不断取下两个顺序表表头较小的结点存入新的顺序表，然后看哪个表还有剩余，将剩下的部分加到新的顺序表后面。
核心代码：
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[m+n]A[m+n]A[m+n]中依次存放两个线性表(a1,a2,⋯,am)(a_1,a_2,\cdots,a_m)(a1,a2,⋯,am)和(b1,b2,⋯,bn)(b_1,b_2,\cdots,b_n)(b1,b2,⋯,bn)。编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,⋯,bn)(b_1,b_2,\cdots,b_n)(b1,b2,⋯,bn)放在(a1,a2,⋯,am)(a_1,a_2,\cdots,a_m)(a1,a2,⋯,am)的前面。
解：
算法思想：先将数组A[m+n]A[m+n]A[m+n]中的全部元素(a1,a2,a3,⋯,am,b1,b2,b3⋯,bn)(a_1,a_2,a_3,\cdots,a_m,b_1,b_2,b_3\cdots,b_n)(a1,a2,a3,⋯,am,b1,b2,b3⋯,bn)原地逆置为(bn,bn−1,bn−2,⋯,b1,am,am−1,am−2,⋯,a1)(b_n,b_{n-1},b_{n-2},\cdots,b_1,a_m,a_{m-1},a_{m-2},\cdots,a_1)(bn,bn−1,bn−2,⋯,b1,am,am−1,am−2,⋯,a1)，再对前nnn个元素和后mmm个元素分别使用逆置算法，即可得到(b1,b2,b3,⋯,bn,a1,a2,⋯,am)(b_1,b_2,b_3,\cdots,b_n,a_1,a_2,\cdots,a_m)(b1,b2,b3,⋯,bn,a1,a2,⋯,am)，从而实现顺序表的位置互换。
核心代码：
typedef int DataType; void Reverse(DataType A[],int left,int right,int arraySize){// 逆转(aleft,aleft+1,...,aright)为(aright,aright-1,...,aleft)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 m,int n,int arraySize){Reverse(A,0,m+n-1,arraySize);Reverse(A,0,n-1,arraySize);Reverse(A,n,m+n-1,arraySize); } -
线性表(a1,a2,⋯,an)(a_1,a_2,\cdots,a_n)(a1,a2,⋯,an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为xxx的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。
解：
算法思想：顺序存储的线性表递增有序，可以顺序查找，亦可折半查找，题设要求用最少时间在表中查找数值为xxx的元素，因此，使用折半查找法。
核心代码：
void SearchExchangeInsert(ElemType A[],ElemType x){int low=0,high=-1,mid,t; // low：顺序表下界下标；high：顺序表上界下标；while(low<=high){mid=(low+high)/2;if(A[mid]==x)break;else if(A[mid] -
设将n(n>1)n(n>1)n(n>1)个整数存放到一维数组RRR中。设计一个在时间和空间两方面都尽可能高效的算法。将RRR中保存的序列循环左移p(0
- 给出算法的基本设计思想；
- 根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
- 说明你所设计算法的时间复杂度和空间复杂度；
解：
-
给出算法的基本设计思想；
算法基本设计思想：将这个问题视为把数组ababab转换成数组bababa(aaa代表数组的前ppp个元素，bbb代表数组中余下的n−pn-pn−p个元素)，将aaa逆置得到a−1ba^{-1}ba−1b，再将bbb逆置得到a−1b−1a^{-1}b^{-1}a−1b−1，最后整个a−1b−1a^{-1}b^{-1}a−1b−1逆置得到(a−1b−1)−1=ba(a^{-1}b^{-1})^{-1}=ba(a−1b−1)−1=ba.设Reverse{\rm Reverse}Reverse函数执行将数组元素逆置的操作，对abcdefgh{\rm abcdefgh}abcdefgh向左循环移动3(p=3)3(p=3)3(p=3)个位置过程如下：
Reverse(0,p−1){\rm Reverse(0,p-1)}Reverse(0,p−1)得到cbadefgh{\rm cbadefgh}cbadefgh；
Reverse(p,n−1){\rm Reverse(p,n-1)}Reverse(p,n−1)得到cbahgfed{\rm cbahgfed}cbahgfed；
Reverse(0,n−1){\rm Reverse(0,n-1)}Reverse(0,n−1)得到defghabc{\rm defghabc}defghabc；
-
根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
使用C{\rm C}C语言描述算法如下：
void Reverse(int R[],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;} }void Converse(int R[],int n,int p){Reverse(R,0,p-1);Reverse(R,p,n-1);Reverse(R,0,n-1); } -
说明你所设计算法的时间复杂度和空间复杂度；
上述算法中三个Reverse{\rm Reverse}Reverse函数时间复杂度分别为：O(p/2),O((n−p)/2),O(n/2)O(p/2),O((n-p)/2),O(n/2)O(p/2),O((n−p)/2),O(n/2)，因此，所设计的算法时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)。
-
一个长度为L(L≥1)L(L≥1)L(L≥1)的升序序列SSS，处在第[L/2][L/2][L/2]个位置的数称为SSS的中位数。例如，若序列S1=(11,13,15,17,19)S_1=(11,13,15,17,19)S1=(11,13,15,17,19)，则S1S_1S1的中位数是151515，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4,6,8,20)S_2=(2,4,6,8,20)S2=(2,4,6,8,20)，则S1S_1S1和S2S_2S2的中位数是111111。现有两个等长升序序列AAA和BBB，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列AAA和BBB的中位数。要求：
- 给出算法的基本设计思想；
- 根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
- 说明你所设计算法的时间复杂度和空间复杂度；
解：
-
给出算法的基本设计思想；
算法基本设计思想：分别求两个升序序列A,BA,BA,B的中位数，设为aaa和bbb，求序列A、BA、BA、B中位数过程如下：
- 若a=ba=ba=b，则aaa或bbb即为所求中位数，算法结束；
- 若a
- 若a>ba>ba>b，则舍弃序列AAA中较大的一半，同时舍弃序列BBB中较小的一半，要求两次舍弃的长度相等；
在保留的两个升序序列中，重复过程①、②、③，直到两个序列中均只含一个元素时为止，较小者即为所求的中位数。
-
根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
使用C{\rm C}C语言描述算法如下：
int M_Search(int A[],int B[],int n){// 分别表示序列A、B的首位数，末位数和中位数int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;while(s1!=d1 || s2!=d2){m1=(s1+d1)/2;m2=(s2+d2)/2;// 满足条件①if(A[m1] == B[m2])return A[m1];// 满足条件②if(A[m1] -
说明你所设计算法的时间复杂度和空间复杂度；
算法的时间复杂度为O(log2n)O(\log_2n)O(log2n)，空间复杂度为O(1)O(1)O(1)。
-
已知一个整数序列A=(a0,a1,⋯,an−1)A=(a_0,a_1,\cdots,a_{n-1})A=(a0,a1,⋯,an−1)，其中0≤ai≤n(0≤i
- 给出算法的基本设计思想；
- 根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
- 说明你所设计算法的时间复杂度和空间复杂度；
解：
-
给出算法的基本设计思想；
算法基本设计思想：从前往后扫描数组元素，标记出一个可能成为主元素的元素Num{\rm Num}Num，然后重新计数，确认Num{\rm Num}Num是否是主元素。
算法步骤：
- 选取候选主元素。依次扫描所给数组的每个整数，将第一个遇到的整数Num{\rm Num}Num保存到ccc中，记录Num{\rm Num}Num出现次数为111；若遇到的下一个整数仍等于Num{\rm Num}Num，则计数加111，否则计数减111；当计数减到000时，将遇到的下一个整数保存到ccc中，计数重新记为111，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素；
- 判断ccc中元素是否是真正的主元素。再次扫描该数组，统计ccc中元素出现的次数，若大于n/2n/2n/2，则为主元素；否则，序列中不存在主元素。
-
根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
使用C{\rm C}C语言描述算法如下：
int Majority(int A[],int n){int i,c,count=1; // c用来保存候选主元素，count用来计数c=A[0]; // 设置A[0]为候选主元素// 查找候选主元素for(i=1;i -
说明你所设计算法的时间复杂度和空间复杂度；
实现程序的时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)。
-
给定一个含n(n≥1)n(n≥1)n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{−5,3,2,3}\{-5,3,2,3\}{−5,3,2,3}中未出现的最小正整数是111；数组{1,2,3}\{1,2,3\}{1,2,3}中未出现的最小正整数是444。要求：
- 给出算法的基本设计思想；
- 根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
- 说明你所设计算法的时间复杂度和空间复杂度；
解：
-
给出算法的基本设计思想；
算法的基本设计思想：分配一个用于标记的数组B[n]B[n]B[n]，用来记录AAA中是否出现了1～n1～n1～n中的正整数，B[0]B[0]B[0]对应正整数111，B[n−1]B[n-1]B[n−1]对应正整数nnn，初始化BBB中全部为000。由于AAA中含有nnn个整数，因此，可能返回的值是1～n+11～n+11～n+1，当AAA中nnn个数恰好为1～n1～n1～n时返回n+1n+1n+1。当数组AAA中出现了小于等于000或大于nnn的值时，会导致1～n1～n1～n中出现空余位置，返回结果必然在1～n1～n1～n中，因此，对于AAA中出现了小于等于000或大于nnn的值，可以不采取任何操作。
-
根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
使用C{\rm C}C语言描述算法如下：
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 -
说明你所设计算法的时间复杂度和空间复杂度；
时间复杂度为O(n)O(n)O(n)，空间复杂度为O(n)O(n)O(n)。
-
定义三元组(a,b,c)(a,b,c)(a,b,c)(a、b、ca、b、ca、b、c均为正数)的距离D=∣a−b∣+∣b−c∣+∣c−a∣D=|a-b|+|b-c|+|c-a|D=∣a−b∣+∣b−c∣+∣c−a∣。给定333个非空整数集合S1,S2,S3S_1,S_2,S_3S1,S2,S3，按升序分别存储在333个数组中。请设计一个在时间上尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)(a∈S1,b∈S2,c∈S3)(a,b,c)(a\in{S_1},b\in{S_2},c\in{S_3})(a,b,c)(a∈S1,b∈S2,c∈S3)中的最小距离。例如，S1={−1,0,9},S2={−25,−10,10,11},S_1=\{-1,0,9\},S_2=\{-25,-10,10,11\},S1={−1,0,9},S2={−25,−10,10,11},S3={2,9,17,30,41}S_3=\{2,9,17,30,41\}S3={2,9,17,30,41}，则最小距离为222，相应的三元组为(9,10,9)(9,10,9)(9,10,9)。要求：
- 给出算法的基本设计思想；
- 根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
- 说明你所设计算法的时间复杂度和空间复杂度；
解：
-
给出算法的基本设计思想；
算法基本设计思想：
- 使用Dmin{\rm D_{\min}}Dmin记录所有已处理的三元组的最小距离，初值为一个足够大的整数；
- 集合S1、S2、S3S_1、S_2、S_3S1、S2、S3分别保存在数组A、B、CA、B、CA、B、C中。数组的下标变量i=j=k=0i=j=k=0i=j=k=0，当i<∣S1∣、i<|S_1|、i<∣S1∣、j<∣S2∣j<|S_2|j<∣S2∣且k<∣S3∣k<|S_3|k<∣S3∣时(∣S∣|S|∣S∣表示集合SSS中的元素个数)，循环执行下面步骤：
- 计算(A[i],B[j],C[k])(A[i],B[j],C[k])(A[i],B[j],C[k])的距离DDD；
- 若D
- 将A[i]、B[j]、C[k]A[i]、B[j]、C[k]A[i]、B[j]、C[k]中的最小值的下标+1+1+1；
- 输出DminD_{\min}Dmin，结束。
-
根据设计思想，采用C{\rm C}C或C{\rm C}C++或Java{\rm Java}Java语言描述算法，关键之处给出注释；
使用C{\rm C}C语言描述算法如下：
#define INT_MAX 0x7fffffff// 计算绝对值 int abs_(int a){if(a<0)return -a;elsereturn a; }// a是否是三个数中的最小值 bool xls_min(int a,int b,int c){if(a<=b && a<=c)return true;return false; }int findMinofTrip(int A[],int n,int B[],int m,int C[],int p){// D_min用于记录三元组的最小距离int i=0,j=0,k=0,D_min=INT_MAX,D;while(i0){// 计算距离DD=abs_(A[i]-B[j])+abs_(B[j]-C[k])+abs_(C[k]-A[i]);// 更新距离Dif(D -
说明你所设计算法的时间复杂度和空间复杂度；
时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)。