A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。

選択肢

• ア3
• イ4
• ウ5
• エ6

正解と解説

正解：ウ 5

各データについて挿入と取出しを1回ずつ行える場合の出力順序の総数は、要素数nに対するカタラン数で求まる。n＝3のときは5通りであり、具体的にはABC、ACB、BAC、BCA、CBAが実現できる。CABだけは作れない。Cを最初に出すにはAとBを積んだままにする必要があり、そのときBがAの上にあるため、スタックのLIFO性から次にAを出せない。

選択肢ごとの解説

• ア実現できる順序はもっと多く、数え漏らしがある。
• イ5通り実現できるので1通り不足している。
• ウ正解。n＝3のカタラン数は5で、CAB以外の5通りが実現できる。
• エ3要素の順列は6通りだが、そのうちCABはスタックのLIFO性により実現できない。

この問題は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