データ構造 (全40問中35問目)
No.35
次の条件a～dを満たすデータを処理するために，内部データ構造の要素①～③を考えた。これらを用いて実装できるデータ構造は，どの抽象データ型に分類されるか。
〔条件〕
〔条件〕
- データはすべて同じ型をもつ。
- データは時系列的に発生する。
- 処理の済んだデータを記憶しておく必要はない。
- 未処理のデータ数は常にn未満になることが分かっている。
- データと同じ型の要素をもつ大きさnの配列A(A[0]，A[1]，…，A[n－1])
- 0以上n未満の整数が記憶できる変数XとY
- 0以上n未満の値をとる仮引数iに対して，i＋1をnで割った余りを返す関数succ(i)
出典：平成18年春期 問10
- キュー(FIFO)
- スタック(LIFO)
- 根付き木
- 優先度キュー
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
ア
解説
〔条件〕a～dの記述をもとに選択肢を絞っていきます。
なお、〔内部データ構造の要素〕に記述されている2つの変数はキューの先頭と末尾の位置を保持する変数、関数succは固定長の領域を循環利用するリングバッファ構造を実現するための関数であると考えられます。
- a.データはすべて同じ型をもつ。
- どのデータ型も配列で実装できる
→全部のデータ型がOK - b.データは時系列的に発生する。
- 発生順に処理するのであれば、スタックと木構造は不適切
よって、キューまたは優先度キュー - c.処理の済んだデータを記憶しておく必要はない。
- 全部のデータ型がOK
- d.未処理のデータ数は常にn未満になることが分かっている。
- 固定長のデータ構造で大丈夫
→全部のデータ型がOK
なお、〔内部データ構造の要素〕に記述されている2つの変数はキューの先頭と末尾の位置を保持する変数、関数succは固定長の領域を循環利用するリングバッファ構造を実現するための関数であると考えられます。
- リングバッファ構造
- バッファの終端までデータを格納した後、バッファの先頭に戻ってデータ書き込む方式