北京海淀区信息学竞赛 · 2024 北京市海淀区信息学竞赛（初赛）试题 第 10 题

一种常用的数据结构栈是只允许在一端进行进栈（插入）或出栈（删除）操作的线性表。如果进栈序列为 $1, 2, 3, 4, 5$，则出栈序列不可能出现的是（ ）

这题考栈的先进后出特性。拿到序列别急着看，先想象手里有个空栈，按 1 到 5 顺序往里面塞，每塞进去一个，就盯着题目给的出栈序列：要是下一个该出的数正好在栈顶，那就立刻把它弹出来；要是栈顶不是，那就只能继续往里塞。全程只要发现‘该出的数不在栈顶’又‘还没塞进去’，这序列就非法了，直接排除。

最容易栽跟头的是把栈当成队列，以为可以随便进出；或者只盯着数字大小，忘了栈顶限制。比如选项 B 里 4 出栈后，1 和 2 还没进栈，但题目要求 1 先出，这时候 1 根本不在栈顶，也没法塞进去，这种‘顺序错乱’的坑很多学生一眼就跳过去了。还有人会误以为只要数字递减就合法，忽略了进栈的时机。

这道题考查的是栈（Stack）这种线性数据结构的核心特性——先进后出（LIFO），以及基于固定进栈序列判断出栈序列合法性的经典模型。命题人特别喜欢在看似简单的排列组合里挖坑，比如让你判断一个出栈序列是否可能，或者在多个序列中找出唯一合法的一个。这类题往往不考复杂的算法实现，而是考你对栈操作逻辑的直觉和模拟能力。拿到题后，正确的思考心法应该是：把进栈序列 1,2,3,4,5 当作一个固定的输入流，想象你有一个空栈，必须按顺序把 1 塞进去，然后检查栈顶是否等于题目要求的下一个出栈元素。如果相等，就弹出；如果不相等，就继续塞下一个数。这个过程必须严格模拟，不能跳过任何一步。比如对于选项 A（5,4,3,2,1）：1 进栈，栈顶不是 5，继续塞 2,3,4,5，此时栈顶是 5，弹出 5；接着栈顶是 4，弹出 4……一路顺利，合法。对于选项 B（4,3,1,2,5）：1 进，栈顶不是 4，继续 2,3,4，栈顶是 4，弹出 4；接下来要求 3，栈顶确实是 3，弹出 3；再要求 1，但此时栈里只剩 1,2（1 在底，2 在顶），栈顶是 2，不是 1，而且 1 已经在栈里了，无法再塞进去，所以这个序列不可能出现，直接排除。选项 C 和 D 同理，都能通过模拟验证其合法性。这里的关键避坑点是：很多同学会误以为只要数字顺序‘看起来合理’就行，或者把栈和队列搞混，导致错误地认为某些序列合法。实际上，栈的约束非常严格——一旦某个元素入栈，它必须等上面所有元素都出栈后才能出来。考频趋势方面，根据历年真题数据，栈的合法性判断类题目在 CSP-J/S 和 NOIP 中属于高频考点，近三年出现频率稳定在每年 1-2 道，常出现在单选或多选的前半部分，难度中等偏上。预测未来几年，这类题目仍会保持较高热度，命题人可能会结合递归、括号匹配等场景进行变式考查，但核心逻辑不会改变。因此，掌握栈的模拟方法是应对此类题目的不二法门。