応用情報技術者 2021年 春期 午前2 問05
問題文
A,B,Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。
選択肢
ア：3
イ：4
ウ：5（正解）
エ：6
データの出力順序の通り数【午前2 解説】
要点まとめ
- 結論：A, B, Cを順にスタックに入れ、各データを1回ずつ出す場合、出力順序は5通り存在します。
- 根拠：スタックのLIFO特性により、入力順序ABCから可能な出力順は特定の順列に限定されます。
- 差がつくポイント：スタック操作の入出力タイミングを正確に理解し、可能な出力順を列挙できるかが鍵です。
正解の理由
スタックは後入れ先出し（LIFO）構造であり、A, B, Cを順に入れて1回ずつ出す操作を考えると、出力順は以下の5通りに限定されます。
具体的には、入力順ABCに対して、スタック操作の組み合わせで生成可能な出力順は「ABC」「ACB」「BAC」「BCA」「CBA」の5通りです。
このため、選択肢の中で唯一5通りを示すウが正解となります。
具体的には、入力順ABCに対して、スタック操作の組み合わせで生成可能な出力順は「ABC」「ACB」「BAC」「BCA」「CBA」の5通りです。
このため、選択肢の中で唯一5通りを示すウが正解となります。
よくある誤解
スタックの動作を単純に「逆順になる」と誤解し、出力順が3通り（ABC, CBA, その逆）だけと考えることが多いです。
また、入出力のタイミングを自由に操作できると誤認し、通り数を過大評価することもあります。
また、入出力のタイミングを自由に操作できると誤認し、通り数を過大評価することもあります。
解法ステップ
- 入力順ABCを順にスタックに入れる操作を考える。
- 各データは1回ずつ出す必要があるため、出力タイミングを変えながら可能な順列を列挙。
- スタックのLIFO特性を利用し、途中で出すか後でまとめて出すかのパターンを検討。
- 可能な出力順をすべて書き出し、重複なく数える。
- 5通りであることを確認し、選択肢と照合する。
選択肢別の誤答解説
- ア: 3通りは少なすぎます。スタック操作の柔軟性を考慮していません。
- イ: 4通りも実際の可能性より少ないです。
- ウ: 5通りは正しい通り数で、スタックの入出力操作を正確に反映しています。
- エ: 6通りは多すぎで、スタックの制約を超えています。
補足コラム
スタックの入出力順序問題は「スタック可能順列（stack sortable permutations）」として知られ、組合せ論やアルゴリズムの基礎問題です。
3つの要素の場合は5通りですが、要素数が増えるとカタラン数に関連する通り数となり、計算が複雑になります。
3つの要素の場合は5通りですが、要素数が増えるとカタラン数に関連する通り数となり、計算が複雑になります。
FAQ
Q: なぜスタックの出力順序はすべての順列にならないのですか？
A: スタックはLIFO構造のため、入力順序を自由に並べ替えられず、特定の順列のみが可能です。
A: スタックはLIFO構造のため、入力順序を自由に並べ替えられず、特定の順列のみが可能です。
Q: 入力順ABCで出力順BACはどうやって実現しますか？
A: Aを入れてすぐ出さずにBを入れ、Bを先に出し、その後Aを出す操作で実現可能です。
A: Aを入れてすぐ出さずにBを入れ、Bを先に出し、その後Aを出す操作で実現可能です。
関連キーワード: スタック、順列、LIFO, データ構造、組合せ論
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！