第3章-栈及队列习题.doc

第3章 栈和队列
一 选择题
1. 对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。
①, ②: 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）个元素是（ ）。
A. 不确定 B. n-i+1 C. i D. n-i
4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的
5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。
A. i B. n-i C. n-i+1 D. 不确定
6. 有六个元素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
7. 设栈的输入序列是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，
8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
9. 设一个栈的输入序列是 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
10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。
A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b
11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ ）。
A．fedcba B. bcafed C. dcefba D. cabdef
12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。
A．XYZ B. YZX C. ZXY D. ZYX

13. 输入序列为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
14. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。
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
16. 栈在（ ）中应用。
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ
19. 表达式a*(b+c)-d的后缀表达式是( )。
A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd
20. 表达式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；(*^(-
25. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．(rear-front+m)%m B．rear-front+1
C．(front-rear+m)%m D．(rear-front)%m
26. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。
A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front
27. 循环队列存储在数组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)
28. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front
32. 栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
33. 栈的特点是（ ① ）,队列的特点是（ ② ）,栈和队列都是（ ③ ）。若进栈序列为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
34. 栈和队都是（ ）
A．顺序存储的线性结构 B. 链式存储的非线性结构
C. 限制存取点的线性结构 D. 限制存取点的非线性结构
37. 依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？
A．{d ，e，c，f，b，g，a} B. {f，e，g，d，a，c，b}
C. {e，f，d，g，b，c，a} D. {c，d，b，e，f，a，g}

二 判断题
2. 栈是实现过程和函数等子程序所必需的结构。（ √ ）
7. 栈与队列是一种特殊操作的线性表。（√ ）
8. 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. （√ ）
9. 栈和队列都是限制存取点的线性结构。（√ ）
10．若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。（× ）
13. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ × ）
14. 通常使用队列来处理函数或过程的调用。（ × ）
16. 循环队列通常用指针来实现队列的头尾相接。（ ×）
18. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（× ）
19. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（√ ）
20. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ √ ）

三 填空题
1．栈是_______的线性表，其运算遵循_______的原则。
2．_______是限定仅在表尾进行插入或删除操作的线性表。
3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_____
4. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。
7．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。
9．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。
10. 顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。
12. 循环队列的引入，目的是为了克服_______。
14．________又称作先进先出表。
15. 队列的特点是_______。
16．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。
17. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。
18．区分循环队列的满与空，只有两种方法，它们是______和______。
19．设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为_______。
22．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。
23．设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为_______。

四 应用题
1. 名词解释：栈。
2. 名词解释：队列
3. 什么是循环队列？
5. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
6. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。
7. 若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E、D和D、B、A、C、E？为什么？
8. 设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。
9. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？
11. 设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。
（1） 能否得到输出顺序为325641的序列。
（2） 能否得到输出顺序为154623的序列。
22. 画出对算术表达式A-B*C/D-E↑F求值时操作数栈和运算符栈的变化过程。