#### 03. C
随机存取是指在 $O(1)$ 的时间访问下标为 $i$ 的元素，所需时间与顺序表中的元素个数 $n$ 无关。
#### 04. B
顺序表所占的存储空间 = 表长×sizeof（元素的类型），表长和元素的类型显然会影响存储空间的大小。若元素为结构体类型，则元素中各字段的类型也会影响存储空间的大小。
<!-- page: 34 -->
2027年数据结构考研复习指导
05. D
题干实际要求能最快存取第 $i - 1$ 、 $i$ 和 $i + 1$ 个元素值。选项 A、B、C 都只能从头结点依次顺序查找，时间复杂度为 $O(n)$；只有顺序表可以按序号随机存取，时间复杂度为 $O(1)$。
06. A
只有顺序表可以按序号随机存取，且在最后进行插入和删除操作时不需要移动任何元素。
07. C
对说法 I，解析略；对说法 II，在最后位置插入新结点不需要移动元素，时间复杂度为 $O(1)$；对说法 III，被删结点后的结点需要依次前移，时间复杂度为 $O(n)$；对说法 IV，需要后移 $n - i$ 个结点，时间复杂度为 $O(n)$。
08. C
对说法 II，顺序表只需 3 次交换操作；链表需要分别找到两个结点前驱，第 4 个结点断链后再插入到第 2 个结点后，效率较低。对说法 III，需要依次顺序访问每个元素，时间复杂度相同。
09. C
需要将元素 $a_{i+1} \sim a_n$ 依次前移一位，共移动 $n - (i + 1) + 1 = n - i$ 个元素。
10. C
在第 $i$ 个位置插入一个元素，需要移动 $n - i + 1$ 个元素，时间复杂度为 $O(n)$。
11. C
对 $n$ 个元素进行排序的时间复杂度最小也要 $O(n)$（初始有序时），通常为 $O(n \log_2 n)$ 或 $O(n^2)$，通过第 8 章学习后会更容易理解。选项 B 和 D 显然错误。顺序表支持按序号的随机存取方式。
12. D
顺序存储需要连续的存储空间，在申请时需申请 $n + m$ 个连续的存储空间，然后将线性表原来的 $n$ 个元素复制到新申请的 $n + m$ 个连续的存储空间的前 $n$ 个单元。
13. D
对于顺序存储的有序表，查找指定值元素可以采用顺序查找法或折半查找法，平均时间复杂度最少为 $O(\log_2 n)$。插入指定值元素需要先找到插入位置，然后将该位置及之后的元素依次后移一个位置，最后将指定值元素插入到该位置，平均时间复杂度为 $O(n)$。删除第 $i$ 个元素需要将该元素之后的全部元素依次前移一个位置，平均时间复杂度为 $O(n)$。获取第 $i$ 个元素只需直接根据下标读取对应的数组元素即可，时间复杂度为 $O(1)$。
## 二、综合应用题
### 01. 【解答】
算法思想：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置。
本题代码如下：
boolDel_Min(SqList&amp;L,ElemType&amp;value){//删除顺序表 L 中最小值元素结点，并通过引用型参数 value 返回其值//若删除成功，则返回 true；否则返回 falseif(L.length==0)returnfalse;//表空，中止操作返回value=L.data[0];intpos=0;//假定 0 号元素的值最小for(inti=1;i&lt;L.length;i++)//循环，寻找具有最小值的元素if(L.data[i]&lt;value){//让 value 记忆当前具有最小值的元素value=L.data[i];<!--page:35-->第2章线性表23```txtpos=i;}L.data[pos]=L.data[L.length-1];//空出的位置由最后一个元素填补L.length--;returntrue;//此时，value 为最小值}
void del_x_1(SqList &amp;L,ElemType x) {
//本算法实现删除顺序表 L 中所有值为 x 的数据元素
int k=0,i; //记录值不等于 x 的元素个数
for (i=0; i&lt;L.length; i++)
if (L.data[i]!=x) {
L.data[k]=L.data[i];
k++; //不等于 x 的元素增 1
}
L.length=k; //顺序表 L 的长度等于 k
}
void del_x_2(SqList &amp;L,ElemType x) {
int k=0, i=0; //k 记录值等于 x 的元素个数
while (i&lt;L.length) {
if (L.data[i]==x)
k++;
else
L.data[i-k]=L.data[i]; //当前元素前移 k 个位置
i++;
}
L.length=L.length-k; //顺序表 L 的长度递减
}
boolDel_s_t(SqList&amp;L,ElemTypes,ElemTypet){//删除顺序表 L 中值在给定值 s 和 t（要求 s<t）之间的所有元素 int="" i,k="0;" if(l.length="0||s" {="">=t)returnfalse;//线性表为空或 s、t 不合法，返回for(i=0;i<l.length;i++)(i="0;"(l.data[i]=""<table=""else=""i++)=""i<=""i,j=""i,j;=""i<l.length="k;"i<="t)"if(l.data[i]="L.data[i];"l.length="k;"l.data[i-k]="L.data[i];"{="">=s&amp;&amp;L.data[i]&lt;=t)//当前元素前移 k 个位置}
voidSearchExchangeInsert(ElemTypeA[],ElemTypex){intlow=0,high=n-1,mid;//low 和 high 指向顺序表下界和上界的下标while(low&lt;=high){<!--page:38-->2027年数据结构考研复习指导```cmid=(low+high)/2;//找中间位置if(A[mid]==x)break;//找到x，退出while循环elseif(A[mid]<x)(a[mid="1;"(low="mid+1);"(low=mid+1);=""子)=""子)=""else=""high="mid-1;"high)=""if(a[mid]="x&amp;&amp;mid!=n-1)"if(inv=""min)=""q)=""q):=""{=""}=""}="">high;i--)A[i+1]=A[i];//后移元素A[i+1]=x;//插入x}//结束插入
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)$。
## 11. 【解答】
1）算法的基本设计思想如下。
分别求两个升序序列 $A$、$B$ 的中位数，设为 $a$ 和 $b$，求序列 $A$、$B$ 的中位数过程如下：
① 若 $a = b$，则 $a$ 或 $b$ 为所求中位数，算法结束。
② 若 $a < b$，则舍弃序列 $A$ 中较小的一半，同时舍弃序列 $B$ 中较大的一半，要求两次舍弃的长度相等。
③ 若 $a > b$，则舍弃序列 $A$ 中较大的一半，同时舍弃序列 $B$ 中较小的一半，要求两次舍弃的长度相等。
在保留的两个升序序列中，重复过程①、②、③，直到两个序列中均只含一个元素时为止，较小者为所求的中位数。
2）本题代码如下：
intM_Search(intA[],intB[],intn){ints1,d1,m1,s2,d2,m2;s1=0;d1=n-1;s2=0;d2=n-1;while(s1!=d1||s2!=d2){m1=(s1+d1)/2;m2=(s2+d2)/2;if(A[m1]==B[m2])returnA[m1];//满足条件①if(A[m1]&lt;B[m2]){//满足条件②if((s1+d1)%2==0){//若元素个数为奇数s1=m1;//舍弃 A 中间点以前的部分，且保留中间点d2=m2;//舍弃 B 中间点以后的部分，且保留中间点}else{//元素个数为偶数s1=m1+1;//舍弃 A 的前半部分d2=m2;//舍弃 B 的后半部分}}else{//满足条件③if((s1+d1)%2==0){//若元素个数为奇数d1=m1;//舍弃 A 中间点以后的部分，且保留中间点s2=m2;//舍弃 B 中间点以前的部分，且保留中间点}else{//元素个数为偶数d1=m1;//舍弃 A 的后半部分s2=m2+1;//舍弃 B 的前半部分