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

問 5
応用情報技術者試験 2016年(平成28年度)春期 午前

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

        A, B, C
           │
        ┌──▼──┐
        │スタック│
        └─────┘
           │
       取出し順
解説

正解は「ウ」です。

A,B,C をこの順にスタックへ挿入し,各データについて挿入と取出しを 1 回ずつ行うとき,得られる出力順序は次の 5 通りです。

  • ABC(A を挿入して取出し,B を挿入して取出し,C を挿入して取出す)
  • ACB(A を挿入して取出し,B と C を挿入してから C,B の順に取出す)
  • BAC(A と B を挿入して B を取出し,A を取出してから C を挿入して取出す)
  • BCA(A と B を挿入して B を取出し,C を挿入して取出してから A を取出す)
  • CBA(A,B,C を挿入してから C,B,A の順に取出す)

これは 3 個の要素のスタック順列の数(カタラン数 C3=5C_3 = 5)に一致します。

  • ア・イ・エ: 3 通り,4 通り,6 通りは誤りです。

よって正解は「ウ」です。

関連問題

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