A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。
スタックで作れる出力順序の数はカタラン数になる
選択肢
- ア3
- イ4
- ウ5
- エ6
正解と解説
正解：ウ 5
スタックはLIFOなので、各データについて挿入・取出しを1回ずつ行うときに得られる出力順序の数はカタラン数で求められ、要素3個では5通りになる。実際に列挙すると、ABC・ACB・BAC・BCA・CBAの5通りが可能である。先にCを出してから残りをA→Bの順に出すこと（CAB）は、Cを取り出した時点でスタック内がB・Aの並びになっているため実現できない。
選択肢ごとの解説
- ア列挙すると3通りより多く得られるので不足している。
- イ実現できない順序を除いても4通りより多い。
- ウ正解。カタラン数C3＝5に一致し、CABだけが実現不能となる。
- エ3個の全順列は6通りだが、そのうちCABはスタックの後入れ先出しの制約で作れない。
この問題は2回出題されています
- 2021年度 春期 問2（このページ）
- 2025年度 春期 問3
同じ分野の他の問題
- 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 問3
- 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
- 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
- あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3
- ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 問6
最終更新：2026-08-25／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。