令和5年度 春期 午前 問5

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

解説

探す手掛かりと同じ大きさで並べた木です。

設問は、最適適合アルゴリズムで空き領域を管理するとき、割当て時の平均処理時間が最も短いデータ構造を四つから選ばせています。最適適合が毎回する仕事は、要求量以上の大きさをもつ空き領域のうち最小のものを一つ見つけることです。ですから見分けの軸は、探す手掛かりである大きさが索引そのものになっているか、そして探索を途中から始められるか、という二点になります。大きさをキーとする2分探索木であれば、根から下りながら要求量に届かない側の枝をまとめて捨てられるので、空き領域がn個あっても比較の回数はおよそlog nに収まります。求める条件と索引のキーがそろっていて、しかも半分ずつ範囲を絞れる形が、この構造だけだからです。空き領域が1,000個あるとき、およそ10回で目的の領域に届く見当になります。

ほかの選択肢はなぜ違うのか

• ア空き領域のアドレスをキーとする 2 分探…：空き領域のアドレスをキーとする2分探索木です。木の形に反映されているのは配置の順序であって大きさではないため、条件に合う領域を探すには結局すべての節点をたどることになります。
• イ空き領域の大きさが小さい順の片方向連結リ…：大きさが小さい順に並んだ片方向連結リストです。並び順は目的に合っていますが、先頭から一つずつたどるほかに進み方がなく、要求量に届く位置まで歩く手間が領域の個数に比例して増えます。
• エアドレスに対応したビットマップ：アドレスに対応したビットマップです。使用中か空きかを1ビットずつ持つだけなので、連続した空きがどこまで続くかは端から数え上げないと分からず、割当てのたびに広い走査が必要になります。