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

選択肢

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

正解と解説

正解：ウ 5

各データについて挿入と取出しを1回ずつ行える場合の出力順序の総数は、要素数nに対するカタラン数で求まる。n＝3のときは5通りであり、具体的にはABC、ACB、BAC、BCA、CBAが実現できる。入力順の最初の要素より前に後続要素を出し切ったうえで先頭要素を最後より前に出すCABだけは、スタックのLIFO性から作れない。

選択肢ごとの解説

• ア実現できる順序はもっと多く、数え漏らしがある。
• イ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