ITパスポート令和元年秋期 問62

問62

下から上へ品物を積み上げて,上にある品物から順に取り出す装置がある。この装置に対する操作は,次の二つに限られる。
 PUSH x:品物xを1個積み上げる。
 POP:一番上の品物を1個取り出す。

最初は何も積まれていない状態から開始して,a,b,cの順で三つの品物が到着する。一つの装置だけを使った場合,POP操作で取り出される品物の順番としてあり得ないものはどれか。

分類

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

正解

解説

選択肢ごとPUSH操作とPOP操作のみで順番が実現できるか検証します。[ ]は装置の中の状態を表しています。横向きになっていますが左側を装置の底として考えてください。
  • 以下の手順で可能です。
    PUSH a:[a]
    POP:[] → aを取り出す
    PUSH b:[b]
    POP:[] → bを取り出す
    PUSH c:[c]
    POP:[] → cを取り出す
  • 以下の手順で可能です。
    PUSH a:[a]
    PUSH b:[a,b]
    POP:[a] → bを取り出す
    POP:[] → aを取り出す
    PUSH c:[c]
    POP:[] → cを取り出す
  • 正しい。順番としてあり得ません。
    PUSH a:[a]
    PUSH b:[a,b]
    PUSH c:[a,b,c]
    POP:[a,b] → cを取り出す
    次にaを取り出す必要がありますが、POP操作を行うとbが取り出されます。aはbより下に積まれているのでbより先に取り出すことができません。
  • 以下の手順で可能です。
    PUSH a:[a]
    PUSH b:[a,b]
    PUSH c:[a,b,c]
    POP:[a,b] → cを取り出す
    POP:[a] → bを取り出す
    POP:[] → aを取り出す
© 2009-2019 ITパスポート試験ドットコム All Rights Reserved.

Pagetop