内容发布更新时间 : 2024/5/3 8:57:42星期一 下面是文章的全部内容请认真阅读。

第三章 栈和队列(作业)

一、判断题

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);