応用情報技術者 2016年 春期 午前2 問05
問題文
A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。
選択肢
ア：3
イ：4
ウ：5（正解）
エ：6
データの出力順序の通り数【午前2 解説】
要点まとめ
- 結論：A, B, Cを順にスタックに入れ、各データを1回ずつ出す場合、出力順序は5通り存在します。
- 根拠：スタックはLIFO（後入れ先出し）構造であり、入出力の組み合わせから可能な順序を列挙すると5通りとなるためです。
- 差がつくポイント：スタックの特性を理解し、入出力操作の順序を正確に追えるかが合否を分けます。
正解の理由
スタックは後入れ先出しの構造で、A, B, Cを順に入れながら1回ずつ出す操作を考えます。
この条件下で可能な出力順序は以下の5通りです。
この条件下で可能な出力順序は以下の5通りです。
- ABC（順に入れて順に出す）
- ACB（Bを一旦スタックに残しCを先に出す）
- BAC（Aを出してからBを出し、最後にC）
- BCA（Bを出してからCを出し、最後にA）
- CAB（Cを先に出し、AとBを後から出す）
これらを網羅すると選択肢の中で5通りの「ウ」が正解となります。
よくある誤解
スタックの操作を単純に「順番通りに出すだけ」と誤解し、通り数を3通りや4通りと考えてしまうことが多いです。
また、入出力のタイミングを混同し、実際に可能な順序を正確に列挙できないこともあります。
また、入出力のタイミングを混同し、実際に可能な順序を正確に列挙できないこともあります。
解法ステップ
- 入力順序A→B→Cを確認する。
- スタックに入れる操作（push）と出す操作（pop）を1回ずつ行う条件を理解する。
- 可能な入出力の組み合わせを順に列挙する。
- スタックのLIFO特性を考慮し、出力順序を導き出す。
- 列挙した出力順序の数を数え、選択肢と照合する。
選択肢別の誤答解説
- ア: 3通りは少なすぎる。単純に順番通りだけを考えた誤り。
- イ: 4通りは一部の順序を見落としている。
- ウ: 5通りは正しく、全ての可能な出力順序を網羅している。
- エ: 6通りはスタックの制約を超えた順序を含むため誤り。
補足コラム
この問題は「スタックの出力順列問題」として知られ、アルゴリズムやデータ構造の基本理解に役立ちます。
スタックの入出力順序は「スタック可能順列」と呼ばれ、数学的にはカタラン数と関連する場合もありますが、3要素の場合は手計算で列挙可能です。
スタックの入出力順序は「スタック可能順列」と呼ばれ、数学的にはカタラン数と関連する場合もありますが、3要素の場合は手計算で列挙可能です。
FAQ
Q: なぜスタックはLIFO構造と言われるのですか？
A: 最後に入れたデータが最初に出る（Last In First Out）ためです。
A: 最後に入れたデータが最初に出る（Last In First Out）ためです。
Q: 入力順序が変わると出力通り数は変わりますか？
A: はい。入力順序が異なれば可能な出力順序も変わります。
A: はい。入力順序が異なれば可能な出力順序も変わります。
関連キーワード: スタック、出力順序、データ構造、LIFO, 順列
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！