基本情報技術者試験 2004年度 = 平成16年度・春期 午前 問12

 A、B、C、Dの順に到着するデータに対して、一つのスタックだけを用いて出力可能なデータ列はどれか。

ア A、D、B、C
イ B、D、A、C
ウ C、B、D、A
エ D、C、A、B

解答



解説

 スタックstack)は、データをLIFOLast-In First-Out)で蓄えます。ちょうど、机の上に重ねた皿のように、最も上に重ねた皿を優先的に取り出すのと同様です。
 データを入れる操作をプッシュpush)、データを取り出す操作をポップpop)といいます。

ア A、D、B、C
 プッシュ、ポップは、次のようになります。

push A pop A push B push C push D pop D pop C pop B  ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌  │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │  │ │ │ │ │ │ │ │ │D│ │ │ │ │ │ │  │ │ │ │ │ │ │C│ │C│ │C│ │ │ │ │  │A│ │ │ │B│ │B│ │B│ │B│ │B│ │ │  └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘

 Dを取り出した後は、C、Bと取り出されることになりますので、A、D、CBでなければなりません。

イ B、D、A、C
 プッシュ、ポップは、次のようになります。

push A push B pop B push C push D pop D pop C pop A  ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌  │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │  │ │ │ │ │ │ │ │ │D│ │ │ │ │ │ │  │ │ │B│ │ │ │C│ │C│ │C│ │ │ │ │  │A│ │A│ │A│ │A│ │A│ │A│ │A│ │ │  └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘

 Dを取り出した後は、C、Aと取り出されることになりますので、B、D、CAでなければなりません。

ウ C、B、D、A
 プッシュ、ポップは、次のようになります。

push A push B push C pop C pop B push D pop D pop A  ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌  │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │  │ │ │ │ │C│ │ │ │ │ │ │ │ │ │ │  │ │ │B│ │B│ │B│ │ │ │D│ │ │ │ │  │A│ │A│ │A│ │A│ │A│ │A│ │A│ │ │  └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘

 正解です。

エ D、C、A、B
 プッシュ、ポップは、次のようになります。

push A push B push C push D pop D pop C pop B pop A  ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ ┌  │ │ │ │ │ │ │D│ │ │ │ │ │ │ │ │  │ │ │ │ │C│ │C│ │C│ │ │ │ │ │ │  │ │ │B│ │B│ │B│ │B│ │B│ │ │ │ │  │A│ │A│ │A│ │A│ │A│ │A│ │A│ │ │  └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘

 Cを取り出した後は、B、Aと取り出されることになりますので、D、C、BAでなければなりません。


BohYoh.comトップページへ