応用情報技術者試験 令和7年度 春期 午前 問5

【正解】ウ

スタックは、最後に挿入したデータを最初に取り出すLIFO方式です。入力はA、B、Cの順にしか行えませんが、各入力の途中で取出しを行えるので、操作の組合せを具体的に調べます。

Aを挿入直後に取り出し、B、Cも同様に処理するとABCです。Aを取り出した後、B、Cを挿入して逆順に取り出すとACBです。A、Bを挿入してB、Aの順に取り出し、その後Cを処理するとBACです。A、Bを挿入してBを取り出し、次にCを挿入してC、Aの順に取り出すとBCAです。三つ全てを挿入してから取り出すとCBAです。したがって、可能なのはABC、ACB、BAC、BCA、CBAの5通りです。

アの3通りは誤りです。途中で挿入と取出しを切り替える場合を数え切れておらず、実際には上記の5通りが可能です。

イの4通りは誤りです。例えばBを出力した後でCを挿入するBCAなど、正当な操作順序を一つ見落とすと4通りになります。

エの6通りは誤りです。単純な順列なら3！＝6通りですが、CABは実現できません。Cを最初に出すにはA、B、Cを全て挿入する必要があり、Cを取り出した直後の最上部はBなので、AをBより先には取り出せないためです。

【ポイント】 スタックの出力順序は、実際に挿入と取出しを並べて確認すると確実です。n個の異なるデータを順番に入力する場合、可能な出力順序の総数はカタラン数で表され、n＝3では5です。