2.2 线性表的顺序表示·习题

教材导航 · 返回本节知识

复习入口

2.2 线性表的顺序表示 · 2.2.1 顺序表的定义 · 2.2.2 顺序表上基本操作的实现

本节共29题:选择题15题,综合应用题14题。每题答案紧接题目折叠显示。

文字转录进度:29/29题。已转录题目的题干、选项和解析可编辑;示意图按需保留。

单项选择题

单项选择题 01

原书题目P17 · 解析P20 · 目视转录

下列叙述中,( )是顺序存储结构的优点。

A. 存储密度大

B. 插入运算方便

C. 删除运算方便

D. 方便地适用于各种逻辑结构的存储表示

查看答案与解析

答案:A。

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

单项选择题 02

原书题目P18 · 解析P20 · 目视转录

下列关于顺序表的叙述中,正确的是( )。

A. 顺序表可以利用一维数组表示,因此顺序表与一维数组在逻辑结构上是相同的

B. 在顺序表中,逻辑上相邻的元素物理位置上不一定相邻

C. 顺序表和一维数组一样,都可以进行随机存取

D. 在顺序表中,每个元素的类型不必相同

查看答案与解析

答案:C。

顺序表是顺序存储的线性表,表中所有元素的类型必须相同,且必须连续存放。一维数组中的元素可以不连续存放;此外,栈、队列和树等逻辑结构也可利用一维数组表示,但它与顺序表不属于相同的逻辑结构。在顺序表中,逻辑上相邻的元素物理位置上也相邻。

单项选择题 03

原书题目P18 · 解析P20 · 目视转录

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

A. 随机存取的存储结构

B. 顺序存取的存储结构

C. 索引存取的存储结构

D. 散列存取的存储结构

查看答案与解析

答案:A。

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

单项选择题 04

原书题目P18 · 解析P21 · 目视转录

通常说顺序表具有随机存取的特性,指的是( )。

A. 查找值为 xx 的元素的时间与顺序表中元素个数 nn 无关

B. 查找值为 xx 的元素的时间与顺序表中元素个数 nn 有关

C. 查找序号为 ii 的元素的时间与顺序表中元素个数 nn 无关

D. 查找序号为 ii 的元素的时间与顺序表中元素个数 nn 有关

查看答案与解析

答案:C。

随机存取是指在 O(1)O(1) 的时间访问下标为 ii 的元素,所需时间与顺序表中的元素个数 nn 无关。

单项选择题 05

原书题目P18 · 解析P21 · 目视转录

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

A. 表的长度

B. 元素的存放顺序

C. 元素的类型

D. 元素中各字段的类型

查看答案与解析

答案:B。

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

单项选择题 06

原书题目P18 · 解析P21 · 目视转录

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

A. 单链表

B. 双链表

C. 循环单链表

D. 顺序表

查看答案与解析

答案:D。

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

单项选择题 07

原书题目P18 · 解析P21 · 目视转录

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

A. 顺序表

B. 双链表

C. 带头结点的循环双链表

D. 循环单链表

查看答案与解析

答案:A。

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

单项选择题 08

原书题目P18 · 解析P21 · 目视转录

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

Ⅰ. 访问第 ii(1≤i≤n1\le i\le n)个结点和求第 ii(2≤i≤n2\le i\le n)个结点的直接前驱

Ⅱ. 在最后一个结点后插入一个新的结点

Ⅲ. 删除第 1 个结点

Ⅳ. 在第 ii(1≤i≤n1\le i\le n)个结点后插入一个结点

A. Ⅰ

B. Ⅱ、Ⅲ

C. Ⅰ、Ⅱ

D. Ⅰ、Ⅱ、Ⅲ

查看答案与解析

答案:C。

对于Ⅰ,解析略;对于Ⅱ,在最后位置插入新结点不需要移动元素,时间复杂度为 O(1)O(1);对于Ⅲ,被删结点后的结点需要依次前移,时间复杂度为 O(n)O(n);对于Ⅳ,需后移 n−in-i 个结点,时间复杂度为 O(n)O(n)。

单项选择题 09

原书题目P18 · 解析P21 · 目视转录

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

Ⅰ. 输出第 ii(1≤i≤n1\le i\le n)个元素值

Ⅱ. 交换第 3 个元素与第 4 个元素的值

Ⅲ. 顺序输出这 nn 个元素的值

A. Ⅰ

B. Ⅰ、Ⅲ

C. Ⅰ、Ⅱ

D. Ⅱ、Ⅲ

查看答案与解析

答案:C。

对于Ⅱ,顺序表只需要 3 次交换操作;链表则需要分别找到两个结点前驱,第 4 个结点断链后再插入到第 2 个结点后,效率较低。对于Ⅲ,需依次顺序访问每个元素,时间复杂度相同。

单项选择题 10

原书题目P18 · 解析P21 · 目视转录

在一个长度为 nn 的顺序表中删除第 ii(1≤i≤n1\le i\le n)个元素时,需向前移动( )个元素。

A. nn

B. i−1i-1

C. n−in-i

D. n−i+1n-i+1

查看答案与解析

答案:C。

需要将元素 ai+1∼ana_{i+1}\sim a_n 依次前移一位,共移动 n−(i+1)+1=n−in-(i+1)+1=n-i 个元素。

单项选择题 11

原书题目P18 · 解析P21 · 目视转录

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

A. O(n)O(n)、O(n)O(n)

B. O(n)O(n)、O(1)O(1)

C. O(1)O(1)、O(n)O(n)

D. O(1)O(1)、O(1)O(1)

查看答案与解析

答案:C。

在第 ii 个位置插入一个元素,需要移动 n−i+1n-i+1 个元素,时间复杂度为 O(n)O(n)。

单项选择题 12

原书题目P18 · 解析P21 · 目视转录

对于顺序存储的线性表,其算法时间复杂度为 O(1)O(1) 的运算应该是( )。

A. 将 nn 个元素从小到大排序

B. 删除第 ii(1≤i≤n1\le i\le n)个元素

C. 改变第 ii(1≤i≤n1\le i\le n)个元素的值

D. 在第 ii(1≤i≤n1\le i\le n)个元素后插入一个新元素

查看答案与解析

答案:C。

对 nn 个元素进行排序的时间复杂度最小也要 O(n)O(n)(初始有序时),通常为 O(nlog⁡2n)O(n\log_2 n) 或 O(n2)O(n^2),通过第 8 章学习后会更理解。选项 B 和 D 显然错误。顺序表支持按序号的随机存取方式。

单项选择题 13

原书题目P19 · 解析P21 · 目视转录

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

A. 1≤i≤n1\le i\le n

B. 1≤i≤n+11\le i\le n+1

C. 0≤i≤n−10\le i\le n-1

D. 0≤i≤n0\le i\le n

查看答案与解析

答案:B。

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

单项选择题 14

原书题目P19 · 解析P21 · 目视转录

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

A. mm 个

B. mm 个连续

C. n+mn+m 个

D. n+mn+m 个连续

查看答案与解析

答案:D。

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

单项选择题 15

原书题目P19 · 解析P21 · 目视转录

【2023 统考真题】在下列对顺序存储的有序表(长度为 nn)实现给定操作的算法中,平均时间复杂度为 O(1)O(1) 的是( )。

A. 查找包含指定值元素的算法

B. 插入包含指定值元素的算法

C. 删除第 ii(1≤i≤n−11\le i\le n-1)个元素的算法

D. 获取第 ii(1≤i≤n1\le i\le n)个元素的算法

查看答案与解析

答案:D。

对于顺序存储的有序表,查找指定值元素可以采用顺序查找法或折半查找法,平均时间复杂度最少为 O(log⁡2n)O(\log_2 n)。插入指定值元素需要先找到插入位置,然后将该位置及之后的元素依次后移一个位置,最后将指定值元素插入到该位置,平均时间复杂度为 O(n)O(n)。删除第 ii 个元素需要将该元素之后的全部元素依次前移一个位置,平均时间复杂度为 O(n)O(n)。获取第 ii 个元素只需直接根据下标获取对应的数组元素即可,时间复杂度为 O(1)O(1)。

综合应用题

综合应用题 01

原书题目P19 · 解析P21 · 目视转录

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

查看答案与解析

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

本题代码如下:

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为最小值
}

注意:本题也可用函数返回值返回,两者的区别是:函数返回值只能返回一个值,而参数返回(引用传参)可以返回多个值。

综合应用题 02

原书题目P19 · 解析P22 · 目视转录

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

查看答案与解析

算法思想:扫描顺序表 LL 的前半部分元素,对于元素 L.data[i](0≤i<L.length/20\le i<\mathrm{L.length}/2),将其与后半部分的对应元素 L.data[L.length-i-1] 进行交换。

本题代码如下:

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

综合应用题 03

原书题目P19 · 解析P22 · 目视转录

对长度为 nn 的顺序表 LL,编写一个时间复杂度为 O(n)O(n)、空间复杂度为 O(1)O(1) 的算法,该算法删除顺序表中所有值为 xx 的数据元素。

查看答案与解析

解法 1:用 kk 记录顺序表 LL 中不等于 xx 的元素个数(需要保存的元素个数),扫描时将不等于 xx 的元素移动到下标 kk 的位置,并更新 kk 值。扫描结束后修改 LL 的长度。

void del_x_1(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:用 kk 记录顺序表 LL 中等于 xx 的元素个数,一边扫描 LL,一边统计 kk,并将不等于 xx 的元素前移 kk 个位置。扫描结束后修改 LL 的长度。

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=ni=1,j=n),从两端向中间移动,在遇到最左端值为 xx 的元素时,直接将最右端值非 xx 的元素左移至值为 xx 的数据元素位置,直到两指针相遇。但这种方法会改变原表中元素的相对位置。

综合应用题 04

原书题目P19 · 解析P23 · 目视转录

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

查看答案与解析

算法思想:从前向后扫描顺序表 LL,用 kk 记录值在 ss 和 tt 之间的元素个数(初始时 k=0k=0)。对于当前扫描的元素,若其值不在 ss 和 tt 之间,则前移 kk 个位置;否则执行 k++。每个不在 ss 和 tt 之间的元素仅移动一次,因此算法效率高。

bool Del_s_t(SqList &L,ElemType 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个位置
    }                                 // for
    L.length-=k;                      // 长度减小
    return true;
}

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

综合应用题 05

原书题目P19 · 解析P23 · 目视转录

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

查看答案与解析

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

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.data[i]!=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 来手动模拟算法的执行过程,在模拟过程中要标注 ii 和 jj 所指示的元素。

思考:若将本题中的有序表改为无序表,你能想到时间复杂度为 O(n)O(n) 的方法吗?(提示:使用散列表。)

综合应用题 06

原书题目P19 · 解析P24 · 目视转录

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

查看答案与解析

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

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;
}

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

综合应用题 07

原书题目P19 · 解析P24 · 目视转录

已知在一维数组 A[m+n]A[m+n] 中依次存放两个线性表 (a1,a2,a3,⋯ ,am)(a_1,a_2,a_3,\cdots,a_m) 和 (b1,b2,b3,⋯ ,bn)(b_1,b_2,b_3,\cdots,b_n)。编写一个函数,将数组中两个顺序表的位置互换,即将 (b1,b2,b3,⋯ ,bn)(b_1,b_2,b_3,\cdots,b_n) 放在 (a1,a2,a3,⋯ ,am)(a_1,a_2,a_3,\cdots,a_m) 的前面。

查看答案与解析

算法思想:首先将数组 A[m+n]A[m+n] 中的全部元素 (a1,a2,⋯ ,am,b1,b2,⋯ ,bn)(a_1,a_2,\cdots,a_m,b_1,b_2,\cdots,b_n) 原地逆置为 (bn,bn−1,⋯ ,b1,am,am−1,⋯ ,a1)(b_n,b_{n-1},\cdots,b_1,a_m,a_{m-1},\cdots,a_1),然后对前 nn 个元素和后 mm 个元素分别使用逆置算法,即可得到 (b1,b2,⋯ ,bn,a1,a2,⋯ ,am)(b_1,b_2,\cdots,b_n,a_1,a_2,\cdots,a_m),从而实现顺序表的位置互换。

typedef int DataType;
void Reverse(DataType A[],int left,int right,int arraySize){
    // 逆转(a_left,a_left+1,...,a_right)为(a_right,a_right-1,...,a_left)
    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){
    /* 数组A[m+n]中,从0到m-1存放顺序表(a1,a2,...,am),
       从m到m+n-1存放顺序表(b1,b2,...,bn),算法将这两个表的位置互换 */
    Reverse(A,0,m+n-1,arraySize);
    Reverse(A,0,n-1,arraySize);
    Reverse(A,n,m+n-1,arraySize);
}

综合应用题 08

原书题目P19 · 解析P25 · 目视转录

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

查看答案与解析

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

void SearchExchangeInsert(ElemType A[],ElemType x){
    int low=0,high=n-1,mid;            // low和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+1]; A[mid+1]=t;
    }
    if(low>high){                     // 查找失败,插入数据元素x
        for(i=n-1;i>high;i--) A[i+1]=A[i]; // 后移元素
        A[i+1]=x;                     // 插入x
    }                                 // 结束插入
}

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

综合应用题 09

原书题目P19 · 解析P25 · 目视转录

给定三个序列 AA、BB、CC,长度均为 nn,且均为无重复元素的递增序列,请设计一个时间上尽可能高效的算法,逐行输出同时存在于这三个序列中的所有元素。例如,数组 AA 为 {1,2,3}\{1,2,3\},数组 BB 为 {2,3,4}\{2,3,4\},数组 CC 为 {−1,0,2}\{-1,0,2\},则输出 2。要求:

  1. 给出算法的基本设计思想。
  2. 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。
  3. 说明你的算法的时间复杂度和空间复杂度。
查看答案与解析

1)算法的基本设计思想。

使用三个下标变量从小到大遍历数组。当三个下标变量指向的元素相等时,输出并向前推进指针,否则仅移动小于最大元素的下标变量,直到某个下标变量移出数组范围时,即可停止。

2)算法的实现。

void samekey(int A[],int B[],int C[],int n){
    int i=0,j=0,k=0;                  // 定义三个工作指针
    while(i<n&&j<n&&k<n){             // 相同则输出,并集体后移
        if(A[i]==B[j]&&B[j]==C[k]){
            printf("%d\n",A[i]);
            i++;j++;k++;
        }else{
            int maxNum=max(A[i],max(B[j],C[k]));
            if(A[i]<maxNum)i++;
            if(B[j]<maxNum)j++;
            if(C[k]<maxNum)k++;
        }
    }
}

3)每个指针移动的次数不超过 nn 次,且每次循环至少有一个指针后移,所以时间复杂度为 O(n)O(n),算法只用到了常数个变量,空间复杂度为 O(1)O(1)。

综合应用题 10

原书题目P19 · 解析P25 · 目视转录

【2010 统考真题】设将 nn(n>1n>1)个整数存放到一维数组 RR 中。设计一个在时间和空间两方面都尽可能高效的算法。将 RR 中保存的序列循环左移 pp(0<p<n0<p<n)个位置,即将 RR 中的数据由 (X0,X1,⋯ ,Xn−1)(X_0,X_1,\cdots,X_{n-1}) 变换为 (Xp,Xp+1,⋯ ,Xn−1,X0,X1,⋯ ,Xp−1)(X_p,X_{p+1},\cdots,X_{n-1},X_0,X_1,\cdots,X_{p-1})。要求:

  1. 给出算法的基本设计思想。
  2. 根据设计思想,采用 C 或 C++ 或 Java 语言描述算法,关键之处给出注释。
  3. 说明你所设计算法的时间复杂度和空间复杂度。
查看答案与解析

1)算法的基本设计思想。

可将问题视为把数组 abab 转换成数组 baba(aa 代表数组的前 pp 个元素,bb 代表数组中余下的 n−pn-p 个元素),先将 aa 逆置得到 a−1ba^{-1}b,再将 bb 逆置得到 a−1b−1a^{-1}b^{-1},最后将整个 a−1b−1a^{-1}b^{-1} 逆置得到 (a−1b−1)−1=ba(a^{-1}b^{-1})^{-1}=ba。设 Reverse 函数执行将数组逆置的操作,对 abcdefgh 向左循环移动 3(p=3p=3)个位置的过程如下:

  • Reverse(0,p-1) 得到 cbadefgh;
  • Reverse(p,n-1) 得到 cbahgfed;
  • Reverse(0,n-1) 得到 defghabc。

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

2)使用 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);
}

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

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

综合应用题 11

原书题目P19 · 解析P26 · 目视转录

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

  1. 给出算法的基本设计思想。
  2. 根据设计思想,采用 C 或 C++ 或 Java 语言描述算法,关键之处给出注释。
  3. 说明你所设计算法的时间复杂度和空间复杂度。
查看答案与解析

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

分别求两个升序序列 AA、BB 的中位数,设为 aa 和 bb,求序列 AA、BB 的中位数过程如下:

① 若 a=ba=b,则 aa 或 bb 为所求中位数,算法结束。

② 若 a<ba<b,则舍弃序列 AA 中较小的一半,同时舍弃序列 BB 中较大的一半,要求两次舍弃的长度相等。

③ 若 a>ba>b,则舍弃序列 AA 中较大的一半,同时舍弃序列 BB 中较小的一半,要求两次舍弃的长度相等。

在保留的两个升序序列中,重复过程①、②、③,直到两个序列中均只含一个元素时为止,较小者为所求的中位数。

2)本题代码如下:

int M_Search(int A[],int B[],int n){
    int s1,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])
            return A[m1];             // 满足条件①
        if(A[m1]<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的前半部分
            }
        }
    }
    return A[s1]<B[s2]? A[s1]:B[s2];
}

3)算法的时间复杂度为 O(log⁡2n)O(\log_2 n),空间复杂度为 O(1)O(1)。

【另解】对两个长度为 nn 的升序序列 AA 和 BB 中的元素按从小到大的顺序依次访问,这里访问的含义只是比较序列中两个元素的大小,并不实现两个序列的合并,因此空间复杂度为 O(1)O(1)。按上述规则访问第 nn 个元素时,这个元素为两个序列 AA 和 BB 的中位数。

综合应用题 12

原书题目P20 · 解析P27 · 目视转录

【2013 统考真题】已知一个整数序列 A=(a0,a1,⋯ ,an−1)A=(a_0,a_1,\cdots,a_{n-1}),其中 0≤ai<n0\le a_i<n(0≤i<n0\le i<n)。若存在 ap1=ap2=⋯=apm=xa_{p_1}=a_{p_2}=\cdots=a_{p_m}=x 且 m>n/2m>n/2(0≤pk<n,1≤k≤m0\le p_k<n,1\le k\le m),则称 xx 为 AA 的主元素。例如 A=(0,5,5,3,5,7,5,5)A=(0,5,5,3,5,7,5,5),则 5 为主元素;又如 A=(0,5,5,3,5,1,5,7)A=(0,5,5,3,5,1,5,7),则 AA 中没有主元素。假设 AA 中的 nn 个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出 AA 的主元素。若存在主元素,则输出该元素;否则输出 −1-1。要求:

  1. 给出算法的基本设计思想。
  2. 根据设计思想,采用 C 或 C++ 或 Java 语言描述算法,关键之处给出注释。
  3. 说明你所设计算法的时间复杂度和空间复杂度。
查看答案与解析

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

算法可分为以下两步:

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

② 判断 cc 中元素是否是真正的主元素。再次扫描该数组,统计 cc 中元素出现的次数,若大于 n/2n/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中的候选主元素计数
        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(n),空间复杂度为 O(1)O(1)。

说明:本题若采用先排序再统计的方法[时间复杂度为 O(nlog⁡2n)O(n\log_2 n)],则只要解答正确,最高可拿 11 分。即使是写出 O(n2)O(n^2) 的算法,最高也能拿 10 分,因此对于统考算法题,花费大量时间去思考最优解法是得不偿失的。本算法的方法非常典型,需牢固掌握。

综合应用题 13

原书题目P20 · 解析P28 · 目视转录

【2018 统考真题】给定一个含 nn(n≥1n\ge1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组 {−5,3,2,3}\{-5,3,2,3\} 中未出现的最小正整数是 1;数组 {1,2,3}\{1,2,3\} 中未出现的最小正整数是 4。要求:

  1. 给出算法的基本设计思想。
  2. 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。
  3. 说明你所设计算法的时间复杂度和空间复杂度。
查看答案与解析

1)算法的基本设计思想。

要求在时间上尽可能高效,因此采用空间换时间的办法。分配一个用于标记的数组 B[n]B[n],用来记录 AA 中是否出现了 1∼n1\sim n 中的正整数,B[0]B[0] 对应正整数 1,B[n−1]B[n-1] 对应正整数 nn,初始化 BB 中全部为 0。AA 中含有 nn 个整数,因此可能返回的值是 1∼n+11\sim n+1,当 AA 中 nn 个数恰好为 1∼n1\sim n 时返回 n+1n+1。当数组 AA 中出现了小于或等于 0 或大于 nn 的值时,会导致 1∼n1\sim n 中出现空余位置,返回结果必然在 1∼n1\sim n 中,因此对于 AA 中出现了小于或等于 0 或大于 nn 的值,可以不采取任何操作。

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

2)算法实现。

int findMissMin(int A[],int n)
{
    int i,*B;                         // 标记数组
    B=(int *)malloc(sizeof(int)*n);   // 分配空间
    memset(B,0,sizeof(int)*n);         // 赋初值为0
    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)时间复杂度:遍历 AA 一次,遍历 BB 一次,两次循环内操作步骤为 O(1)O(1) 量级,因此时间复杂度为 O(n)O(n)。空间复杂度:额外分配了 B[n]B[n],空间复杂度为 O(n)O(n)。

综合应用题 14

原书题目P20 · 解析P28 · 目视转录

【2020 统考真题】定义三元组 (a,b,c)(a,b,c)(a,b,ca,b,c 均为整数)的距离 D=∣a−b∣+∣b−c∣+∣c−a∣D=|a-b|+|b-c|+|c-a|。给定 3 个非空整数集合 S1S_1、S2S_2 和 S3S_3,按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法,计算并输出所有可能的三元组 (a,b,c)(a,b,c)(a∈S1,b∈S2,c∈S3a\in S_1,b\in S_2,c\in S_3)中的最小距离。例如 S1={−1,0,9}S_1=\{-1,0,9\},S2={−25,−10,10,11}S_2=\{-25,-10,10,11\},S3={2,9,17,30,41}S_3=\{2,9,17,30,41\},则最小距离为 2,相应的三元组为 (9,10,9)(9,10,9)。要求:

  1. 给出算法的基本设计思想。
  2. 根据设计思想,采用 C 语言或 C++ 语言描述算法,关键之处给出注释。
  3. 说明你所设计算法的时间复杂度和空间复杂度。
查看答案与解析

分析。由 D=∣a−b∣+∣b−c∣+∣c−a∣≥0D=|a-b|+|b-c|+|c-a|\ge0 有以下结论。

① 当 a=b=ca=b=c 时,距离最小。

② 其余情况,不失一般性,假设 a≤b≤ca\le b\le c,在数轴上 aa、bb、cc 从左到右排列,令 L1=∣a−b∣L_1=|a-b|,L2=∣b−c∣L_2=|b-c|,L3=∣c−a∣L_3=|c-a|,则

D=∣a−b∣+∣b−c∣+∣c−a∣=L1+L2+L3=2L3≥0.D=|a-b|+|b-c|+|c-a|=L_1+L_2+L_3=2L_3\ge0.

由 DD 的表达式可知,事实决定 DD 大小的关键是 aa 和 cc 之间的距离,于是问题就可以简化为每次固定 cc 找一个 aa,使得 L3=∣c−a∣L_3=|c-a| 最小。

1)算法的基本设计思想:

① 使用 Dmin⁡D_{\min} 记录所有已处理的三元组的最小距离,初值为一个足够大的整数。

② 集合 S1S_1、S2S_2 和 S3S_3 分别保存在数组 AA、BB、CC 中。数组的下标变量 i=j=k=0i=j=k=0,当 i<∣S1∣i<|S_1|、j<∣S2∣j<|S_2| 且 k<∣S3∣k<|S_3| 时(∣S∣|S| 表示集合 SS 中的元素个数),循环执行下面的 a)~c)。

a)计算 (A[i],B[j],C[k])(A[i],B[j],C[k]) 的距离 DD;(计算 DD)

b)若 D<Dmin⁡D<D_{\min},则 Dmin⁡=DD_{\min}=D;(更新 DD)

c)将 A[i]A[i]、B[j]B[j]、C[k]C[k] 中的最小值的下标加 1;(对照分析:最小值为 aa,最大值为 cc,这里 cc 不变而更新 aa,试图寻找更小的距离 DD)

③ 输出 Dmin⁡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 A[],int n,int B[],int m,int C[],int p){
    // D_min用于记录三元组的最小距离,初值赋为INT_MAX
    int i=0,j=0,k=0,D_min=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<D_min) D_min=D;           // 更新D
        if(xls_min(A[i],B[j],C[k])) i++; // 更新a
        else if(xls_min(B[j],C[k],A[i])) j++;
        else k++;
    }
    return D_min;
}

3)设 n=∣S1∣+∣S2∣+∣S3∣n=|S_1|+|S_2|+|S_3|,时间复杂度为 O(n)O(n),空间复杂度为 O(1)O(1)。