データ構造 (全52問中11問目)

No.11

A,B,C,Dの順に到着するデータに対して,一つのスタックだけを用いて出力可能なデータ列はどれか。
  • A,D,B,C
  • B,D,A,C
  • C,B,D,A
  • D,C,A,B
  • [出題歴]
  • 基本情報技術者 H16春期 問12
  • 基本情報技術者 H22秋期 問5

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

スタックは後入れ先出し(LIFO)のデータ構造で、PUSH命令とPOP命令によってデータを操作します。"後入れ先出し"ですので、スタックに先に入れたデータは、後から入れたデータよりも先に出力することができません。

選択肢の出力順をひとつずつ試していけばわかるのですが、4つのデータ列の中で出力可能なのは「C,B,D,A」で、その出力の過程は以下の通りです。
  1. PUSH(A) 05_1.gif/image-size:81×14
  2. PUSH(B) 05_2.gif/image-size:81×14
  3. PUSH(C) 05_3.gif/image-size:81×14
  4. POP(C) 05_4.gif/image-size:81×14
  5. POP(B) 05_5.gif/image-size:81×14
  6. PUSH(D) 05_6.gif/image-size:81×14
  7. POP(D) 05_7.gif/image-size:81×14
  8. POP(A) 05_8.gif/image-size:81×14
各出力を試みた場合、以下のようになります。※[]はスタックを表し、左の要素ほど昔に格納されたことを意味します。
  • PUSH(A) [A]
    POP(A) [] ※Aを出力
    PUSH(B) [B]
    PUSH(C) [BC]
    PUSH(D) [BCD]
    POP(D) [BC] ※Dを出力
    BはCより先にスタックに格納されたので、Cより先にBを出力することができません。
  • PUSH(A) [A]
    PUSH(B) [AB]
    POP(B) [A] ※Bを出力
    PUSH(C) [AC]
    PUSH(D) [ACD]
    POP(D) [AC] ※Dを出力
    AはCより先にスタックに格納されたので、Cより先にAを出力することができません。
  • 正しい。
  • PUSH(A) [A]
    PUSH(B) [AB]
    PUSH(C) [ABC]
    PUSH(D) [ABCD]
    POP(D) [ABC] ※Dを出力
    POP(C) [AB] ※Cを出力
    AはBより先にスタックに格納されたので、Bより先にAを出力することができません。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop