解説

• 先に[イ]と[ウ]に入る字句を考えてから、[ア]に進むとスムーズです。
  
  〔イについて〕
  表1「ヘッダ部分のメンバの意味」よを見ると'A'と'F'の定数を値として持つメンバは status のみです。よって、[イ]には「status」が入ります。
  
  ∴イ＝status
  
  〔ウについて〕
  q->statusが'A'の場合、すなわち「データ部分は割当て済みメモリである場合」や、q->sizeがmsize未満である場合、すなわち「データ部分のバイト数が割り当てたいバイト数未満」であれば、現在参照しているメモリブロックにメモリを割り当てることはできません。このとき、1つ後のメモリブロックの確認に移るために、q を1つ後のメモリブロックの先頭アドレスで更新することになります。そのメモリブロックの1つ後のメモリブロックの先頭アドレスは、メンバ next が保持しているので、q に q->next を設定する手続きが適切です。
  
  ∴ウ＝next
  
  〔アについて〕
  ポインタ変数 q の初期値は、変数EDGEのメンバ next（リストの先頭要素）です。前述の通り q が割当てできないメモリブロックである場合には、q は1つ後ろのメモリブロックに移動しますが、割当て可能なメモリブロックが見つかったときは関数の戻り値に q をセットして関数を終了します（〔メモリ割当ての関数〕(4)(5)参照）。ここで、もし末尾のメモリブロックまで適切な空きメモリが見つからず、q に末尾のメモリブロックのメンバ next がセットされたとき、q の値はどうなっているのかを考えます。
  
  問題文では「最後尾のメモリブロックのメンバ next には，… EDGEの先頭アドレスをセットする」と説明されているので、末尾のメモリブロックまで走査した結果、十分な空きメモリをもったメモリブロックがなかった場合、q にはEDGEの先頭アドレスがセットされていることになります。よって、q が「EDGEの先頭アドレス」と等しい場合には、関数の戻り値に NULL をセットして終了することになります。
  
  ∴ア＝EDGEの先頭アドレス
  
  
• 〔メモリ割当ての関数〕(5)の処理は、q をメモリ割当て済みのメモリブロックと、空きメモリブロック r に分割する処理です。
  図3「メモリ割り当てによるメモリ分割」より、空きメモリブロック r は q の1つ後ろのメモリブロックになることがわかります。したがって、リスト内のメモリブロックの連結が以下のように変わることになります。

  分割前

  qの1つ前のブロック ←→ q ←→ qの1つ前のブロック

  分割後

  qの1つ前のブロック ←→ q ←→ r ←→ qの1つ前のブロック

  〔エについて〕
  r->prev は、r の1つ前のメモリブロックの先頭アドレスなので、「q」をセットするのが適切です。
  
  〔オについて〕
  r->next は、r の1つ後のメモリブロックの先頭アドレスなので、「q->next」をセットするのが適切です。q->next の値を r に更新する処理は最後に行っているので、q->next で分割前の q の1つ後ろのメモリブロックを参照可能です。
  
  ∴エ＝q
  　オ＝q->next

解説

• 〔カについて〕
  status に設定する値ですので、'A'または'F'の択一です。
  
  関数 freemem 中では、前後のブロックの少なくとも1つが空きブロックである場合には、それらをまとめて1つの空きブロックにします。この際、空きブロックのメンバ size を設定していますが、変数 EDGE はデータ部分を持っていない（size=0）ので、p や r となったときに空きブロックとして扱われてしまうのは適切ではありません。特に p になったときは、変数EDGEのメンバ size を空きブロックのデータサイズで更新してしまうことになります。
  
  よって、変数EDGEのメンバ status には'A'(割当て済)をセットしておき、空きブロックとして扱われないようにしておく必要があります。
  
  ∴カ＝'A'
  
  
• 〔キについて〕
  コメント部にあるように、この分岐は前後のブロックがともに空きであるときの処理です。
  
  この場合、前・解放対象・後の3つのブロックの空き領域を前のブロック（p）にまとめることになります。解放対象のブロック及び後のブロックについては、解放によりヘッダ部分とデータ部分の両方が空き領域となるので、前のブロックのメンバ size に設定する値は以下の3つの合計となります。
  1. 前のブロックのデータサイズ
  2. 解放対象のブロックのヘッダサイズ＋データサイズ
  3. 後のブロックのヘッダサイズ＋データサイズ
  
  したがって p->size に設定する値は、p->size、q->size、r->size とヘッダ部分のバイト数である HSIZE 2つ分（HSIZE * 2）の合計となります。
  
  ∴キ＝p->size + q->size + r->size + 2*HSIZE
  
  〔クについて〕
  空き領域を前のメモリブロックにまとめると、まとめられた側のメモリブロック（qやr）は不要となるのでリストから外されます。このとき、リストの連結を維持するために前のメモリブロック（p）のメンバ next を更新する必要があります。具体的には、p->next の値は関数 freemem の6行目または9行目で次の値で更新されています。

  前後とも空きの場合（6行目）

  p ←→ q ←→ r ←→ rの1つ後
  が
  p ←→ rの1つ後
  となるので、r->next を設定

  前だけが空きの場合（9行目）

  p ←→ q ←→ r
  が
  p ←→ r
  となるので、r を設定

  本問のリストは双方向のリストなので、p->next（rの1つ後またはr）のメンバ prev には、1つ前のメモリブロックである「p」を設定することになります。
  
  ∴ク＝p
  
  〔ケについて〕
  コメント部にあるように、この分岐は前が割当て済で、後が空きであるときの処理です。
  
  この場合、解放対象・後の2つのブロックの空き領域を解放対象のブロック（q）にまとめることになります。後のブロックについては、解放によりヘッダ部分とデータ部分の両方が空き領域となるので、解放対象のブロックのメンバ size に設定する値は以下の2つの合計となります。
  1. 解放対象のブロックのデータサイズ
  2. 後のブロックのヘッダサイズ＋データサイズ
  
  したがって q->size に設定する値は、q->size、r->size とヘッダ部分のバイト数である HSIZE 1つ分の合計となります。
  
  ∴ケ＝q->size + r->size + HSIZE

解説

• 記憶領域を区画してプログラムに割り当てていくと、その結果として記憶領域上に小さな空き領域が点在した状態になります。この状態になると空き領域の合計としては余裕があるにもかかわらず、サイズの大きな空きメモリの確保が難しくなり、アクセス効率が低下します。この現象を「フラグメンテーション」と呼びます。
  
  ∴コ＝フラグメンテーション
  
  
• 〔サについて〕
  図6「ヒープ領域の状態」を見ると、割当て済（status='A'）のメモリが4つ、空きメモリ（status='F'）が3つあります。この3つの空メモリの size を合計すると「200＋300＋100=600」となります。メモリコンパクションを行うと複数の空きメモリが1つの大きな空きメモリにまとまるので、ヘッダ部分が1つで済みます。3つの空きメモリを1つの空きメモリにまとめた場合、2つのヘッダ部分の領域もデータ部分として使用できることになります。
  
  したがって、図6の状態にメモリコンパクションを実行した場合にできる空きメモリの大きさは、600バイトに HSIZE 2つ分を足した「2×HSIZE＋600」が適切です。
  
  ∴サ＝2×HSIZE＋600
  
  
• メモリ割当ての関数の戻り値である q は、割当て可能とされたメモリブロックの先頭アドレスです。メモリコンパクションでは、割当て済みのメモリブロックが連続するようにメモリブロックを移動するので、移動対象となった割当て済みメモリについては先頭アドレスが変わることになります。このため、メモリ解放の関数の引数として戻り値の q を指定しても、正しく参照できないことがあります。
  
  ∴メモリブロックの先頭アドレスが変わるから