4G Spaces

出栈序列题的终极解法

Comments

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

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

  1. [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. 设栈的输入序列是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 是大宝藏,　这废话就无须多说了.

comments powered by Disqus