問 題
図Ⅰのように先に入れたデータを先に取り出す FIFO (First In First Out) 構造のキューについて考える。
いま、初期状態が ㋐ ～ ㋔ のどれかの状態にあるキューに対し次に示す一連の操作を実行したところ、キューの状態が図Ⅱのようになった。㋐ ～ ㋔ のうちこのキューの初期状態であった可能性があるもののみを全て挙げているのはどれか。
1．㋐、㋑、㋔
2．㋐、㋒
3．㋑、㋒
4．㋑、㋓
5．㋓、㋔
正解 (4)
解 説
enq(deq()) は
「キューの左から取り出して 右からつっこむ」という意味と読み取れます。
㋐ ですが、初期状態が 11111
・enq(1) で 111111
・enq(deq()) で変化なし
・deq() で 11111
・enq(2) で 111112
・deq() × 2 で 1112
・enq(2) で 11122
・enq(deq()) で 11221 となります。 惜しい…！
㋐ は誤りです。
従って、選択肢 1,2 は誤りです。
同様に、各初期状態に対して一連の操作を行った状態について考えていけば、㋑、㋓ が妥当です。ぜひ ㋐ と同様に確認してみてください。ちなみにですが、今回の一連の操作は「abcde → 1a22e」にする という操作です。
特に ㋓ は初期状態で余計な 3 が 3 つもあるし、最後の最後まで「えっ、これほんとにあってる？」という状態変化を経て、うまーく 11222 になるので、特に面白い流れではないかと思います。
以上より、正解は 4 です。
類題 2019 no39
https://yaku-tik.com/koumuin/2019-denjyou-39/
コメント