第3章 栈和队列
一、 选择题
1. 栈结构通常采用的两种存储结构是（A ）。
A、顺序存储结构和链表存储结构 B、散列和索引方式
C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2. 设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ）
A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3. 向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ）
A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next;
4. 从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C）
A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5. 表达式a*(b+c)-d 的后缀表达式为（ B ）
A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6. 中缀表达式A-（B+C/D）*E 的后缀形式是（ D ）
A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7. 一个队列的入列序列是1，2，3，4， 则队列的输出序列是（ B ）
A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1
8. 循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队
列为空的条件是（ ） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1
9. 循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队
列为满的条件是（ ） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n
10. 若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，
再加入两个元素后，rear 和front 的值分别为（ ） A、1，5 B、2, 4 C、4，2 D、5，1 11. 用单链表表示的链式队列的队头在链表的（ ）位置
A、链头 B、链尾 C、链中
12. 判定一个链队列Q（最多元素为n 个）为空的条件是（ ）
A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13. 在链队列Q 中，插入s 所指结点需顺序执行的指令是（ ）
A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; C 、s->next=Q.rear；Q.rear=s; D 、s->next=Q.front；Q.front=s; 14. 在一个链队列Q 中，删除一个结点需要执行的指令是（ ）
A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next;
1/15
15. 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）
A、仅修改队头指针 B、仅修改队尾指针
C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16. 栈和队列的共同点是（ ）
A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 17. 消除递归（ ）需要使用栈。
A、一定 B、不一定
18. 设有一顺序栈S，元素s1，s2，s3，s4，s5，s6 依次进栈，如果6 个元素出栈的顺序是s2，s3，s4，s6，s5，s1，
则栈的容量至少应该是（ ） A、2 B、3 C、 5 D、 6
19. 若一个栈的输入序列是a，b，c，则通过入、出栈操作可能得到a,b,c 的不同排列个数为（ ）
A、 4 B、 5 C、 6 D、 7
20. 设有一顺序栈已经含有3 个元素，如图3.1 所示元素a4 正等待进栈。下列不可能出现的出栈序列是（ ）
A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1
图3.1
21. 链栈和顺序栈相比，有一个比较明显的优势是（ ）
A、通常不会出现栈满的情况 B、通常不会出现栈空的情况 C、插入操作更容易实现 D、删除操作更加容易实现
22. 若一个栈的输入序列是1，2，3，4，?，n，输出序列的第一个元素是n，则第i 个输出元素是（ C ）
A、不确定 B、 n-i C、 n-i+1 D、n-i-1 23. 以下说法正确的是( )
A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。
二、 判断题
1. 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 2. 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。
3. 若一个栈的输入序列为 1，2，3，?，n，其输出序列的第一个元素为n，则其输出序列的每个元素一定满足
ai=i+1(i=1,2, ?,n)。
4. 在链队列中，即使不设置尾指针也能进行入队操作。
5. 在对链队列（带头指针）做出队操作时，不会改变 front 指针的值。 6. 循环队列中元素个数为 rear-front。
7. 一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。 8. 一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。 9. 若以链表作为栈的存储结构，则进栈需要判断栈是否满。 10. 若以链表作为栈的存储结构，则出栈需要判断栈是否空。
2/15
三、 填空题
1. 栈的特点是（先进后出 ），队列的特点是（ 先进先出 ）。
2. 线性表、栈、队列都是（ ）结构，可以在线性表的（ ）位置插入和删除元素；对于栈只能在（ ）插
入和删除元素；对于队列只能在（ ）插入元素和在（ ）位置删除元素。
3. 有程序如下，则此程序的输出结果（栈的元素类型是SelemType 为char）是（ ）。
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); }
4. 在栈顶指针为HS 的链栈中，判定栈空的条件是（ ）。 5. 向栈中压入元素的操作是先（ ）后（ ）。 6. 对栈进行退栈操作是先（ ）后（ ）。
7. 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ ）和（ ）；若只
设尾指针，则出队和入队的时间复杂度分别是（ ）和（ ）。 8. 从循环队列中删除一个元素时，其操作是（ ）。 9. 在一个循环队列中，队首指针指向队首元素的（ ）。
10. 在具有n 个单元的循环队列中，队满时共有（ ）个元素。 11. 在HQ 的链队列中，判断只有一个结点的条件是（ ）。
12. 设栈S 和队列Q 的初始状态为空，元素a、b、c、d、e、f 依次通过栈S，一个元素出栈后即进入队列Q。若
这6个元素出队列的顺序是b、d、c、f、e、a 则栈S 的容量至少应该是（ ）。
13. 有程序如下，则此程序的输出结果（队列的元素类型是QSelemType 为char）是（ ）。
void main(){
char x=’e’,y=’c’;
enqueue(q,’h’);enqueue(q,’r’);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x); enqueue(q,’a’);
while(!queueempty(q)){
dequeue(q,y);printf(y); }
printf(x);
}
3/15
14. 有如下递归函数：
int dunno(int m){
int value; if(m==0)
value=3; else
value=dunno(m-1)+5; return(value); }
执行语句printf(“%d\\n”,dunno(3));的结果是（ ）。
四、 简答题
1. 对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写
出每种序列对应的操作。例如：A 进B 进C 进C 出B 出A 出，产生的序列为CBA。 2. 简述以下算法的功能（栈的元素类型是 SelemType 为int）。
（1）
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)
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); } }
3. 内存中一片连续空间（不妨假设地址从0 到m-1）提供给两个栈s1 和s2 使用，怎样分配这部分存储空间，
使得对任一栈仅当这部分空间全满时才发生溢出。 4. 有递归过程如下：
void print(int w){
int I;
4/15
if(w!=0){
print(w-1);
for(I=1;I<=w;I++)
printf(“=”,w); printf(“\\n”);
} }
问：调用语句print(4)的结果是什么？
5. 简述以下算法的功能（栈和队列的元素类型均为 int）
void algo(queue &q){
stack s; int d;
initstack(s);
while(!queueempty(q)){
dequeue(q,d); push(s,d); }
while(!stackempty(s)){
pop(s,d);
enqueue(q,d); } }
6. 假设 Q[0，9]是一个非循环线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变
化情况，如果不能入队，请指出其元素，并说明理由。
d,e,b,g,h 入队 d,e 出队 I,j,k,l,m入队 b 出队 n,o,p,q,r 入队。
7. 按照运算符优先数法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：
9-2*4+(8+1)/3。
8. 设栈S＝（1，2，3，4，5，6，7），其中7 为栈顶元素。写出调用algo 后栈S 的状态。
void algo(Stack *S){ int i=0; Queue Q; Stack T;
InitQueue(Q); InitStack(T);
while(!StackEmpty(S)){
if(i%2==0)
Push(T,Pop(S)); else
EnQueue(Q,Pop(S)); i++; }
while(!QueueEmpty(Q))
Push(S,DeQueue(Q)); while(!StackEmpty(T))
Push(S,Pop(T)); }
5/15