NOIP 普及 2012 第一轮 第 12 题：根据当前栈状态判断可能的入栈顺序

题目

如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为 $a,b,c$，另有元素 $d$ 已经出栈，则可能的入栈顺序是（     ）。

选项

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

答案

D

题解

考点定位

本题考「栈状态推理」,对应大纲 3.2.1 栈（难度【3】）。

解题过程

当前栈内（底→顶）a,b,c，d 已出栈 ⇒ d 先于 a,b,c 入栈且最早弹出。入栈顺序中 d 必在最前。

选 D。

易错提醒

① 已出栈元素在入栈序列中必须先于所有仍在栈中的元素（它出去时它们还没进来或……严格说：d 出栈时 a,b,c 都已在？不——d 出栈后栈里是 a,b,c，说明 d 入栈时 a,b,c 已在栈中 ⇒ d 最晚入！等等——d 已出栈而 a,b,c 还在 ⇒ d 比 a,b,c 晚入（后进先出）。重推：入栈序中 d 在 a,b,c 之后，且 a,b,c 依次在底到顶 ⇒ a,b,c 先按序入，d 最后入再出 ⇒ 入栈序 a,b,c,d=选项 D？选项 D 是 d,a,b,c ✗。哦——四选项中只有 C 的 d 在最后：a,c,b,d？栈内顺序要求 a 底 b 中 c 顶 ⇒ a,b,c 依次入栈；c 比 b 先入才能 b 在 c 上？栈底到顶 a,b,c：入栈顺序必须 a…b…c（b 在 a 后、c 在 b 后）。选项 C a,c,b,d：c 先于 b 入栈则 c 在 b 下 ✗。D：d,a,b,c？d 最先入则 d 在栈底，不可能已出栈而 a,b,c 在上……除非 d 出时 a,b,c 未入：d 入即出，然后 a,b,c 入栈 → 当前栈 a,b,c ✓！入栈序 d,a,b,c 合法 ✓。

所以正确推理：d 已出 ⇒ 要么 d 最先入即出（D），要么 d 后入先出（d 在 a,b,c 之后）——选项里没有 a,b,c,d。故 D ✓。

选 D。

易错提醒

① 「已出栈的元素」入栈序可在最前（进即出）或在全部现存元素之后；② 两个方向都要检查，别只想其一。