第3章 栈和队列
一 选择题
1. 对于栈操作数据的原则是（ B ）。【青岛大学 2001 五、2（2分）】
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. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.
【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】
3. 一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。
A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】
4. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】
5. 若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3，?，pN,若pN是n，则pi是( D)。
A. i B. n-i C. n-i+1 D. 不确定
【南京理工大学 2001 一、1（1.5分）】 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 【北方交通大学 2001 一、3（2分）】
7. 设栈的输入序列是1，2，3，4,则（ D）不可能是其出栈序列。【中科院计算所2000一、10(2分)】
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，则下列序列中不可能是栈的输出序列的是（B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】
9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。
A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】
10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是
（ D ）。
A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b
【北京航空航天大学 2000 一、3（2分）】【北京邮电大学 1999 一、3（2分）】 11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ D ）。
A．fedcba B. bcafed C. dcefba D. cabdef 【南京理工大学 1996 一、9（2分）】
12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( C )。
A．XYZ B. YZX C. ZXY D. ZYX 【南京理工大学 1997 一、5（2分）】
13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（B ）【中山大学 1999 一、8(1分)】
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进栈的正确操作是( C )。
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 【南京理工大学 1998 一、13（2分）】
15. 若栈采用顺序存储方式存储，现两栈共享空间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]
【南京理工大学 1999 一、14（1分）】 16. 栈在（ D ）中应用。【中山大学 1998 二、3（2分）】
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 17. 一个递归算法必须包括（ B ）。【武汉大学 2000 二、2】
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分
18. 执行完下列语句段后，i值为：（B ）【浙江大学 2000 一 、6 (3分)】
int f(int x)
{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));
A．2 B. 4 C. 8 D. 无限递归 19. 表达式a*(b+c)-d的后缀表达式是( B )。【南京理工大学 2001 一、2（1.5分）】
A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 20. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ D ），其中^为乘幂 。
A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(-
【青岛大学 2000 五、5（2分）】
21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。
A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈
【西安电子科技大学 1996 一、6（2分）】
22. 用链接方式存储的队列，在进行删除运算时（ D ）。【北方交通大学 2001 一、12（2分）】
A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。【北京理工大学 2001 六、3（2分）】
A．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改
24. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。
A．队列 B．多维数组 C．栈 D. 线性表 【福州大学 1998 一、1（2分）】
25. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。【北京工商大学 2001 一、2（3分）】
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 )。【南京理工大学 2001 一、5（1.5分）】
A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front
27. 循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。【中山大学 1999 一、6（1分）】
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的值分别为多少？( B )【浙江大学1999 四、1(4分)】
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
29. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ BD ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对
【西安交通大学 1996 三、3 (3分)】
30. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( C )。【西安电子科技大学 1996 一、5（2分）】
A. 1234 B. 4132 C. 4231 D. 4213 31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ B ）。
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front 【南京理工大学 1999 一、16（2分）】 32. 栈和队列的共同点是（ C ）。【燕山大学 2001 一、1（2分）】
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点
33. 栈的特点是（ ① B）,队列的特点是（ ② A ）,栈和队列都是（ ③C ）。若进栈
序列为1,2,3,4 则（ ④ C）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ ⑤ F ）是一个出队列序列。【北方交通大学 1999 一、1（5分）】
①, ②: 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. 栈和队都是（ C ）【南京理工大学 1997 一、3（2分）】
A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构
35. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。
A． 6 B. 4 C. 3 D. 2 【南京理工大学 2000 一、6（1.5分）】
36. 用单链表表示的链式队列的队头在链表的（A ）位置。【清华大学 1998 一、1（2分）】
A．链头 B．链尾 C．链中
37. 依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？【哈尔滨工业大学 2000 七（8分）】AD
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}
二 判断题
1. 消除递归不一定需要使用栈，此说法（ √ ）
【中科院计算所 1998 二、2（2分）】【中国科技大学 1998 二、2（2分）】 2. 栈是实现过程和函数等子程序所必需的结构。（√ ）【合肥工业大学 2000 二、2（1分）】
3. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。（√ ）【青岛大学 2000 四、2（1分）】
4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ √ ）【上海海运学院 1998 一、4（1分）】
5. 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ × ）【北京邮电大学 1999 二、4（2分）】
6. 有n个数顺序（依次）进栈，出栈序列有Cn种，Cn=[1/（n+1）]*（2n）!/[(n!)*(n!)]。（ √ ）
【北京邮电大学 1998 一、3（2分）】 7. 栈与队列是一种特殊操作的线性表。（√ ）【青岛大学 2001 四、3 （1分）】 8. 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. （√ ）
【上海海运学院1995 一、2（1分） 1997 一、3（1分）】 9. 栈和队列都是限制存取点的线性结构。（ √ ）【中科院软件所 1999 六、(5)（2分）】 10．若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。（ × ）
【上海海运学院 1999 一、3（1分）】
11. 任何一个递归过程都可以转换成非递归过程。（ √ ）【上海交通大学 1998一、3（1分）】
12. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（ ×）
【上海交通大学 1998 一、4（1分）】
13. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ × ）
【上海海运学院 1998 一、3（1分）】 14. 通常使用队列来处理函数或过程的调用。（ × ）【南京航空航天大学 1997 一、5（1分）】
15. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ √）【上海交通大学 1998 一、2】
16. 循环队列通常用指针来实现队列的头尾相接。（ × ）【南京航空航天大学 1996 六、1（1分）】
17. 循环队列也存在空间溢出问题。（√ ）【青岛大学 2002 一、2 （1分）】 18. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（×）【长沙铁道学院1997一、5(1分)】
19. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ √ ）【北京邮电大学2002一、3(1分)】
20. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（√ ）
【上海海运学院 1996 一、2（1分） 1999 一、2（1分）】
三 填空题
1．栈是____操作受限（或限定仅在表尾进行插入和删除操作）___的线性表，其运算遵循______后进先出_的原则。【北京科技大学 1997 一、3】
2．_____栈__是限定仅在表尾进行插入或删除操作的线性表。【燕山大学 1998 一、3 （1分）】
3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是__3 1 2_____。【中国人民大学2001一、1(2分)】
4. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是___3 1 2____，而栈顶指针值是____两栈顶指针相邻（即值之差的绝对值为1）___H。设栈为顺序栈，每个元素占4个字节。【西安电子科技大学 1998 二、1（4分）】
5. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为____0___，栈2空时 ，top[2]为__n+1_____，栈满时为___top[1]+1=top[2]____。
【南京理工大学 1997 三、1（3分）】
6．两个栈共享空间时栈满的条件___两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）。____。【中山大学 1998 一、3（1分）】
7．在作进栈运算时应先判别栈是否_(1满)_;在作退栈运算时应先判别栈是否_(空2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3n)_。
为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(栈底4)_分别设在内存空间的两端，这样只有当_(5两栈顶指针相邻（即值之差的绝对值为1)_时才产生溢出。【山东工业大学 1994 一、1（5分）】