第3章 栈和队列

注意：1.本次作业可以不抄题，只写出题号和答案即可； 2. 9月29日上午交作业。

一 选择题

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

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

2. 在作进栈运算时,应先判别栈是否( ① B ),在作退栈运算时应先判别栈是否( ② A )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ B )。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ D )分别设在这片内存空间的两端,这样,当( ⑤ C )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点.

B. 其中一个栈的栈顶到达栈空间的中心点.

C. 两个栈的栈顶在栈空间的某一位置相遇.

D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.

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

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

4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。

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

5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( D )。

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

6. 有六个元素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 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..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ B ）。

A. |top[2]-top[1]|=0 B. top[1]-1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 9. 栈在（ D ）中应用。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 10. 表达式a*(b+c)-d的后缀表达式是( B )。

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

解析：表达式 a*(b+c)-d是中缀表达式，转化成二叉树后，它是中序遍历的结果 二叉树如下图：

______(-)_________ _____/___\\________ ____(*)__(d)______ ____/__\\__________ __(a)__(+)________ ______/___\\_______ ____(b)___(c)_____

后缀表达式，就是后序遍历该二叉树，所得到的序列,也就是：abc+*d- 同样的道理，前缀表达式是前序遍历二叉树，所得到的序列，是：-*a+bcd

11. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 12. 用链接方式存储的队列，在进行删除运算时（ D ）。

A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改

PS：栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。

队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表，在进行链队列插入和删除操作时，只需要修改尾指针或头指针。删除唯一元素时，要修改头指针和尾指针；大多数只修改头指针。

13. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（C ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表

14. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 15. 循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)

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

17. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。

A. (rear+1) MOD n=front B. rear=front

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

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

19. 栈的特点是（ ① ）,队列的特点是（ ② ）,栈和队列都是（ ③ ）。若进栈序列为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

20. 设栈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

21. 用单链表表示的链式队列的队头在链表的（ ）位置。 A．链头 B．链尾 C．链中

二、填空题

1．栈运算遵循_______的原则。

2．_______是限定在表尾进行插入，在表头进行删除操作的线性表。 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。

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

5．在作进栈运算时应先判别栈是否_(1) _;在作退栈运算时应先判别栈是否_(2) _；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3) _。 6. 多个栈共存时，最好用_______作为存储结构。

7. 顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。 8. 循环队列的引入，目的是为了克服_______。 9．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是： _____ 10．________又称作先进先出表。

11．区分循环队列的满与空，只有两种方法，它们是______和______。

12. 设循环队列存放在向量sq.data[0:M]中，队头指针sq.front，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。 13．表达式求值是_______应用的一个典型例子。

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

15. 在具有n个单元的循环队列中，队满时共有_______个元素。

三、判断题

1、在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，则队列为满的条件是front＝＝rear。（ ） 2、在栈空的情况下，不能做退栈运算。（ ）

3、用一个带头结点的链表表示队列Q，front指向表头结点，rear指向表尾，则执行出队操作时front不变。（ ）

4、循环队列只能用数组实现，而不能用链表实现。（ ） 5. 在表结构中最常用的是线性表，栈和队列不太常用。（ ）

6. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（ ）