応用情報技術者 2012年 春期 午前2 問06
問題文
A,B,Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。
選択肢
ア：3
イ：4
ウ：5（正解）
エ：6
データの出力順序の通り数【午前2 解説】
要点まとめ
- 結論：スタックにA, B, Cを順に入れ、各データを1回ずつ出す場合の出力順序は5通りです。
- 根拠：スタックのLIFO（後入れ先出し）特性により、入力順序ABCから可能な出力順は特定のパターンに限定されます。
- 差がつくポイント：スタック操作の入出力順序の組み合わせを正確に理解し、全パターンを網羅的に列挙できるかが鍵です。
正解の理由
スタックは後入れ先出しの構造で、A, B, Cを順に入れながら1回ずつ出す操作を考えると、可能な出力順は以下の5通りになります。
- ABC（順に入れて順に出す）
- ACB（Bを一旦スタックに残しCを先に出す）
- BAC（Aを出してからBを出す）
- BCA（Bを出してからCを出す）
- CAB（Cを先に出してからA, Bを出す）
これらはスタックの操作制約を満たす唯一の出力順序であり、選択肢の中で5通りに該当するウが正解です。
よくある誤解
スタックの操作を単純に「順番通りに出せる」と考え、全ての順列6通りが可能と誤認しやすいです。実際はLIFO制約で出力順が制限されます。
解法ステップ
- 入力順序ABCを確認する。
- スタックのLIFO特性を理解する。
- 入力データを順にスタックに入れ、出す操作を1回ずつ行う条件を考慮。
- 可能な出力順序を全て列挙する。
- 列挙した順序の数を数え、選択肢と照合する。
選択肢別の誤答解説
- ア: 3通りは少なすぎ、スタック操作の可能性を過小評価しています。
- イ: 4通りも実際より少なく、全パターンを網羅できていません。
- ウ: 5通りは正しく、全ての可能な出力順序を含みます。
- エ: 6通りは全順列の数であり、スタックの制約を無視した誤りです。
補足コラム
この問題は「スタックの出力順列問題」として知られ、スタックの操作制約下で可能な出力順列の数を求める典型問題です。一般に、個のデータに対して可能な出力順列の数はカタラン数で表され、の場合は5通りとなります。カタラン数は組合せ論やデータ構造の理解に役立つ重要な数学的概念です。
FAQ
Q: なぜ全ての順列（6通り）が出力できないのですか？
A: スタックは後入れ先出しの構造で、順序を自由に入れ替えられないため、全順列は不可能です。
A: スタックは後入れ先出しの構造で、順序を自由に入れ替えられないため、全順列は不可能です。
Q: この問題は他のデータ構造でも同じ結果になりますか？
A: いいえ。キューなどFIFO構造では出力順序の制約が異なり、可能な順列数も変わります。
A: いいえ。キューなどFIFO構造では出力順序の制約が異なり、可能な順列数も変わります。
関連キーワード: スタック、出力順列、カタラン数、データ構造、LIFO, 組合せ論
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！