問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) |
ウ |
根付き木 |
エ |
優先度キュー |
|
|
解説 |
[条件]を満たすためのものが、[内部データ構造の要素]なのでこちらだけを考えます。
要素@から、n未満のデータをそれぞれ配列に格納することが予想されます。
要素Aから、使用される変数が2つであることがわかります。
要素Bから、0、1、2、・・・n−1、0、1のように、値を循環させることがわかります。
以上のことからキューをあらわしていることがわかります。(XとYは入り口と出口を表している変数と予想されます)
最後に、スタックとキューのデータ構造を以下にまとめます。
|
|