高度情報処理技術者試験・情報処理安全確保支援士試験 令和7年度 春期 午前I 問3

【正解】ウ

スタックは、最後に挿入したデータを最初に取り出すLIFO方式のデータ構造です。図のとおりA、B、Cの順に挿入できますが、各データを挿入した後、後続データを挿入する前に取り出すこともできます。挿入と取出しのタイミングを変えて得られる出力順序は、ABC、ACB、BAC、BCA、CBAの5通りです。

例えばACBは、Aを挿入してすぐ取り出した後、B、Cを順に挿入し、C、Bの順に取り出すと得られます。BCAは、A、Bを挿入してBを取り出し、続いてCを挿入してC、Aの順に取り出すと得られます。一方、CABを得ることはできません。Cを最初に出力するにはA、B、Cを全てスタックに入れる必要があり、Cを取り出した後はBがAより上にあるため、必ずB、Aの順になるからです。

アの3通りは誤りです。挿入と取出しを途中で切り替える場合を十分に数えていません。

イの4通りは誤りです。実現可能な五つの順序のいずれかを見落とした数です。

エの6通りは誤りです。これは3個のデータの全順列である3！＝6を数えたものですが、スタックではCABを実現できません。

【ポイント】 スタックは「後入れ先出し」であり、上にあるデータを飛び越して下のデータを取り出すことはできません。 少数のデータでは、挿入と取出しの操作を具体的に追跡して列挙すると確実です。 入力順が固定された3要素の実現可能な出力順序数は5です。