条件に基づく実現可能なデータ構造についての問題・解説


問題

【条件】

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

【内部データ構造の要素】
①:配列A(データと同じ型。大きさはn。)
②:変数X(0以上n未満の整数が記憶できる)
③:変数Y(0以上n未満の整数が記憶できる)
④:関数succ(i)(仮引数iに対して、i+1をnで割った余りを返す)(仮引数iは0以上n未満の値を取る)

上記の条件と内部データ構造の要素を実現できるものは以下のどれになるか。

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

解説

【情報整理】
キュー(FIFO) :入れた順番に取り出す
スタック(LIFO):最後に入れたものを最初に取り出す
根付き木     :ある要素を基準にした時に上下関係があるもの
優先度キュー     :優先度に従ってデータを取り出す

キュー(FIFO):
・発生したデータの格納位置を変数X、取出し位置を変数Yに記録する
・キューが行われた時に関数succの返却値によって値を更新すればよい
→実装可能(関数succ(i)は要素数nの配列を循環使用するため)

スタック(LIFO):
・要素を取出したときに、次の取出し位置を減算によって決める必要がある
→内部データの構造にはそのような要素はないので、実現不可

根付き木:
・根に当たる要素をA[0]に記録する
・【親の要素番号をi】とした時、左右の子をそれぞれ2✕i、2✕i+1に相当する位置に記録する
→という操作ができれば可能だが、当条件にはそれに該当する関数はない。実現不可

優先度キュー:
・処理順番が格納順と無関係で、優先度を考慮しなくてはいけない
・優先度順に格納する場合には、データの値のほかに優先度を記録する必要がある
→実現不可