栈和队列部分习题
一、单项选择题
1.栈的插入和删除操作在______进行。
A、栈顶
B、栈底
C、任意位置
D、指定位置
2.在栈中存取数据的原则是______。
A、先进先出
B、后进先出
C、后进后出
D、随意进出
3.当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插
入一个元素时，首先应执行______语句修改top指针。
A、top++;
B、top--;
C、top=0;
D、top=N-1;
4.判断一个由ST指向的栈（最多元素m0）为满的条件是______。
A、ST->top !=0
B、ST->top= =0
C、ST->top!=m0
D、ST->top = =m0-1
5.对于顺序栈]，假设栈底在stack[0]处，并用top指向栈顶元素之后的空位置，
则判断栈空的条件是______。
A、top= = -1
B、top= =0
C、top= =1
D、top==n-1
6.假定利用数组a[N+1]顺序存储一个栈，用top表示栈顶指针，用top=N+1表示栈空，
该数组所存储的栈的最大长度为N，则表示栈满的条件为______。
A、top==1
B、top==-1
C、top=0
D、top=N-1
7.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并
已知栈未满，当元素x进栈时所执行的操作为______。
A、a[--top]=x;
B、a[top--]=x;
C、a[++top]=x;
D、a[top++]=x;
8.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并
已知栈未空，当退栈并返回栈顶元素时所执行的操作为______。
A、return a[--top];
B、return a[top--];
C、return a[++top];
D、return a[top++];
9.假定一个链式栈的栈顶指针用top表示，该链式栈为空的条件______。
A、top！=NULL
B、top==top->next
C、top== NULL
D、top！= top->next
10.假定一个链式栈的栈顶指针用top
p所指向的
结点进栈时，执行的操作为______。
A、p->next=top; top=top->next;
B、top=p; p->next=top;
C、p->next=top->next; top->next=p;
D、p->next=top; top=p;
11.
假定一个链式栈的栈顶指针用top 的操作为______。
A、top->next=top;
B、top=top->data;
C、top=top->next;
D、top->next=top->next->next;
12.若让元素1，2，3，4依次进栈，则出栈次序不可能出现______的情况。
A、3，2，1，4
B、2，1，4，3
C、4，3，2，1
D、1，4，2，3
13.由两个栈共享一个向量空间的好处是：______。
A、减少存取时间，降低下溢发生的机率
B、节省存储空间，降低上溢发生的机率
C、减少存取时间，降低上溢发生的机率
D、节省存储空间，降低下溢发生的机率
14.队列结构通常采用的两种存储结构是______。
A、顺序存储结构和链式存储结构
B、散列方式和索引方式
C、链表存储结构和数组
D、线性存储结构和非线性存储结构
15.假设一个队列的入队序列是1,2,3,4，则队列的输出序列是______。
A、4,3,2,1
B、1,2,3,4
C、1,4,3,2
D、3,2,4,1
16.以下______不是队列的基本运算。
A、从队尾插入一个新元素
B、从队列中删除第i个元素
C、判断一个队列是否为空
D、读取队头元素的值
17.在初始为空的队列中顺序插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队
尾元素是______。
A、a
B、b
C、c
D、d
18.对于长度为n的队列，出队操作的时间复杂度为______。
A、O(1)
B、O(log2n)
C、O(n)
D、O(n２)
19.当利用大小为N的数组循环存储一个队列时，该队列的最大长度为______。
A、N-2
B、N-1
C、N
D、N+1
20.从一个顺序循环队列中删除元素时，首先需要______。
A、前移队首指针
B、后移队首指针
C.取出队首指针所指位置上的元素D、取出队尾指针所指位置上的元素
21.假定一个顺序循环队列的队首和队尾指针分别用f和r表示，则判断队空的条件为
_____。
A、f+1==r
B、r+1==f
C、f==0
D、f==r
22.假定一个顺序循环队列存储于数组a[N]，其队首和队尾指针分别用f和r表示，则判
断队满的条件为______。
A、（r-1）%N==f
B、（r+1）%N==f
C、（f-1）%N==r
D、（f+1）%N==r
23.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并
已知队列未满，当元素x入列时所执行的操作为______。
A、a[++r%N]=x;
B、a[r++%N]=x;
C、a[--r%N]=x;
D、a[r--%N]=x;
24.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并
已知队列未空，当出列并返回队首元素时所执行的操作为______。
A、return a[++r%N];
B、return a[--r%N];
C、return a[++f%N];
D、return a[f++%N];
25.假定一个链式队列的队首和队尾指针分别为front和rear，则判断队空的条件为
______。
A、front==rear
B、front！=NULL
C、rear！=NULL
D、front==NULL
26.假定一个链式队列的队首和队尾指针分别为front和rear
当
出列时所进行的操作为______。
A、front=front->next;
B、rear=rear->next;
C、front->next =rear；rear=rear->next;
D、front=front->next；front->next =rear;
27.假定一个带头结点的循环链式队列的队首和队尾指针分别用front和rear表示，则判断
队空的条件为______。
A、front=rear->next
B、rear==NULL
C、front==NULL
D、front ==rear
28.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为包含值域
data和指针域next，则使p所指结点入列所执行的操作为______。
A、p->next=NULL；rear->next=p；
B、p->next=rear->next；rear=rear->next=p；
C、p->next=front；front=p；
D、p->next=front->next；front->next=p；
29.在一个长度为N的数组空间中，循环顺序存储着一个队列，该队列的队首和队尾指针
数组和链表
分别用front和rear表示，则该队列中数组元素个数为______。
A、（rear-front）%N
B、（rear-front+N）%N
C、（rear+N）%N
D、（front+N）%N
30.在初始为空的堆栈中依次插入元素f,e,d,c,b,a以后，连续进行了三次删除操作，此时栈
顶元素是______。
A、c
B、d
C、b
D、e
31.若某堆栈的输入序列是1,2,3,---,n，输出序列的第一个元素为n，则第i个输出元素为
______。
A、i
B、n-I
C、n-i+1
D、哪个元素无所谓
32.向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行______。
A、h- > next=s;
B、s- > next=h;
C、s- > next=h; h=h- > next;
D、s- > next=h- > next ; h- > next=s;
33.一个栈的入栈序列是a,b,c,d,e，则栈不可能的输出序列是______。
A、edcba
B、decba
C、dceab
D、abcde
34.栈和队列的共同点是______。
A、都是先进后出
B、都是先进先出
C、只允许在指定端点处插入和删除元素
D、没有共同点
35.对于循环队列______。
A、无法判断队列是否为空
B、无法判断队列是否为满
C、队列不可能满
D、以上说法都不是
36.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当
从队列中删除一个元素，再加入两个元素后，rear和front的值分别为______。
A、1和5
B、2和4
C、4和2
D、5和1
37.设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是______。
A、1，2，3，4，5，6
B、2，1，3，4，5，6
C、3，4，2，1，5，6
D、4，3，2，1，5，6
38.设栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈，
______是可能的出栈序列。
A、E D C A B F
B、B C E F A D
C、C B E D A F
D、A D F E B C
39.在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，
主机将要输出的数据依次写入该缓冲区，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个______结构。
A、栈
B、队列
C、数组
D、线性表
二、填空题
1.栈是一种________________的线性表。
2.在栈结构中，允许插入、删除的一端称为______，另一端称为_______。
3.对于顺序存储的栈，因为栈的空间是有限的，在进行______运算时，可能发生栈的上
溢。
4.用单链表实现一个栈的时候，插入一个元素是在单链表的________进行。
5.链式栈永远不会发生栈满的情况，此说法是____________。
6.设有一个顺序栈S，数据元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为
s2,s3,s4,s6,s5,s1，则顺序栈的容量至少为______。
7.两个栈共享一个向量空间时，两个栈的栈底在________________。
8.向栈中压入元素x的操作是____________。
9.对栈进行退栈时的操作是____________。
10.顺序存储的栈在进行__________运算时，可能发生栈的下溢。
11.设有一个空栈，现输人序列为1,2,3,4,5。经过push, push, pop, push, pop, push, pop,push
后，输出序列是____________。
12.仅允许在同一端进行插入和删除的线性表称为______。
13.顺序栈]进行初始化执行的操作是（top为指向栈顶的当前元素，第一个入栈
的元素放在stack[0]处）________________。
14.用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈
顺序，相应的S、X操作串为______。
15.在队列中，存取数据应遵从的原则是___________。
16.在队列结构中，允许插入的一端称为_________；允许删除的一端称为_________。
17.在顺序循环队列中，假设队头指针front指向队头元素，队尾指针rear指向队尾元素后
的一个空闲元素。则在循环队列中，判断队空的条件为________；判断队满的条件为________。当rear>=front时，队列长度为_____________。
18.用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，
若要达到队满的条件，还需要继续入队的元素个数是______。
19.假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当p所指向
的结点入栈时，则首先执行____________操作，然后执行____________操作。
20.假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当进行出栈
运算时（假定栈非空），需要把栈顶指针修改为________的值。
21.设元素1，2，3，4，5依次进栈，若要在输出端得到序列34251，则应进行的操作序
列为Push(s,1),Push(s,2),________,Pop(s),Push(s,4),Pop(s),_______,_________,Pop(s), Pop(s)。
22.设元素a，b，c，d依次进栈，若要在输出端得到序列cbda，则应进行的操作序列为
Push(s,a),Push(s,b),Push(s,c),________,________，____________Pop(s),Pop(s)。
23.一个顺序循环队列存在于a[M]中，假定队首和队尾指针分别为front和rear，则判断队
空的条件为______________，判断队满的条件为______________。
24.一个顺序循环队列存在于a[M]中，假定队首和队尾指针分别为front和rear，则求出队
首和队尾指针的下一个位置的计算公式分别为____________和____________。
25.在一个用一维数组a[N]存储的顺序循环队列中，该队列中的元素个数最少为____个，
最多为____个。
26.向一个顺序循环队列中插入元素时，需要首先移动________，然后再向它所指位置
______新元素。
27.在用一维数组a[m]存储的顺序循环队列中，如果队头指针front指向队头元素前的空
位置，队尾指针rear指向队尾元素，则删除一个结点时队列指针的操作为
____________。
28.在一个带头结点的循环链队列中，假定队首和队尾指针分别为f和r，当向它插入一个
新结点*p时，则执行的语句为________________________。
29.假定front和rear分别为一个链队列的队首和队尾指针，则该链队列中只有一个结点的
条件为________________________。
30.在一个链栈中，若栈顶指针等于NULL则为________；在一个链队列中，若队首和队
尾的指针相同，则表示该队列为________或该队列____________。
31.引入循环队列的目的是为了克服____________。
32.递归算法中，每次递归调用前，系统自动将需要保存的数据放入__________中。
三、综合题
1.试编写一个算法，用顺序栈s实现函数关系式F(n)=n×F(n-1)，其中当n=1的时候，
F(1)=1。可以直接使用的操作函数包括：初始化栈操作SETNULL(s)、栈空判断操作EMPTY(s)、入栈操作push(s, x)、出栈操作pop(s)和取栈顶元素操作gettop(s)。
2.假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen分别指示队尾元
素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入列和出列算法。
3.对于一个栈，如果输入项序列由A，B，C所组成，试给出全部可能的输出序列并给
出它们的进栈和出栈过程。
4.简述以下算法的功能，其中栈和队列的元素类型均为int。算法中包含的操作说明如下：
入栈操作push(S, x)、出栈操作pop(s)、初始化栈操作SETNULL(s)、判断栈空的操作EMPTY(s)和取栈顶元素的操作gettop(s)。
（1）void proc_1(Stack S)
{int i, n, A[255];
n=0;
while(!EMPTY(S))
{n++;A[n]=Pop(S);}
for(i=1; i<=n; i++)
Push(S, A[i]);
}
（2）void proc_2(Stack S, int e)
{Stack T;
int d;
SETNULL(T);
while(!EMPTY(S))
{d=Pop(S);
if (d!=e)Push(T, d);
}
while(!EMPTY(T))
{d=Pop(T);
Push( S, d);
}
}
5.假设一个算术表达式中可以包含3种括号：圆括号“（”和“）”，方括号“[”和“]”，
花括号“{”和“}”，且这3种括号可任意的次序嵌套使用。利用顺序栈s编写判别给定表达式中所含括号是否正确配对出现的算法（假定表达式已存入数据元素为字符的顺序表中）。
正确格式形如：( )、( [ ] )、[ ( ) ]、( [ ] [ ] )
不正确的示例包括：( ]、[ )、( [ ] ]、[ { } )等。
假设下列操作可以直接使用：入栈操作push(s, x)、出栈操作pop(s)、初始化栈操作