A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。
n要素のスタック出力順序はカタラン数で、n=3なら5通り
選択肢
- ア3
- イ4
- ウ5
- エ6
正解と解説
正解：ウ 5
スタックは後入れ先出しなので、挿入と取出しを交互に組み合わせて作れる順序は限られる。3個の場合に実現できるのはABC・ACB・BAC・BCA・CBAの5通りで、Cを最初に取り出した後にAがBより先に出るCABだけは作れない。全順列6通りから作れない1通りを除いた5通りで、これは要素数3のカタラン数と一致する。
選択肢ごとの解説
- ア実現できる順序を数え落としている。3通りより多く作れる。
- イ1通り数え落とした値。カタラン数C(3)は4ではない。
- ウ正解。3要素のスタック出力順序はカタラン数で5通り。
- エ全順列は6通りだが、スタックの後入れ先出し制約で1通りは作れない。
この問題は2回出題されています
- 2016年度 春期 午前 問5この問題の代表ページ
- 2025年度 春期 午前 問5（このページ）
同じ分野の他の問題
- 図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。2025年度 春期 午前 問6
- 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
- 各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたと…2024年度 春期 午前 問6
- 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5
- 要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当て…2023年度 春期 午前 問5
最終更新：2026-08-25／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。