栈和队列

第3章 栈和队列

一、选择题

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

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

2. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定 B. n-i+1 C. i D. n-i

3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）

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. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）

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

5. 若栈采用顺序存储方式存储，现两栈共享空间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]

6. 栈在（ ）中应用。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ

7. 表达式a*(b+c)-d的后缀表达式是( )。

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

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

A．线性表的顺序存储结构 B. 队列

C. 线性表的链式存储结构 D. 栈

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

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

C．(front-rear+m)%m D．(rear-front)%m

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

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

参考答案

第1题 正确答案是B 栈的特点后进先出

第2题 正确答案是B 栈的特点是后进先出，输出的第一个是n，说明全压入栈里了，出来应是倒序。

第3题 正确答案是C

第4题 正确答案是B

第5题 正确答案是B 两栈公用存储空间，栈满时栈顶指针相邻。

第6题 正确答案是D A,B,C三项都对数据涉及后存的先用形式，因此采用栈做存储结构。

第7题 正确答案是B 根据表达式构造二叉树，在进行后序遍历。

第8题 正确答案是D 括号匹配符合右括号和最后出现的左括号匹配，满足后存的先使用原则，采用栈做为存储结构。

第9题 正确答案是A 若rear>=front 则元素个数为rear-front

若rear

第10题 正确答案是B 出队操作队头增1，入队操作队尾增1.

二、填空题

1.栈是_______的线性表，其运算遵循_______的原则。

2.顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。

3．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。 4．区分循环队列的满与空，只有两种方法，它们是______和______。

5．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是： M=

_______。

6. 算术表达式求值的流程，其中OPTR为算术符栈，OPND为操作数栈，precede(oper1，oper2)是比较运算符优先级别的函数，operate(opnd1,oper,opnd2)为两操作数的运算结果函数。（#表示运算起始和终止符号）

operandtype exp_reduced( )

{

INITSTACK(OPTR);PUSH(OPTR"#")；INITSTACK(OPND);scanf(w)；

WHILE NOT((w='#’) AND (GETTOP(OPTR)='#'))

IF (NOT w in op) PUSH(OPND,w);

ELSE CASE precede(GETTOP(OPTR),w)

{ '<':[(1)_______; scanf(w);]

'=':[(2)_______; scanf(w);];

'>':[theta:=POP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)__ _____；]

}

RETURN(GETTOP(OPND));

}

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

8.循环队列的引入，目的是为了克服_______。

9.循环队列Q中，队列的存储空间为M ,入队操作时队尾指针的变化是_______。

10.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。

参考答案

第1题 正确答案是允许在表的一端操作 后进先出

第2题 正确答案是data[++top]=x； 栈顶指针指向栈顶元素的表示方法。

第3题 正确答案是先进先出

第4题 正确答案是牺牲一个存储单元 设标记 牺牲一个存储单元时当队尾再增1就和队头相等我们认为队列满了。设标记是当出现队头指针和队尾指针相等时，看设定的标志位，若为1，标志队列满了。

第5题 正确答案是(M+1)%N 若控制M的范围采用取余运算是最简单的方法，对N取余取值范围就为0..N-1。

第6题 正确答案是（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b）） 表达式求值算法，读入的是操作符就和操作符栈顶元素比较，级别高压栈，级别相等即为括号，将栈里的左括号弹出，级别低栈里的操作符运算，弹出两个操作数，一个操作符运算。

第7题 正确答案是23 100CH 压栈栈顶指针增4，出栈栈顶指针减4。

第8题 正确答案是假溢出时大量移动数据元素。 顺序队列有假溢出现象，即随着不断的入队，队列的队尾指针达到了最大容量值，认为队列已满，尽管随着不断的出队，队列里还有可用空间，这种现象被称作假溢出现象。采用循环队列循环利用队列的有效空间，避免了这一现象。

第9题 正确答案是Q.rear=(Q.rear+1)%M 入队操作队尾指针增一，为了循环利用要对存储空间个数取余运算。

第10题 正确答案是S×SS×S××

三、应用题

1. 假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。

（1）试指出判别给定序列是否合法的一般规则。

（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。

2. 试证明：若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i

参考答案

第1题 （1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。

（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的S×S×S×操作序列；对于合法序列BAC，我们使用SS××S×操作序列。

第2题 如果ipj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这就说明，对于i

四、算法题

1.从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$

2.请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。

参考答案

第1题 逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。

float expr( )

//从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。

｛float OPND[30]; // OPND是操作数栈。

init(OPND); //两栈初始化。

float num=0.0; //数字初始化。

scanf (“%c”,&x);//x是字符型变量。

while(x!=’$’)

{switch

{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’) //拼数

if(x!=’.’) //处理整数

{num=num*10+（ord(x)-ord(‘0’)）; scanf(“%c”,&x);}

else //处理小数部分。