408考研数据结构栈和队列真题

【2010年题1】 若元素 a, b, c, d, e, f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是____。
A. d c e b f a   B. c b d a e f   C. b c a e f d   D. a f e d c b

解析：
选项 A 可由 in, in, in, in, out, out, in, out, out, in, out, out 得到；选项 B 可由 in, in, in, out, out, in, out, out, in, out, in, out 得到；选项 C 可由 in, in, out, in, out, out, in, in, out, in, out, out 得到；选项 D 可由 in, out, in, in, in, in, in, out, out, out, out, out 得到，但题意要求不允许连续三次退栈操作，故 D 不可能得到。
【另解】先进栈的元素后出栈，进栈顺序为 a, b, c, d, e, f，故连续出栈时的序列必然是按字母表逆序的，若出栈序列中出现了长度大于等于 3 的连续逆序子序列，则为不符合要求的出栈序列。

【2010年题2】 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 a, b, c, d, e 依次入此队列后再进行出队操作，则不可能得到的出队序列是____。
A. b a c d e   B. d b a c e   C. d b c a e   D. e c b a d

解析：
本题的队列实际上是一个输出受限的双端队列。A 操作：a 左入（或右入）、b 左入、c 右入、d 右入、e 右入。B 操作：a 左入（或右入）、b 左入、c 右入、d 左入、e 右入。D 操作：a 左入（或右入）、b 左入、c 左入、d 右入、e 左入。C 操作：a 左入（或右入）、b 右入、因 d 未出，此时只能进队，c 怎么进都不可能在 b 和 a 之间。
【另解】初始时队列为空，第 1 个元素 a 左入（或右入），而第 2 个元素 b 无论是左入还是右入都必与 a 相邻，而选项 D 中 a 与 b 不相邻，不合题意。

2013年真题

【2013年题2】

一个栈的入栈序列为 $1, 2, 3, \cdots, n$，其出栈序列是 $p_1, p_2, p_3, \cdots, p_n$。若 ，则 可能取值的个数是______。