题31

题31

题目

[!question]+
【2022 统考真题】给定有限符号集 ,in 和 out 均为 中所有元素的任意排列. 对于初始为空的栈 ST，下列叙述中，正确的是 ( ).
A. 若 in 是 ST 的入栈序列, 则不能判断 out 是否为其可能的出栈序列
B. 若 out 是 ST 的出栈序列, 则不能判断 in 是否为其可能的入栈序列
C. 若 in 是 ST 的入栈序列, out 是对应 in 的出栈序列, 则 in 与 out 一定不同
D. 若 in 是 ST 的入栈序列, out 是对应 in 的出栈序列, 则 in 与 out 可能互为倒序

分析

[!NOTE]+
通过模拟出入栈操作, 可以判断入栈序列 in 和出栈序列 out 是否合法。因此, 已知 in 序列可以判断 out 序列是否为可能的出栈序列;
已知 out 序列也可以判断 in 序列是否为可能的入栈序列, 和 错误。
若每个元素入栈后立即出栈,则 序列和 out 序列相同, 错误。若所有元素都入栈后才依次出栈, 则 in 序列和 out 序列互为倒序, D 正确。

解

[!done]+
D