数据结构及应用算法教程习题第四章 栈和队列

第四章 栈和队列

一、选择题

1．对于栈操作数据的原则是（B ）。

A．先进先出 B．后进先出 C．后进后出 D．不分顺序 2．一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。

A．不确定 B．n-i+1 C．i D．n-i 3．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）

A．5 4 3 6 1 2 B．4 5 3 1 2 6 C．3 4 6 5 2 1 D．2 3 4 1 5 6 4．设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A．1，2，4，3， B．2，1，3，4， C．1，4，3，2， D．4，3，1，2， E．3，2，1，4，

5．某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。

A．a，c，b，d B．b, c，d，a C．c, d，b, a D．d, c，a，b 6．设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。

A．XYZ B．YZX C．ZXY D．ZYX 7．输入序列为ABC，可以变为CBA时，经过的栈操作为（ B ） A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 8．若一个栈以向量V[1．．n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( C )。

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 10．栈在（ D ）中应用。

A．递归调用 B．子程序调用 C．表达式求值 D．A，Ｂ，Ｃ 11．一个递归算法必须包括（ B ）。

A．递归部分 B．终止条件和递归部分 C．迭代部分 D．终止条件和迭代部分 12．执行完下列语句段后，i值为：（ ） int f(int x)

{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));

A．2 B．4 C．8 D．无限递归 13．表达式a*(b+c)-d的后缀表达式是( B )。

A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd

14．设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。

A．线性表的顺序存储结构 B．队列 C．线性表的链式存储结构 D．栈

15．用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( A )。

A．仅修改队头指针 B．仅修改队尾指针

C．队头、队尾指针都要修改 D．队头,队尾指针都可能要修改

16．假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m

17．循环队列A[0．．m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( A )。

A．(rear-front+m)%m B．rear-front+1 C．rear-front-1 D．rear-front 18．循环队列存储在数组A[0．．m]中，则入队时的操作为（ C ）。 A．rear=rear+1 B．rear=(rear+1) mod (m-1) C．rear=(rear+1) mod m D．rear=(rear+1)mod(m+1)

19．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B )

A．1和 5 B．2和4 C．4和2 D．5和1 21．最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ B ）。

A．(rear+1) MOD n=front B．rear=front C．rear+1=front D．(rear-l) MOD n=front 22．栈和队列的共同点是（ C ）。

A．都是先进先出 B．都是先进后出 C．只允许在端点处插入和删除元素 D．没有共同点 23．栈和队都是（ C ）

A．顺序存储的线性结构 B．链式存储的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构

24．设栈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 二、填空题

1．_______是限定仅在表尾进行插入或删除操作的线性表。

2．设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。

4．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。 6．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。

7．循环队列的引入，目的是为了克服_______。 8．________又称作先进先出表。

9．已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 10．区分循环队列的满与空，只有两种方法，它们是______和______。 11．设循环队列用数组A[1．．M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为_______。

12．表达式求值是_______应用的一个典型例子。

13．循环队列用数组A[0．．m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。

14．设Q[0．．N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为_______。 三、应用题

1．有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？ 5．如果用一个循环数组q[0．．m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。 （1）编写实现队列的三个基本运算：判空、入队、出队 （2）队列中能容纳元素的最多个数是多少？

参考答案

一、选择题 1.B 2.B 3.C 4.D

5.D 6.C 7.B 8.C 9.B 10.D 11.B 12.B

13.B 14.D 15.D 16.A 17.A 18.D 19.B 20.C 21.B 22.C 23.C 24.C

二、填空题

1、栈 2、23 100CH 3、0 n+1 top[1]+1=top[2]

4、(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1）

5、链式存储结构 6、S×SS×S×× 7、假溢出时大量移动数据元素。 8、队列

9、s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s；

10、牺牲一个存储单元 设标记

11、（TAIL+1）MOD M=FRONT (数组下标0到M-1，若一定使用1到M，则取模为0者，值改取M

12、栈 13、（rear-front+m）% m； 14、（R-P+N）% N； 三、应用题

1、三个：CDEBA，CDBEA，CDBAE

2、借助栈结构，n个入栈元素可得到1/(n+1)((2n）！/（n!*n!）)种出栈序列。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种。但dabc和adbc是不可能得到的两种。 5、typedef struct

{elemtp q[m];

int front,count; //front是队首指针，count是队列中元素个数。 }cqnode; //定义类型标识符。

(1)判空：int Empty(cqnode cq) //cq是cqnode类型的变量

{if(cq.count==0) return(1)；else return(0); //空队列} 入队: int EnQueue(cqnode cq，elemtp x)

{if(count==m){printf(“队满\\n”)；exit(0); }

cq.q[(cq.front+count)%m]=x; //x入队

count++; return(1); //队列中元素个数增加1,入队成功。

}

出队: int DelQueue(cqnode cq)

{if (count==0){printf(“队空\\n”)；return(0);} printf(“出队元素”，cq.q[cq.front]); x=cq.q[cq.front];

cq.front=(cq.front+1)%m; //计算新的队头指针。

本文来源：https://www.bwwdw.com/article/v0ut.html