Skip to content

2010年 408 数据结构 第 1 题

数据结构2010年选择题2分

题目

若元素 a, b, c, d, e, f 依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈操作,则不可能得到的出栈序列是( )。

错因

A

模拟时漏掉了中间的入栈步骤。d、c 连续出栈(2次)后,下一步要让 e 出栈必须先压入 e,这次入栈把连续计数清零。此后 b 单独出栈(1次),再压 f,再弹 f,再弹 a,每段连续退栈均 ≤ 2 次,A 是可行的。误以为 A 不可行的人通常把 d,c,e 连读成三次退栈,没意识到中间插了一次 push e。

B

误以为 c、b 出完之后再出 d 会构成三连。实际上 c,b 连续出栈后(2次),下一步压入 d 打断计数;随后弹 d(1次)再弹 a(1次继续,但前一步压 d 已重置,d 与 a 属于新段;两次也不超 2),之后 push e, push f, pop f, pop e 各单次。全程最大连续退栈 = 2,B 可行。

C

把「b 出,push c,pop c,pop a」误算为"b→c→a 三连退栈"。实际上 b 出后紧接 push c,push 使计数归零;pop c 是新段的第 1 次,pop a 是第 2 次,最大连续 = 2,不违规。C 可行。

总解析

判断哪个序列不可行,只需找到必须出现"连续 3 次退栈"的情况。

对 D(a, f, e, d, c, b):

  • 先 push a,pop a(1 次连续);
  • 接着依次 push b, c, d, e, f;
  • 要输出 f,pop f(1次);要输出 e,pop e(2次);要输出 d,pop d(3次)——触发限制!

三次连续退栈之间没有任何 push 操作可以插入(因为 a 已出,b,c,d,e,f 全部已压入,没有新元素可以用来打断),所以 D 不可能实现。

A、B、C 均可通过在恰当时机插入入栈操作,使连续退栈次数保持 ≤ 2,完整模拟可验证。

最终答案是 D

最后更新:

🎬 可视化演示
加载中...

提示:可在可视化区直接操作播放、步进、修改参数