我考研的那会儿, 研究北大计算机系历年考研的试题, 发现几乎每年都会很常规的问一道选择题 给定进栈序列是 123456, 问选项中哪个是不可能的出栈序列的题目. 我觉得这个题超级简单, 标准解法应该满天飞, 可是就昨天, 还有一个刚考了研的哥们给我发信问这道题的“快速解法”. 我想想也是, 北大出的那本离散数学的教材上, 的确是没有讲怎么去算, 我也没有翻过其他的国内教材, 不知道哪本教材覆盖到了. 不过当时和我一起考研的同学, 看了很多参考书, 似乎也都不知道这个方法, 我还讲给他们听过. (如果哪位读者知道国内哪本教材讲到一下的方法的,可以提醒我一下)

方法不是我的, 是TAoCP 的. 我就直接抄书了. 参见 TAOCP 第一卷 2.2.1 习题 5.

  1. [M28] Show that it is possible to obtain the permutation from using a stack if and only if there are no indices such that .

下面是随便拷贝的网上的几条考研题 (http://www.vipkaoyan.com/dl-149-4039-0-8587.html)

瞬间可以看出答案分别为:

D, B, D, D.

  1. 设栈的输入序列是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,

【中科院计算所2000一、10(2分)】

  1. 一个栈的输入序列为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

【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2(2分)】

  1. 设一个栈的输入序列是 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

【合肥工业大学 2001 一、1(2分)】

  1. 某堆栈的输入序列为a, b,c ,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分)】

TAoCP 是大宝藏, 这废话就无须多说了.