問題プレビューID: 1ccc05fbITパスポート試験 2016年(平成28年度)秋期

問 92
ITパスポート試験 2016年(平成28年度)秋期

後に入れたデータが先に取り出されるデータ構造(以下,スタックという)がある。これを用いて,図に示すような,右側から入力されたデータの順番を変化させて,左側に出力する装置を考える。この装置に対する操作は次の 3 通りである。

  • ① 右側から入力されたデータをそのまま左側に出力する。
  • ② 右側から入力されたデータをスタックの 1 番上に積み上げる。
  • ③ スタックの 1 番上にあるデータを取り出して左側に出力する。

この装置の右側から順番にデータ A,B,C,D を入力した場合に,この①〜③の操作を組み合わせても,左側に出力できない順番はどれか。

解説

正解は「エ」です。

スタックは後入れ先出し(LIFO)の構造です。入力順 A,B,C,D に対して,各操作を組み合わせて出力できるかどうかを考えます。

  • ア B,A,D,C: A,B を②で積み,③で B,A を取り出した後,C,D を②で積み,③で D,C を取り出せば実現できます。
  • イ B,D,C,A: A を②で積み,B を①で出力した後,C,D を②で積み,③で D,C,A を取り出せば実現できます。
  • ウ C,B,D,A: A,B を②で積み,C を①で出力し,③で B を取り出した後,D を②で積み,③で D,A を取り出せば実現できます。
  • エ C,D,A,B: 最初に C を出力した時点でスタックには A,B が残ります。次に D を出力した後,スタックの 1 番上にあるのは B なので,A を B より先に取り出すことはできません。よって C,D,A,B は実現できません。

関連問題

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