●设将整数1、2、3、4依次进栈,只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下述问题:

Question

●设将整数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

Answer 1

正确答案：A,B,A
【解析】出栈序列为1、3、4。
序列1、4、2、3不可能得到。因为4和2之间隔了3，当4出栈后，栈顶元素是3，而2在3的下面。
根据栈的数学性质，n个元素的出栈序列数目恰好符合卡塔南数列，即

因此4个元素的出栈序列数为：

这14种出栈序列如下：
1234  1243  1324  1342  1432
2134  2143  2314  2341  2431
3214  3241  3421  4321