408 每日一题 Day1#

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，若元素 $a,b,c,d,e,f,g,h,i$ 依次入队后再进行出队操作，则可能得到以 $i$ 开头的出队序列有（ ）种。

A. 64
B. 128
C. 256
D. 512

正确答案：B#

解析：

由于仅允许在一端出队，因此想让 $i$ 第一个出队，必须将 $i$ 插入到允许出队的一端。

对于 $a$ 从左端或右端入队并无区别。 对前面的 $b\sim h$ 共 7 个元素而言，每个元素入队时都可选择插入左端或右端，共有 $2^7$ 种选择。

且一旦 $i$ 首先出队后，其余元素的出队顺序已由之前的插入方式唯一确定，因此可能的以 $i$ 开头的出队序列共有：$2^7=128$ 种

故答案为 B。