栈的初赛练习题
Description
1. 若已知一个栈的入栈顺序是 1，2，3，…，n，其输出（出栈）序列为 P1，P2，P3，…，Pn，若 P1 是 n，则 Pi 是( )。A. i
B. n - 1
C. n - i + 1
D. 不确定
2. 以下哪一个不是栈的基本运算( )。
A. 删除栈顶元素
B. 删除栈底的元素
C. 判断栈是否为空
D. 将栈置为空栈
3. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。
A. 队列
B. 多维数组
C. 栈
D. 线性表
4. 已知元素（8，25，14，87，51，90，6，19，20），问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8 在 51 前面；90 在 87 的后面；20 在 14 的后面；25 在 6 的前面；19 在 90 的后面。（ ）。
A. 20，6，8，51，90，25，14，19，87
B. 51，6，19，20，14，8，87，90，25
C. 19，20，90，8，6，25，51，14，87
D. 6，25，51，8，20，19，90，87，14
5. [多选]设栈 S 的初始状态为空，元素 a, b, c, d, e, f, g 依次入栈，以下出栈序列不可能出现的有（ ）。
A. a, b, c, e, d, f, g
B. b, c, a, f, e, g, d
C. a, e, c, b, d, f, g
D. d, c, f, e, b, a, g
6. 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口（出入同一口）。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出，出”。假设车辆入站的顺序为 1，2，3，……，则车辆出站的顺序为（ ）。
A. 1, 2, 3, 4, 5
B. 1, 2, 4, 5, 7
C. 1, 4, 3, 7, 6
D. 1, 4, 3, 7, 2
7. 设栈 S 的初始状态为空，元素 a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ ）。
A. a, b, c, e, d
B. b, c, a, e, d
C. a, e, c, b, d
D. d, c, e, b, a
8. 设栈 S 的初始状态为空，元素 a，b，c，d，e，f 依次入栈 S，出栈的序列为 b，d，c，f，e，a，则栈 S 的容量至少应该是（ ）。
A. 6
B. 5
C. 4
D. 3
9. 设有一顺序栈 S，元素 s1, s2, s3, s4, s5, s6 依次进栈，如果有 6 个元素出栈的顺序是 s2, s3, s6, s5, s4, s1，则栈的容量至少是（ ）。
A. 2
B. 3
C. 4
D. 5
10. 设有一个顺序栈，初始时栈中包含 3 个元素，从栈底到栈顶依次为 a1, a2, a3。另有元素 a4 尚未入栈，但可以在任意时刻入栈一次。下列 4 个序列中，不可能通过合法的入栈和出栈操作得到的出栈序列是（ ）。
A. a3, a1, a4, a2
B. a3, a2, a4, a1
C. a3, a4, a2, a1
D. a4, a3, a2, a1
11. 若一个栈的输入序列为 1,2,3,….n，输出序列的第一个元素是 i，则第 j 个输出元素是（ ）。
A. i - j - 1
B. i - j
C. j - i + 1
D. 不确定
12. 设一个栈的输入序列是 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
13. 【noip2017 提高组】2.对于入栈顺序为 a, b, c, d, e, f, g 的序列，下列( )不可能是合法的出栈序列。【多选】
A. a,b,c,d,e,f,g
B. a,d,c,b,e,g,f
C. a,d,b,c,g,f,e
D.g,f,e,d,c,b,a
14. 【noip2015 普及组】15. 今有一空栈 S，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为 （ ）
A. f
B. c
C. a
D. b
15. 栈中元素的进出原则是（ ）
A. 先进先出
B. 后进先出
C. 栈空则进
D. 栈满则出
16. 给定一个空栈，支持入栈和出栈操作。若入栈操作的元素依次是 1 2 3 4 5 6，其中 1 最先入栈，6 最后入栈，下面哪种出栈顺序是不可能的？（ ）
A. 6 5 4 3 2 1
B. 1 6 5 4 3 2
C. 2 4 6 5 3 1
D. 1 3 5 2 4 6
17. 有 6 个元素，按照 6,5,4,3,2,1 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。
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
18. 【CSP 2021 入门级5】对于入栈顺序为a,b,c,d,e 的序列，下列（ ）不是合法的出栈序列。
A. a,b,c,d,e
B. e,d,c,b,a
C. b,a,c,d,e
D. c,d,a,e,b