データ構造(全40問中35問目)

No.35解説へ
次の条件a～dを満たすデータを処理するために，内部データ構造の要素①～③を考えた。これらを用いて実装できるデータ構造は，どの抽象データ型に分類されるか。

〔条件〕
  1. データはすべて同じ型をもつ。
  2. データは時系列的に発生する。
  3. 処理の済んだデータを記憶しておく必要はない。
  4. 未処理のデータ数は常にn未満になることが分かっている。
〔内部データ構造の要素〕
  1. データと同じ型の要素をもつ大きさnの配列A(A[0]，A[1]，…，A[n－1])
  2. 0以上n未満の整数が記憶できる変数XとY
  3. 0以上n未満の値をとる仮引数iに対して，i＋1をnで割った余りを返す関数succ(i)

出典：平成18年春期　問10

  • キュー(FIFO)
  • スタック(LIFO)
  • 根付き木
  • 優先度キュー
正解　ア問題へ
分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：データ構造
広告
解説
〔条件〕a～dの記述をもとに選択肢を絞っていきます。
a.データはすべて同じ型をもつ。
どのデータ型も配列で実装できる
→全部のデータ型がOK
b.データは時系列的に発生する。
発生順に処理するのであれば、スタックと木構造は不適切
よって、キューまたは優先度キュー
c.処理の済んだデータを記憶しておく必要はない。
全部のデータ型がOK
d.未処理のデータ数は常にn未満になることが分かっている。
固定長のデータ構造で大丈夫
→全部のデータ型がOK
したがって、キューまたは優先度キューに絞られます。優先度キューは優先度の高い要素から順番に取り出すデータ構造ですが、これを実現するには要素と優先度を紐付けておき、①要素格納時に適切な位置に挿入するための関数、または、②要素取り出し時に適切な要素を取り出す関数が必要となります。〔内部データの構造〕にはどちらもありませんので、優先度キューではありません。したがって「キュー」が正解です。

なお、〔内部データ構造の要素〕に記述されている2つの変数はキューの先頭と末尾の位置を保持する変数、関数succは固定長の領域を循環利用するリングバッファ構造を実現するための関数であると考えられます。
リングバッファ構造
バッファの終端までデータを格納した後、バッファの先頭に戻ってデータ書き込む方式
広告

次の問題前の問題

▲
Pagetop