要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリズムを用いる場合、空き領域を管理するためのデータ構造として、メモリ割当て時の平均処理時間が最も短いものはどれか。

選択肢

• ア空き領域のアドレスをキーとする2分探索木
• イ空き領域の大きさが小さい順の片方向連結リスト
• ウ空き領域の大きさをキーとする2分探索木
• エアドレスに対応したビットマップ

正解と解説

正解：ウ 空き領域の大きさをキーとする2分探索木

最適適合では「要求量以上で最小の空き領域」を探すので、大きさをキーとした2分探索木に空き領域を格納しておけば、要求量以上の最小要素を木の高さ、すなわち平均O(log n)で見つけられる。線形リストやビットマップは先頭から順に走査する必要があり平均O(n)かかる。

選択肢ごとの解説

• アアドレスをキーにしても大きさの順に並ばないため、条件に合う最小領域を探すには全体を調べることになる。
• イ大きさ順に並んではいるが片方向リストなので先頭から順にたどるしかなく、平均で線形時間かかる。
• ウ正しい。大きさをキーにした2分探索木なら目的の領域を対数時間で探索できる。
• エビットマップは連続した空きビット列を順に走査する必要があり、探索に時間がかかる。

同じ分野の他の問題

• 図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。2025年度 春期 午前 問6
• A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データ…2016年度 春期 午前 問5
• 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
• 各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたと…2024年度 春期 午前 問6
• 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5