次の条件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つあればよい。 |
ウ |
根付き木は、処理の済んだデータを記憶しておく場合に使用する。 |
エ |
優先度キューでは、キューを優先度毎に用意するので、各キューのデータ位置を格納するための変数が必要である。 |
【キーワード】
・キュー
・スタック
【キーワードの解説】
- キュー
一時的なデータの格納領域で、格納したのと同じ順でデータを取り出すことができます。
(First-In First-Out、FIFO)
- スタック
一時的なデータの格納領域で、格納したのと逆の順でデータを取り出すことができます。
(Last-In First-Out、LIFO)
もっと、「キュー」について調べてみよう。
戻る
一覧へ
次へ
|