ITパスポート過去問集 - データ構造

下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。この装置に対する操作は，次の二つに限られる。

PUSH x ： 品物xを1個積み上げる。
POP ： 一番上の品物を1個取り出す。


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

複数のデータが格納されているスタックからのデータの取出し方として，適切なものはどれか。

先入れ先出し（First-In First-Out, FIFO）処理を行うのに適したキューと呼ばれるデータ構造に対して“8”，“1”，“6”，“3”の順に値を格納してから，取出しを続けて2回行った。2回目の取出しで得られる値はどれか。

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

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

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

あるキューに要素“33”，要素“27”及び要素“12”の三つがこの順序で格納されている。このキューに要素“45”を追加した後に要素を二つ取り出す。2番目に取り出される要素はどれか。

数字が書かれた箱を図のように積み上げてある。表に示す操作を，操作1，操作2，操作3，操作4の順に行った場合，操作4が終わったときの箱の状態はどれか。

4 3 2 2 1 図

表 操作名 操作の内容 操作1 箱を上から二つ取り出し，取り出した箱に書かれた値を加算した値を書いた箱を新たに一番上に積む。 操作2 数字3を書いた箱を新たに一番上に積む。 操作3 箱を上から三つ取り出し，取り出した箱に書かれた値の平均値を求める。その平均値を書いた箱を新たに一番上に積む。 操作4 箱を上から二つ取り出し，取り出した箱に書かれた値の差の絶対値を求める。その絶対値を書いた箱を新たに一番上に積む。