NOIP 普及 2017 第一轮 第 16 题：判断不可能的出栈序列

题目

对于入栈顺序为 $a, b, c, d, e, f, g$ 的序列，下列（ ）不可能是合法的出栈序列。

选项

• A. $a, b, c, d, e, f, g$
• B. $a, d, c, b, e, g, f$
• C. $a, d, b, c, g, f, e$
• D. $g, f, e, d, c, b, a$

答案

C

题解

考点定位

本题考「出栈序列合法性判断」，对应大纲 3.2.1 栈（难度【3】）。

解题过程

逐项模拟。判定规则：输出某个元素前，把它之前尚未入栈的元素全部入栈，然后看它是否在栈顶；不在栈顶且它之上还压着别的元素，就卡死。

• A $a,b,c,d,e,f,g$：每个元素进栈后立即出栈，合法。
• B $a,d,c,b,e,g,f$：$a$ 进即出；压入 $b,c,d$ 后依次弹 $d,c,b$；$e$ 进即出；压入 $f,g$ 后弹 $g,f$，合法。
• C $a,d,b,c,g,f,e$：$a$ 进即出；要出 $d$，需压入 $b,c,d$，弹 $d$ 后栈内自底向上是 $b,c$；下一个要出 $b$，但栈顶是 $c$，而 $c$ 在 $b$ 之前不可能弹出——卡死，不合法。
• D $g,f,e,d,c,b,a$：$a$ 到 $g$ 全部入栈后依次弹出，正是逆序，合法。

所以选 C。

易错提醒

① 模拟时栈的每一步状态要写清楚：C 项弹掉 $d$ 后栈是「底 $b$、上 $c$」，此后想先出 $b$ 就再无机会；

② 一个序列合法的充要条件是不出现「$x$ 在 $y$ 之前入栈、$x$ 在 $y$ 之后出栈、但又要求 $y$ 先出」这类逆序冲突，模拟法是最稳的判法。