平成18年 春期 ソフトウェア開発技術者 午前 問10

次の条件a〜dを満たすデータを処理するために、内部データ構造の要素@〜Bを考えた。
これらを用いて実装できるデータ構造は、どの抽象データ型に分類されるか。

[条件]
a データはすべて同じ型を持つ。
b データは時系列に発生する。
c 処理の済んだデータを記憶しておく必要はない。
d 未処理のデータ数は常にn 未満になることがわかっている。

[内部データ構造の条件]
@ データと同じ型の要素を持つ大きさn の配列A (A [0], A [1], …, A [n -1])
A 0以上n 未満の整数が記憶できる変数X Y
B 0以上n 未満の値をとる仮引数i に対して、i +1をn で割った余りを返す関数succ(i )

 ア  キュー(FIFO)
 イ  スタック(LIFO)
 ウ  根付き木
 エ  優先度キュー


答え ア


解説

 ア  キューでは先頭のデータと最後のデータの位置を格納する2つの変数と、A [n ]の次にA [0]に格納するための処理をする関数が必要である。
 イ  スタックでは、データの最後の位置を格納する変数が1つあればよい。
 ウ  根付き木は、処理の済んだデータを記憶しておく場合に使用する。
 エ  優先度キューでは、キューを優先度毎に用意するので、各キューのデータ位置を格納するための変数が必要である。


キーワード
・キュー
・スタック

キーワードの解説

戻る 一覧へ 次へ