软考中级
设将整数1、2、3、4依次进栈，只要出栈时栈非空，则可将出栈操作按任何次序夹人其中；请回答下述问题：1．当人、出栈次序为Push(1)，Pop()，Push(2)，Push(3)，Pop()，Push(4)，Pop()，出栈的数字序列为何?(这里Push(i)表示i进栈，Pop()表示出栈)(26)2．能否得到出栈序列1、4、2、3和1、4、3、2?答案为(27)。3．请分析研究1、2、3、4的24种排列中，(28)序列是可以通过相应的入、出栈操作得到的。A．1，3，4B．1，4，2，3C．1，4，3D．
题目
设将整数1、2、3、4依次进栈，只要出栈时栈非空，则可将出栈操作按任何次序夹人其中；请回答下述问题：
1．当人、出栈次序为Push(1)，Pop()，Push(2)，Push(3)，Pop()，Push(4)，Pop()，出栈的数字序列为何?(这里Push(i)表示i进栈，Pop()表示出栈)(26)
2．能否得到出栈序列1、4、2、3和1、4、3、2?答案为(27)。
3．请分析研究1、2、3、4的24种排列中，(28)序列是可以通过相应的入、出栈操作得到的。
A．1，3，4
B．1，4，2，3
C．1，4，3
D．3，4，1
相似问题和答案
第1题：
设输入序列为1、2、3、4、5，依次执行进栈、进栈、进栈、出栈、进栈、进栈、出栈、出栈，则栈顶栈底分别是______。
A．5和4
B．4和3
C．3和2
D．2和1
解析：栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈项(top)，表头端称为栈底(bottom)。故栈是后进先出(LIFO)的线性表。通常称栈的节点插入为进栈(Push)，栈的节点的删除为出栈(Pop)。
第2题：
若push、pop分别表示入栈、出栈操作，初始栈为空且元素1、2、3依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为(29)。
A．321
B．213
C．231
D．123
解析：栈的运算特点为在同一端插入和删除元素，即先入后出，总是栈顶元素先出栈，新元素总是压在栈顶元素之上并成为栈顶元素。初始栈为空，如下图(a)所示。对于元素 1、2、3，依照操作序列push、push、pop、pop、push、pop，可以得到出栈序列213，其过程为：第一个push操作将元素1压入栈中，如下图(b)所示：第二个push操作将元素2压入栈中，如下图(c)所示：第一个pop将栈顶元素2弹出栈，新栈顶元素为1，如下图(d)所示；第二个pop将栈顶元素1弹出栈，导致栈空，如下图(e)所示：其后的push和pop分别将元素3压入和弹出栈，操作结果如下图(f)和(g)所示。
第3题：
A、5，4，3，2，1，6
B、2，3，5，6，1，4
C、3，2，5，4，1，6
D、1，4，6，5，2，3
第4题：
若pllsh、pop分别表示入栈、出栈操作，初始栈为空且元素1、2、3依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为 ______。
A．321
B．213
C．231
D．123
A．
B．
C．
D．
第5题：
[算法描述]
#define maxsize 栈空间容量
void InOutS(int s[maxsize])
//s是元素为整数的栈，本算法进行入栈和退栈操作。
{int top=0; //top为栈顶指针，定义top=0时为栈空。
for(i=1; i<=n; i++) //n个整数序列作处理。
{cin>>x); //从键盘读入整数序列。
if(x!=-1) // 读入的整数不等于-1时入栈。
{if(top==maxsize-1){cout<<“栈满”<
｝
else //读入的整数等于-1时退栈。
{if(top==0){ cout<<“栈空”<
}//算法结束。
第6题：
n个元素依次全部进入栈后，再陆续出栈并经过一个队列输出。那么，(36)。
A．元素的出队次序与进栈次序相同
B．元素的出队次序与进栈次序相反
C．元素的进栈次序与进队次序相同
D．元素的出栈次序与出队次序相反
解析：本题考查栈和队列的数据结构。栈是先进后出的线性表，n个元素全部进入栈后再依次出栈，则得到原序列的逆序。队列是先进先出的线性表，元素的进入次序与输出次序相同，因此，n个元素先后经过栈和队列，得到的序列与进入栈的序列正好相反。
第7题：
若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )
A．3,2,6,1,4,5
B．3,4,2,1,6,5
C．1,2,5,3,4,6
D．5,6,4,2,3,1
第8题：
●设将整数1、2、3、4依次进栈，只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
1.当入、出栈次序为Push (1) ，Pop ()，Push (2) ，Push (3) ，Pop()，Push (4) ，Pop()，出栈的数字序列为何?(这里Push(i)表示i进栈，Pop()表示出栈) (26)
2.能否得到出栈序列1、4、2、3和1、4、3、2？答案为 (27) 。
3.请分析研究1、2、3、4的24种排列中， (28) 序列是可以通过相应的入、出栈操作得到的。
(26) A．1，3，4
B．1，4，2，3
C．1，4，3
D．3，4，1
(27) A．可以
B．不可以
C．不确定
D．随机获得
(28) A．1，3，2，4
B．4，2，3，1
C．2，4，1，3
D．3，1，4，2
【解析】出栈序列为1、3、4。
序列1、4、2、3不可能得到。因为4和2之间隔了3，当4出栈后，栈顶元素是3，而2在3的下面。
根据栈的数学性质，n个元素的出栈序列数目恰好符合卡塔南数列，即
这14种出栈序列如下：
1234 1243 1324 1342 1432
2134 2143 2314 2341 2431
3214 3241 3421 4321
第9题：
n个元素依次全部进入栈后，再陆续出栈并经过一个队列输出。那么，______。
A．元素的出队次序与进栈次序相同
B．元素的出队次序与进栈次序相反
C．元素的进栈次序与进队次序相同
D．元素的出栈次序与出队次序相反
A．
B．
C．
D．
第10题：
若push、pop分别表示入栈、出栈操作，初始栈为空且元素3、2、1依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为__(3)__。
A.321
B.213
C.231
D.123
经过前两个操作push、push之后，栈里有元素3、2且2在栈顶。接着再进行pop、pop之后，依次把2、3出栈了，栈空了。再接着push、pop，元素1进栈又出栈。因此，最终得到的出栈顺序是231。