数据结构摘星题库800题笔记 第3章栈、队列和数组

第3章栈、队列和数组

§3.1 栈

考点 1 栈的概念

题组闯关

1.一个栈的入栈顺序序列是 ABCDE，则不可能的出栈序列是 ( )。
A. ABCDE
B. EDCBA
C. DECBA
D. DCEAB

2.已知操作符包括 “+”“-”“×”“/”“(” 和 “)”。将中缀表达式a+b−a×((c+d)/e−f)+g转换为后缀表达式ab+acd+e/f−×−g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是 ( )。
A. 5
B. 7
C. 9
D. 11

3.若已知一个栈的进栈序列是1,2,3,⋯,n，其输出序列为p1​,p2​,p3​,⋯,pn​。若p1​=3，则p2​为 ( )。
A. 可能是 2
B. 一定是 2
C. 可能是 1
D. 一定是 1

4.一个栈的入栈序列为1,2,3,4,⋯,n，其出栈序列是p1​,p2​,p3​,⋯,pn​。若p2​=3，则p3​可能取值的个数是 ( )。
A. n−3
B. n−2
C. n−1
D. 无法确定

5.一个栈的输入序列为1,2,3,4,⋯,n，若输出序列的第一个元素是n，输出第i个元素是 ( )。
A. 不确定
B. n−1
C. i
D. n−i+1

6.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且 7 个元素出列的顺序是b,d,c,e,g,f,a，则栈S的容量至少是 ( )。
A. 1
B. 2
C. 3
D. 4

7.由两个栈共享一个向量空间的好处是 ( )。
A. 减少存取时间，降低上溢发生的几率
B. 节省存储空间，降低上溢发生的几率
C. 减少存取时间，降低下溢发生的几率
D. 节省存储空间，降低下溢发生的几率

真题实战（题组闯关对应真题）

1.若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是 ( )。【北京化工大学 2019 年】
A. dcebfa
B. cbdaef
C. bdceaf
D. afedcb

2.给定有限符号集S，in 和 out 均为S中所有元素的任意排列。对于初始为空的栈ST，下列叙述中，正确的是 ( )。【全国统考 2022 年】
A. 若 in 是ST的入栈序列，则不能判断 out 是否为其可能的出栈序列
B. 若 out 是ST的出栈序列，则不能判断 in 是否为其可能的入栈序列
C. 若 in 是ST的入栈序列，out 是对应 in 的出栈序列，则 in 与 out 一定不同
D. 若 in 是ST的入栈序列，out 是对应 in 的出栈序列，则 in 与 out 可能互为倒序

考点 2 顺序栈

题组闯关

若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈（i=1,2）栈顶，栈 1 的底在V[1]，栈 2 的底在V[m]，则栈满的条件是 ( )。
A. ∣top[2]−top[1]∣=0
B. top[1]+1=top[2]
C. top[1]+top[2]=m
D. top[1]=top[2]

真题实战

1.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x入栈的正确操作是 ( )。【中国科学院大学 2015 年】
A. top=top+1;V[top]=x
B. V[top]=x;top=top+1
C. top=top−1;V[top]=x
D. V[top]=x;top=top−1

2.若双栈共享空间S[0..n−1]，初始时top1=−1，top2=n，则判栈满为真的条件是 ( )。【北京邮电大学 2016 年】
A. top1==top2
B. top1−top2==1
C. top1+top2==n
D. top2−top1==1

3.若有一线stack[0..n−1]，初始时栈顶指针top为n，则以下元素x进栈的正确操作是 ( )。【武汉大学 2015 年】
A. top++;stack[top]=x;
B. stack[top]=x;top++;
C. top−−;stack[top]=x;
D. stack[top]=x;top−−;

考点 3 链栈

题组闯关

向一个栈顶指针为top的链栈中插入一个x节点，则执行 ( )。
A. top−>next=x;
B. x−>next=top−>next;top−>next=x;
C. x−>next=top;top=x;
D. x−>next=top;top=top−>next;

真题实战

链式栈与顺序栈相比，一个比较明显的优点是 ( )。【宁波大学 2012 年】
A. 插入操作更加方便
B. 通常不会出现栈满的情况
C. 不会出现栈空的情况
D. 删除操作更加方便

考点 4 栈的应用

题组闯关

1.以下哪个选项中不会应用到栈 ( )。
A. 递归
B. 图的广度优先搜索
C. 表达式求值
D. 树的深度优先遍历

2.表达式3×2∗(4+2×2−6×3)−5，求值过程中当扫描到 6 时，对象栈和算符栈为 ( )，其中 ^ 为乘幂。
A. 3,2,8;×−
B. 3,2,4,2,2;×+×−
C. 3,2,4,2,2;×(+×−
D. 3,2,8;×(−

3.有函数intfunc(inti)的实现如下：

int func(int i)
{
    if (i > 1)
        return i * func(i - 1);
    else
        return 1;
}

请问函数调用func(5)的返回值是多少 ( )。
A. 5
B. 15
C. 20
D. 120
4. 一个问题的递归算法求解和其相对应的非递归算法求解相比 ( )。
A. 递归算法通常高效一些
B. 非递归算法通常高效一些
C. 两者相同
D. 无法比较
5. 当执行函数时，其局部变量的存储一般采用 ( ) 进行存储。
A. 树
B. 静态链表
C. 栈
D. 队列

真题实战

1.已知程序如下：

int S(int n){
    return (n <= 0)? 0 : S(n - 1) + n;
}
void main(){
    count << S(1);
}

程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是 ( )。【全国统考 2015 年】
A. main()→S(1)→S(0)
B. S(0)→S(1)→main()
C. main()→S(0)→S(1)
D. S(1)→S(0)→main()
2. 利用栈求表达式的值时，设立运算数栈OPEN。假设OPEN只有两个存储单元，在下列表达式中，不发生溢出的是 ( )。【武汉大学 2011 年】
A. A−B×(C−D)
B. (A−B)×C−D
C. (A−B×C)−D
D. (A−B)×(C−D)
3. 算术表达式a+b×(c+d/e)转为后缀表达式后为 ( )。【上海海事大学 2017 年】
A. abcde/+×+
B. abcde/∗++
C. abcde∗/++
D. ab+cde/∗

§3.2 队列

考点 1 队列的概念

题组闯关

1.栈和队列的共同点是 ( )。
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点

2.以下哪个问题的求解需要使用队列 ( )。
A. 函数调用时保存函数的参数、局部变量等
B. 检查括号匹配
C. 图的广度优先搜索
D. 基于深度优先搜索的图的拓扑排序过程

3.假设用数组A[8]存储循环队列的元素，其头、尾指针front和rear的当前值分别为 4 和 0。当从队列中出队列两个元素，再入队列一个元素后，front和rear的值分别为 ( )。
A. 3 和 6
B. 6 和 3
C. 1 和 6
D. 6 和 1

4.对于空队列Q，执行如下一组操作：
EnQueue(Q,1);DeQueue(Q);
EnQueue(Q,2);EnQueue(Q,3);
DeQueue(Q);EnQueue(Q,4);
操作之后，队头元素是 ( )。
A. 1
B. 2
C. 3
D. 4

真题实战

1.一个队列的入列序列是1,2,3,4，则队列的出队序列是 ( )。【暨南大学 2017 年】
A. 4,3,2,1
B. 1,2,3,4
C. 1,4,3,2
D. 3,2,4,1

2.循环队列存储在数组A[0...m−1]，则出队时的操作为 ( )。【中国海洋大学 2011 年】
A. front=front+1
B. front=(front+1)mod(m−1)
C. front=(front+1)modm
D. front=(frontmodm)+1

3.下列操作中，不属于队列基本操作的是 ( )。【广东工业大学 2017 年】
A. 取队头元素
B. 删除队头元素
C. 取队尾元素
D. 插入队尾元素

4.有关队列的叙述中正确的是 ( )。【武汉大学 2013 年】
I. 队列中元素的逻辑关系是线性关系
II. 队列中元素的逻辑关系不一定是线性关系
III. 队列是一种先进先出表
IV. 队列的插入和删除操作在同一端进行
A. 仅 I、IV
B. 仅 I、III
C. 仅 II、III
D. 仅 I、III、IV

5.设循环队列中数组的下标为0∼N−1，已知其队头指针f（指向队首元素的前一位置）和队中元素个数n，则队尾指针r（指向队尾元素的位置）为 ( )。【四川大学 2017 年】
A. f−n
B. (f−n)%N
C. (f+n)%N
D. (f+n+1)%N

6.已知初始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1,2,3,4,5，则不能得到的出队序列是 ( )。【全国统考 2021 年】
A. 5,4,3,1,2
B. 5,3,1,2,4
C. 4,2,1,3,5
D. 4,1,3,2,5

考点 2 顺序队列

题组闯关

1.设顺序循环队列Q[0:M−1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一个位置，尾指针R总是指向队尾元素的当前位置，则该循环队列的元素个数为 ( )。
A. R−F
B. F−R
C. (R−F+M)%M
D. (F−R+M)%M

2.设栈S和队列Q的初始状态为空，元素E1​,E2​,E3​,E4​,E5​,E6​依次通过栈S，一个元素出栈后立即进入队列Q，若 6 个元素出队的顺序为E2​,E4​,E3​,E6​,E5​,E1​，则栈S的容量至少应该是 ( )。
A. 6
B. 4
C. 3
D. 2

3.已知循环队列的存储空间为A[21]，front指向队头元素的前一个位置，rear指向队尾元素，假设当前front和rear的值分别为 8 和 3，则该队列的长度为 ( )。
A. 5
B. 6
C. 16
D. 17

4.假设循环队列的长度为QSize。当队列未满时，向队列中添加一个数据后，其队尾下标Rear的变化为 ( )。
A. Rear=Rear+1
B. Rear=Rear+%QSize
C. Rear=(Rear+1)%QSize
D. Rear=Rear%Qsize+1

5.循环队列用数组A[0...m−1]存放其元素值，已知其队头指针front指向队头元素，队尾指针rear指向队尾元素，则当前队列的元素个数是 ( )。
A. (rear−front+m)%m
B. rear−front+1
C. (rear−front+m+1)%m
D. (rear−front+m−1)%m

6.若用一个大小为 6 的数组来实现循环队列，且当前rear和front的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 ( )。
A. 1 和 5
B. 2 和 4
C. 4 和 2
D. 5 和 1

7.循环队列存储在数组A[0...m]中，则入队时的操作为 ( )。
A. rear=rear+1
B. rear=(rear+1)%(m−1)
C. rear=(rear+1)%m
D. rear=(rear+1)%(m+1)

真题实战

1.循环队列放在一维数组A[0...M−1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M−1个元素。初始时为空。下列判断队空和队满的条件中，正确的是 ( )。【全国统考 2014 年】
A. 队空：end1==end2；队满：end1==(end2+1)%M
B. 队空：end1==end2；队满：end2==(end1+1)%(M−1)
C. 队空：end2==(end1+1)%M；队满：end1==(end2+1)%M
D. 队空：end1==(end2+1)%M；队满：end2==(end1+1)%(M−1)

2.采用顺序存储结构的栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f依次进入队列Q，Q中每一个元素出队后立刻进入栈S，如果 6 个元素出栈序列是：b,c,d,f,e,a，则栈S的容量最少是 ( )。【北京工业大学 2018 年】
A. 2
B. 3
C. 4
D. 5

3.循环队列用数组A[0...m−1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是 ( )。【暨南大学 2017 年】
A. (rear−front+m)%m
B. rear−front+1
C. rear−front−1
D. rear−front

4.若线性表中总的元素个数基本稳定，但经常要在表头删除元素，在表尾插入元素，那么最好采用 ( ) 来实现该线性表。【武汉大学 2015 年】
A. 带头指针的单链表
B. 双向循环链表
C. 循环顺序队列
D. 顺序表

5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为 ( )。【上海海事大学 2016 年】
A. rear%n==front
B. (front+1)%n==rear
C. rear%n−1==front
D. (rear+1)%n==front

考点 3 链队列

题组闯关

1.若用一个大小为 6 的数组来实现循环队列，且rear和front的值分别为 0 和 3。从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 ( )。
A. 1 和 5
B. 2 和 4
C. 4 和 2
D. 5 和 1

2.用链接方式存储的队列，在进行删除运算时 ( )。
A. 仅修改头指针
B. 仅修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针可能都要修改

3.设循环队列的存储空间为Q(1:35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为 ( )。
A. 15
B. 16
C. 20
D. 0 或 35

4.单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为 ( )。
A. O(n)
B. O(1)
C. O(n2)
D. O(nlogn)

真题实战

1.若用带头节点的单循环链表表示非空队列，队列只设一个指针Q，则插入新元素节点P的操作语句序列是 ( )。【北京邮电大学 2016 年】
A. P−>next=Q−>next;Q−>next=P;Q=P
B. Q−>next=P;P−>next=Q−>next;Q=P
C. P−>next=Q−>next−>next;Q=P
D. P−>next=Q−>next;Q=P

2.假定一个带头节点的链队列的队头和队尾指针分别为front和rear，则判断队空的条件为 ( )。【广东工业大学 2019 年】
A. front==rear
B. rear!=NULL
C. front!=NULL
D. front==NULL

3.若用一个不带头节点的循环单链表表示队列，则最好用 ( ) 标识链队。【四川大学 2016 年】
A. 首节点指针
B. 尾节点指针
C. 首节点和尾节点两个指针
D. 任何节点指针

考点 4 队列的应用

题组闯关

1.执行 ( ) 操作时，需要使用队列作为辅助存储空间。
A. 查找散列（哈希）表
B. 广度优先搜索图
C. 前序（根）遍历二叉树
D. 深度优先搜索图

2.为解决计算机主机与打印机之间的速度不匹配问题，通常设计一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 ( )。
A. 栈
B. 队列
C. 树
D. 图

§3.3 数组

考点 1 数组的定义和存储

题组闯关

任何一个基于比较的算法在一个长度为n的数组中同时找出最大和最小值，至少需要数组元素之间的比较的次数与下列 ( ) 最接近。
A. n
B. 1.5n
C. 2n
D. n2

真题实战

1.数组通常具有的两种基本操作是 ( )。【北京邮电大学 2018 年】
A. 插入和删除元素
B. 插入和查找元素
C. 修改和删除元素
D. 查找和修改元素

2.在n个节点的线性表的数组表示中，算法的时间复杂度是O(1)的操作是 ( )。【北京工业大学 2014 年】
A. 访问第i个节点(1≤i≤n)和求第i个节点的直接前驱(2≤i≤n)
B. 在第i个节点后插入一个新节点(1<i≤n)
C. 删除第i个节点(1≤i≤n)
D. 以上都不对

3.已知二维数组A按行优先方法存储，每个元素占用 1 个存储单元。若元素A[0][0]的存储地址是 100，A[3][3]的存储地址是 220，则元素A[5][5]的存储地址是 ( )。【全国统考 2021 年】
A. 295
B. 300
C. 301
D. 306

考点 2 数组的压缩存储

题组闯关

已知二维数组A[1:4][1:6]采用列为主序方式存储，每个元素占用 5 个存储单元，并且A[3,4]的存储地址为 2091，那么元素A[1,1]的存储地址为（ ）。
A. 2011
B. 2021
C. 2031
D. 2041

对稀疏矩阵采用压缩存储，其缺点之一是（ ）。
A. 无法判断矩阵有多少行多少列
B. 无法根据行列号查找某个矩阵元素
C. 无法根据行列号计算矩阵元素的存储地址
D. 使矩阵元素之间的逻辑关系更加复杂

若以行优先顺序存储三维数组A[4][5][6]，其中元素A[0][0][0]的地址为 1000，且每个元素占 2 个存储单元，则A[3][2][1]的地址为（ ）。
A. 1150
B. 1206
C. 1200
D. 1380

设有一个二维数组A[m,n]，假设A[0][0]存放位置在644(10)​，A[2][2]存放位置在676(10)​，每个元素占一个空间，则A[3][3]在（ ）位置，(10)表明用 10 进制数表示。
A. 692(10)​
B. 626(10)​
C. 709(10)​
D. 724(10)​

真题实战

用足够容量的一维数组B对n×n阶对称矩阵A进行压缩存储，若B中只存储对称矩阵A的下三角元素，则A[i,j]（其中i<j）存储在B中对应的元素为（ ）。【武汉大学 2015 年】
A. B[i×n/2+j]
B. B[i×(i+1)/2+j]
C. B[j×(j+1)/2+i]
D. B[i×n/2+j]

假设用一个一维数组B来按行存放一个对称矩阵A的下三角部分，那么访问A的下三角部分的第i行第j列元素应表示为（ ）（下标都从 0 开始）。【南京大学 2013 年】
A. B[i×(i−1)/2+j+1]
B. B[i×(i+1)/2+j+1]
C. B[i×(i−1)/2+j]
D. B[i×(i+1)/2+j]

下三角矩阵A(n×n)按行优先顺序压缩在数组Sa[(n+1)×n/2]，若非零元素aij​(0<=i,j<n)存放在Sa[k]中，则i、j和k之间的关系为（ ）。【河海大学 2014 年】
A. k=i×n+j
B. k=j×n/2+i
C. k=(i+1)×i/2+j
D. k=(j−1)×n/2+i−1

若将6×6的上三角矩阵A（下标从 1 起计）的上三角元素按行优先存储在一维数组B中，且B[1]=A11​，那么A35​在B中的下标是（ ）。【广东工业大学 2015 年】
A. B[12]
B. B[13]
C. B[14]
D. B[15]

§3.4 简答题

题组闯关

设计一个算法实现对栈取最小值的操作 min 函数，要求时间复杂度O(1)。

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

设计一个算法，使用两个栈实现队列的入队和出队操作。

编写一个双向起泡的排序算法，即相邻两趟向相反方向起泡。

什么是队列的上溢现象？一般有几种解决方法？

请简述判断队列为空和队列为满的方法都有哪些？

在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点？

（1）分别用多个顺序存储空间建立多个独立的堆栈；

（2）多个堆栈共享一个顺序存储空间；

（3）分别建立多个独立的链接堆栈。

写出下列程序段的输出结果（栈的元素类型 SElemType 为 char）。

c

运行

void main(){

    Stack S;

    char x,y;

    InitStack(S);

    x = 'c';

    y = 'k';

    Push(S,x);

    Push(S,'a');

    Push(S,y);

    Pop(S,x);

    Push(S,'t');

    Push(S,x);

    Pop(S,x);

    Push(S,'s');

    while(!StackEmpty(S)){

        Pop(S,y);

        printf(y);

    }

    printf(x);}

简述以下算法的功能（栈的元素类型 SElemType 为 int）。
（1）

c

运行

status algo1(Stack S){

    int i,n,A[255];

    n = 0;

    while(!StackEmpty(S)){

        n ++; Pop(S,A[n]);

    }

    for(i = 1;i <= n;i ++){

        Push(S,A[i]);

    }}

（2）

c

运行

status algo2(Stack S,int e){

    Stack T; int d;

    InitStack(T);

    while(!StackEmpty(S)){

        Pop(S,d);

        if(d != e){

            Push(T,d);

        }

    }

    while(!StackEmpty(T)){

        Pop(T,d);

        Push(S,d);

    }}

真题实战

阅读如下程序，写出此程序的输出结果（其中栈的元素类型为 char）。【暨南大学 2017 年】

c

运行

void main(){

    Stack S;

    char x,y;

    InitStack(S);

    x = 'y'; y = 's';

    Push(S,x); Push(S,y);

    Pop(S,x); Push(S,'k'); Push(S,x);

    while(!StackEmpty(S)){

        Pop(S,y);

        Printf(y);

    }}