第三章 栈和队列(作业)
一、判断题
1. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。
2. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈
的栈底分别设在这片内存空间的两端。 3. 栈与队列是一种特殊操作的线性表。
4. 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1 。
5. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。 6. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 7. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。 8. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。 二、填空题
1. 栈是（ ）的线性表，其运算遵循（ ）的原则。 2. （ ）是限定仅在表尾进行插入或删除操作的线性表。
3. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经
过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是（ ） ，而栈顶指针值是（ ） H。设栈为顺序栈，每个元素占4个字节。
4. 用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342
出栈顺序，相应的S和X的操作串为（ ） 。 5. （ ）又称作先进先出表。
6. 区分循环队列的满与空，只有两种方法，它们是（ ）和（
）。
7. 设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的
条件为 （ ） 。
8. 表达式求值是（ ） 应用的一个典型例子。
9. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则
当前队列的元素个数是（ ）。
三、选择题
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. 在作进栈运算时,应先判别栈是否(①),在作退栈运算时应先判别栈是否(②)。当栈中
元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③)。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 (④)分别设在这片内存空间的两端,这样,当(⑤)时，才产生上溢。
①②: A.空 B. 满 C. 上溢 D.下溢 ③: A. n-1 B. n C. n+1 D.n/2
④: A. 长度 B. 深度 C. 栈顶 D.栈底
⑤: A. 两个栈的栈顶同时到达栈空间的中心点。 B. 其中一个栈的栈顶到达栈空间的中心点。 C. 两个栈的栈顶在栈空间的某一位置相遇。
D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底。
5. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是
（ ）。
A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4
6. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其
中^为乘幂 。
A. 3,2,4,1,1；#*^(+*- B. 3,2,8；#*^- C. 3,2,4,2,2；#*^(- D. 3,2,8；#*^(-
7. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
8. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列
中的元素个数为（ ）。
A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m
9. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1) mod (m+1)
10. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
11. 栈的特点是（①）,队列的特点是（②）,栈和队列都是（③）。若进栈序列为1,2,3,4 则
（④）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（⑤）是一个出队列序列。栈和队列的共同点是（⑥）。
①②: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 ③: A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构
④⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4 ⑥ A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点
四、写出下列程序段的输出结果
1、 （栈的元素类型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);
2、 （队列中的元素类型QElemType为Char） Void main() {
Queue Q; InitQueue(Q); char x=‘e’,y=‘c’;
EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a’); while(!QueueEmpty(Q)) { DeQueue(Q,y); Printf(y); } Printf(x);
五、简述算法的功能 1、（栈的元素类型SElemType为int） Status sf1(stack s,int e) {
stack t; int d;
initstack(T);