1. 顺序表的初始化
### 1. 顺序表的初始化 静态分配和动态分配的顺序表在初始化时有所不同。静态分配：在声明顺序表时，数组空间已由编译器分配，因此初始化只需将当前长度置为 0。 动态分配：需在运行时为顺序表分配初始大小的数组空间，并设置长度和容量。其中，MaxSize 表示当前分配的存储空间上限。当插入元素导致空间不足时，需要扩容。 ## 2. 插入操作 在顺序表 L 的第 i（ $1 \leqslant i \leqslant L.\text{length} + 1$ ）个位置插入新元素 e。若 i 超出合法范围，或存储空间已满，则插入失败，返回 false；否则，将第 i 个元素及其后的所有元素依次后移一位，腾出一个空位置插入 e，表长加 1，返回 true。void InitList(SeqList &amp;L) { L.data=(ElemType *)malloc(InitSize*sizeof(ElemType)); //分配存储空间 } <!-- page: 29 --> 第2章 线性表 17 ```txt L.length=0; //顺序表初始长度为0 L.MaxSize=InitSize; //初始存储容量 }## 注意 区分位序（从 1 开始）与数组下标（从 0 开始）。为什么判断插入位置时使用 length+1，而移动元素的 for 循环中使用 length？因为合法插入位置包括第 n+1 位，但移动元素时最多从第 n 位开始后移。 最好情况：在表尾插入（ $i = n + 1$ ），无须移动元素，时间复杂度为 $O(1)$ 。 最坏情况：在表头插入（ $i = 1$ ），需移动全部 $n$ 个元素，时间复杂度为 $O(n)$ 。 平均情况：设在第 $i$ 个位置插入的概率为 $p_i = 1 / (n + 1)$ ，则平均移动次数为 $$ \sum_{i = 1}^{n + 1} p_i (n - i + 1) = \sum_{i = 1}^{n + 1} \frac{1}{n + 1} (n - i + 1) = \frac{1}{n + 1} \sum_{i = 1}^{n + 1} (n - i + 1) = \frac{1}{n + 1} \frac{n(n + 1)}{2} = \frac{n}{2} $$ 因此，插入操作的平均时间复杂度为 $O(n)$ 。 ## 3. 删除操作 删除顺序表L中第i（ $1 \leqslant i \leqslant L.\text{length}$ ）个位置的元素，并通过引用参数e返回其值。若i非法，返回false；否则，保存被删元素，将其后所有元素前移一位，表长减1，返回true。 最好情况：删除表尾元素（ $i = n$ ），无须移动元素，时间复杂度为 $O(1)$ 。 最坏情况：删除表头元素（ $i = 1$ ），需移动其余 $n - 1$ 个元素，时间复杂度为 $O(n)$ 。 平均情况：设删除第 $i$ 个元素的概率为 $p_i = 1 / n$ ，则平均移动次数为 $$ \sum_{i = 1}^{n} p_i (n - i) = \sum_{i = 1}^{n} \frac{1}{n} (n - i) = \frac{1}{n} \sum_{i = 1}^{n} (n - i) = \frac{1}{n} \frac{n(n - 1)}{2} = \frac{n - 1}{2} $$ <!-- page: 30 --> 2027年数据结构考研复习指导 因此，删除操作的平均时间复杂度为 $O(n)$。 可见，顺序表的插入和删除操作的时间开销主要耗费在移动元素上，而移动元素的个数取决于操作位置。图2.2显示了顺序表插入和删除操作前、后的状态，以及数据元素在存储空间中的位置和表长变化。图2.2(a)将第 $4\sim 7$ 个元素从后往前依次后移一位，为新元素腾出位置。图2.2(b)将第 $5\sim 7$ 个元素从前往后依次前移一位，填补删除后的空缺。bool ListInsert(SqList &amp;L,int i,ElemType e) { if (i&lt;1||i&gt;L.length+1) //判断 i 的范围是否有效 return false; if (L.length&gt;=MaxSize) //当前存储空间已满 return false; for (int j=L.length;j&gt;=i;j--) //将第 i 个元素及之后的元素后移 L.data[j]=L.data[j-1]; L.data[i-1]=e; //在位置 i 插入 e（注意下标转换） L.length++; //表长加 1 return true; }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 插入新元素示例 图2.2 顺序表的插入和删除
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 删除表中元素示例
## 4. 按值查找（顺序查找）
在顺序表L中查找第一个值等于e的元素，返回其位序；若未找到，则返回0。
```c
int LocateElem(SqList L,ElemType e) {
int i;
for (i=0; i<l.length;i++) #="" $="" $i$="" $i+1$="" $o(n)$。="" $o(n)$。="" $p_i="1" $p_i$，="" $u$="" (i="1)" (l.data[i]="e)" 1="" 1.="" 2.2.3="" 4.="" 5.="" 6)="" 7)="" :="" \="" \ldots$="" \mid="" \mid$="" \mid$="" \times="" \to="" ]="" ]<sup="" \mid="" \mid$="" \mid$，="" \mid$。="" \mid$="" \tag="" \tag{1="" \tag{1}$="" \tag{1}$。="" \tag{1}$。="" \tag{1}$。="" \tag{1}$。="" \tag{1}$。="" \tag{1}$。="" \tag{1}$。="" \tag{1}$。="" \tag{1}]="" \tag{1}]="" \tag{1}]="" \tag{1}]="" \tag{1}]="" \tag{1}]="" |="" |="" |)="" |)$="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |)$。="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |="" |
<!-- page: 31 -->
第2章 线性表
19
A. 查找值为 $x$ 的元素的时间与顺序表中元素个数 $n$ 无关
B. 查找值为 $x$ 的元素的时间与顺序表中元素个数 $n$ 有关
C. 查找序号为 $i$ 的元素的时间与顺序表中元素个数 $n$ 无关
D. 查找序号为 $i$ 的元素的时间与顺序表中元素个数 $n$ 有关
04. 一个顺序表所占用的存储空间大小与（）无关。
A. 表的长度
B. 元素的存放顺序
C. 元素的类型
D. 元素中各字段的类型
05. 若线性表最常用的操作是存取第 $i$ 个元素及其前驱和后继元素的值，为了提高效率，应采用（）的存储方式。
A. 单链表
B. 双链表
C. 循环单链表
D. 顺序表
06. 一个线性表最常用的操作是存取任意一个指定序号的元素并在最后进行插入、删除操作，则利用（）存储方式可以节省时间。
A. 顺序表
B. 双链表
C. 带头结点的循环双链表
D. 循环单链表
07. 在 $n$ 个元素的线性表的数组表示中，时间复杂度为 $O(1)$ 的操作是（）。
I. 访问第 $i$ （$1 \leqslant i \leqslant n$）个结点和求第 $i$ （$2 \leqslant i \leqslant n$）个结点的直接前驱
II. 在最后一个结点后插入一个新的结点
III. 删除第 1 个结点
IV. 在第 $i$ （$1 \leqslant i \leqslant n$）个结点后插入一个结点
A. I
B. II、III
C. I、II
D. I、II、III
08. 设线性表有 $n$ 个元素，严格说来，以下操作中，（）在顺序表上实现要比在链表上实现的效率高。
I. 输出第 $i$ （$1 \leqslant i \leqslant n$）个元素值
II. 交换第 3 个元素与第 4 个元素的值
III. 顺序输出这 $n$ 个元素的值
A. I
B. I、III
C. I、II
D. II、III
09. 在一个长度为 $n$ 的顺序表中删除第 $i$ （$1 \leqslant i \leqslant n$）个元素时，需向前移动（）个元素。
A. $n$
B. $i - 1$
C. $n - i$
D. $n - i + 1$
10. 对于顺序表，访问第 $i$ 个位置的元素和在第 $i$ 个位置插入一个元素的时间复杂度为（）。
A. $O(n), O(n)$
B. $O(n), O(1)$
C. $O(1), O(n)$
D. $O(1), O(1)$
11. 对于顺序存储的线性表，其算法时间复杂度为 $O(1)$ 的运算应该是（）。
A. 将 $n$ 个元素从小到大排序
B. 删除第 $i$ （$1 \leqslant i \leqslant n$）个元素
C. 改变第 $i$ （$1 \leqslant i \leqslant n$）个元素的值
D. 在第 $i$ （$1 \leqslant i \leqslant n$）个元素后插入一个新元素
12. 顺序表的插入算法中，当 $n$ 个空间已满时，可再申请增加分配 $m$ 个空间，若申请失败，则说明系统没有（）可分配的存储空间。
A. $m$ 个
B. $m$ 个连续
C. $n + m$ 个
D. $n + m$ 个连续
13. 【2023 统考真题】在下列对顺序存储的有序表（长度为 $n$）实现给定操作的算法中，平均时间复杂度为 $O(1)$ 的是（）。
<!-- page: 32 -->
2027年数据结构考研复习指导
A. 查找包含指定值元素的算法
B. 插入包含指定值元素的算法
C. 删除第 $i$（$1 \leqslant i \leqslant n$）个元素的算法
D. 获取第 $i$（$1 \leqslant i \leqslant n$）个元素的算法
## 二、综合应用题
01. 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
02. 设计一个高效算法，将顺序表 $L$ 的所有元素逆置，要求算法的空间复杂度为 $O(1)$。
03. 对长度为 $n$ 的顺序表 $L$，编写一个时间复杂度为 $O(n)$、空间复杂度为 $O(1)$ 的算法，该算法删除顺序表中所有值为 $x$ 的数据元素。
04. 从顺序表中删除其值在给定值 $s$ 和 $t$ 之间（包含 $s$ 和 $t$，要求 $s < t$）的所有元素，若 $s$ 或 $t$ 不合理或顺序表为空，则显示出错信息并退出运行。
05. 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
06. 将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
07. 已知在一维数组 $A[m + n]$ 中依次存放两个线性表 $(a_{1}, a_{2}, a_{3}, \dots, a_{m})$ 和 $(b_{1}, b_{2}, b_{3}, \dots, b_{n})$。编写一个函数，将数组中两个顺序表的位置互换，即将 $(b_{1}, b_{2}, b_{3}, \dots, b_{n})$ 放在 $(a_{1}, a_{2}, a_{3}, \dots, a_{m})$ 的前面。
08. 线性表 $(a_{1}, a_{2}, a_{3}, \dots, a_{n})$ 中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为 $x$ 的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍然递增有序。
09. 给定三个序列 $A$、$B$、$C$，长度均为 $n$，且均为无重复元素的递增序列，请设计一个时间上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。例如，数组 A 为 $\{1,2,3\}$，数组 B 为 $\{2,3,4\}$，数组 C 为 $\{-1,0,2\}$，则输出 2。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
3）说明你的算法的时间复杂度和空间复杂度。
10. 【2010 统考真题】设将 $n$（$n > 1$）个整数存放到一维数组 R 中。设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移 $p$（$0 < p < n$）个位置，即将 R 中的数据由 $(X_0, X_1, \dots, X_{n-1})$ 变换为 $(X_p, X_{p+1}, \dots, X_{n-1}, X_0, X_1, \dots, X_{p-1})$。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
11. 【2011 统考真题】一个长度为 $L$（$L \geqslant 1$）的升序序列 $S$，处在第 $[L/2]$ 个位置的数称为 $S$ 的中位数。例如，若序列 $S_1 = (11, 13, 15, 17, 19)$，则 $S_1$ 的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 $S_2 = (2, 4, 6, 8, 20)$，则 $S_1$ 和 $S_2$ 的中位数是 11。现在有两个等长升序序列 $A$ 和 $B$，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 $A$ 和 $B$ 的中位数。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
12. 【2013 统考真题】已知一个整数序列 $A = (a_{0}, a_{1}, \dots, a_{n-1})$，其中 $0 \leqslant a_{i} < n$（$0 \leqslant i < n$）。若存在 $a_{p_{1}} = a_{p_{2}} = \dots = a_{p_{m}} = x$ 且 $m > n/2$（$0 \leqslant p_{k} < n, 1 \leqslant k \leqslant 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$ 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，
<!-- page: 33 -->
第2章 线性表
21
找出 $A$ 的主元素。若存在主元素，则输出该元素；否则输出-1。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 $\mathrm{C}++$ 或 Java 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
13. 【2018 统考真题】给定一个含 $n (n \geqslant 1)$ 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组 $\{-5, 3, 2, 3\}$ 中未出现的最小正整数是 1；数组 $\{1, 2, 3\}$ 中未出现的最小正整数是 4。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
14.【2020 统考真题】定义三元组 $(a, b, c) (a, b, c$ 均为整数) 的距离 $D = |a - b| + |b - c| + |c - a|$ 。给定 3 个非空整数集合 $S_{1}, S_{2}$ 和 $S_{3}$ ，按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a, b, c) (a \in S_{1}, b \in S_{2}, c \in S_{3})$ 中的最小距离。例如 $S_{1} = \{-1, 0, 9\}, S_{2} = \{-25, -10, 10, 11\}, S_{3} = \{2, 9, 17, 30, 41\}$ ，则最小距离为 2，相应的三元组为 $(9, 10, 9)$ 。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 语言或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
15. 【2025统考真题】有两个长度均为 $n$ 的一维整型数组A和res，对数组A中的每个元素 $\mathrm{A}[i]$ ，计算 $\mathrm{A}[i]$ 与 $\mathrm{A}[j] (0 \leqslant i \leqslant j \leqslant n - 1)$ 乘积的最大值，并将其保存到 $\mathrm{res}[i]$ 中。例如，当 $\mathrm{A}[] = \{1, 4, -9, 6\}$ 时，得到 $\mathrm{res}[] = \{6, 24, 81, 36\}$。现给定数组A，设计一个时间和空间上尽可能高效的算法calMulMax，求res中各元素的值。函数原型为void calMulMax(int A[], int res[], int n)。要求如下：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
## 2.2.4 答案与解析
### 一、单项选择题
#### 01. A
顺序表不像链表那样要在结点中存放指针域，因此存储密度大，选项 A 正确。选项 B 和 C 是链表的优点。选项 D 是错误的，比如对于树形结构，顺序表显然不如链表表示起来方便。
#### 02. C
顺序表是顺序存储的线性表，表中所有元素的类型必须相同，且必须连续存放。一维数组中的元素可以不连续存放；此外，栈、队列和树等逻辑结构也可利用一维数组表示，但它与顺序表不属于相同的逻辑结构。在顺序表中，逻辑上相邻的元素物理位置上也相邻。