問題プレビューID: ccea1870応用情報技術者試験 2012年(平成24年度)春期 午前

問 6
応用情報技術者試験 2012年(平成24年度)春期 午前

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

解説

正解は「ウ」です。

A,B,C をこの順にスタックへ挿入(push)し,任意の時点で取出し(pop)できるとき,得られる出力順列を数え上げます。

  • A を push して pop → A B C
  • A を push・pop,B を push,C を push・pop,B を pop → A C B
  • A を push,B を push・pop,A を pop,C を push・pop → B A C
  • A を push,B を push・pop,C を push・pop,A を pop → B C A
  • A,B,C を push してから C,B,A の順に pop → C B A

得られる順序は A B C,A C B,B A C,B C A,C B A の 5 通りです(C A B はスタックの性質上得られません)。3 要素の場合の順列の数はカタラン数 C3=5C_3 = 5 と一致します。

  • ア: 3 通りではありません。
  • イ: 4 通りではありません。
  • エ: 6 通り(全順列)のうち,C A B が得られないため 6 通りではありません。

関連問題

本文が同じ・似ている問題を表示しています