NOIP 普及 2010 第一轮 第 15 题：根据出栈条件判断不可能的出栈元素

题目

元素 $R_1,R_2,R_3,R_4,R_5$ 入栈的顺序为 $R_1,R_2,R_3,R_4,R_5$。如果第 $1$ 个出栈的是 $R_3$，那么第 $5$ 个出栈的不可能是（   ）。

选项

• A. $R_1$
• B. $R_2$
• C. $R_4$
• D. $R_5$

答案

B

题解

考点定位

本题考「栈序列约束」，对应大纲 3.2.1 栈与队列（难度【2】）。

解题过程

$R_3$ 第一个出栈，说明此刻栈内自底向上是 $R_1$、$R_2$（$R_2$ 在上），$R_4$、$R_5$ 还没入栈。

此后任何时刻都有一条硬约束：$R_1$ 在 $R_2$ 下方，$R_1$ 必须晚于 $R_2$ 弹出。

第 5 个出栈就是最后一个出栈。若最后出栈的是 $R_2$，则 $R_1$ 必须在 $R_2$ 之前弹出，与硬约束矛盾。所以第 5 个出栈的不可能是 $R_2$。

再验证其余三个选项都可能，给出完整出栈序列即可：

• $R_1$ 最后：出栈序 $3,2,4,5,1$；
• $R_4$ 最后：出栈序 $3,2,1,5,4$；
• $R_5$ 最后：出栈序 $3,2,1,4,5$。

（例如 $3,2,4,5,1$：压入 $1,2,3$ 弹 $3$，弹 $2$，压 $4$ 弹 $4$，压 $5$ 弹 $5$，最后弹 $1$。）

所以选 B。

易错提醒

① 判断「不可能」：抓住入栈顺序决定的不变式（$R_1$ 晚于 $R_2$ 出栈），让候选元素垫底看是否冲突；

② 判断「可能」：必须写出一个完整的合法出栈序列来证明，别凭感觉；

③ $R_3$ 先出之后，$R_4$、$R_5$ 何时入栈是自由的，这是构造序列时的活动余地。