令和元年度春期 応用情報技術者試験 午前 問5

正解：ウ

AI解説

最適適合(best-fit)は「要求量以上で最小の空き領域」を探すため、空き領域の大きさで探索できるデータ構造が有利である。大きさをキーとする2分探索木なら、要求量以上の最小キーをもつ節点を木の高さ分の比較、平均O(log n)で見つけられ、平均処理時間が最も短い。ウが正解である。 ア: アドレスをキーとする2分探索木は、アドレス順の探索には向くが、大きさの条件で探すには全節点を調べる必要があり非効率である。 イ: 大きさの昇順の片方向連結リストは先頭から順にたどるため平均でO(n)の探索時間がかかり、2分探索木より遅い。 ウ: 正しい。大きさをキーにした2分探索木なら、best-fitの条件(要求量以上の最小)に合う領域を平均O(log n)で発見できる。 エ: ビットマップは各アドレスの使用/未使用をビットで表すもので、連続する空き領域の大きさを知るには走査が必要であり、best-fit探索には向かない。 💡 「何をキーに探すか」とアルゴリズムの要求を一致させるのが原則。best-fitは大きさで探すので大きさキーの木、と対応付ける。リスト=O(n)、平衡した探索木=O(log n)の計算量感覚も重要である。