我考研的那会儿, 研究北大计算机系历年考研的试题, 发现几乎每年都会很常规的问一道选择题 给定进栈序列是 123456, 问选项中哪个是不可能的出栈序列的题目. 我觉得这个题超级简单, 标准解法应该满天飞, 可是就昨天, 还有一个刚考了研的哥们给我发信问这道题的“快速解法”. 我想想也是, 北大出的那本离散数学的教材上, 的确是没有讲怎么去算, 我也没有翻过其他的国内教材, 不知道哪本教材覆盖到了. 不过当时和我一起考研的同学, 看了很多参考书, 似乎也都不知道这个方法, 我还讲给他们听过. (如果哪位读者知道国内哪本教材讲到一下的方法的,可以提醒我一下)
方法不是我的, 是TAoCP 的. 我就直接抄书了. 参见 TAOCP 第一卷 2.2.1 习题 5.
- [M28] Show that it is possible to obtain the permutation \(p\_1 p\_2 \cdots p\_n\) from \(1 2 \cdots n\) using a stack if and only if there are no indices \(i< j < k\) such that \(p\_j < p\_k < p\_i\).
下面是随便拷贝的网上的几条考研题 (http://www.vipkaoyan.com/dl-149-4039-0-8587.html)
瞬间可以看出答案分别为:
D, B, D, D.
- 设栈的输入序列是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 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，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分)】
- 某堆栈的输入序列为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 是大宝藏, 这废话就无须多说了.