da08.htm

1800道数据结构题和答案

<p class=MsoNormal style='margin-right:-88.7pt;text-indent:34.2pt;mso-char-indent-count:
3.0;tab-stops:558.0pt;mso-layout-grid-align:none'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='margin-right:-88.7pt;text-indent:34.2pt;mso-char-indent-count:
3.0;tab-stops:558.0pt;mso-layout-grid-align:none'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='margin-right:-88.7pt;text-indent:34.2pt;mso-char-indent-count:
3.0;tab-stops:558.0pt;mso-layout-grid-align:none'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='margin-right:-88.7pt;text-indent:34.2pt;mso-char-indent-count:
3.0;tab-stops:558.0pt;mso-layout-grid-align:none'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='margin-right:-88.7pt;text-indent:34.2pt;mso-char-indent-count:
3.0;tab-stops:558.0pt;mso-layout-grid-align:none'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='margin-right:-88.7pt;text-indent:45.5pt;mso-char-indent-count:
3.99;tab-stops:558.0pt;mso-layout-grid-align:none'><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>图<span lang=EN-US>8-2<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span></span>图<span
lang=EN-US>8-1<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-right:-88.7pt;text-indent:22.8pt;mso-char-indent-count:
2.0;tab-stops:558.0pt;mso-layout-grid-align:none'><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;color:red'>（注：在图<span lang=EN-US>8.3</span>和<span
lang=EN-US>8.4</span>画上了占用块，从原理上，只有空闲块才出现在“可利用空间表”中。）<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><!--[if gte vml 1]><v:shape id="_x0000_s1027" type="#_x0000_t75"
 style='position:absolute;left:0;text-align:left;margin-left:21.6pt;
 margin-top:9.15pt;width:172.5pt;height:198.75pt;z-index:2'>
 <v:imagedata src="da08.files/image003.wmz" o:title=""/>
</v:shape><![if gte mso 9]><o:OLEObject Type="Embed" ProgID="SmartDraw.2"
 ShapeID="_x0000_s1027" DrawAspect="Content" ObjectID="_1149856468">
</o:OLEObject>
<![endif]><v:shape id="_x0000_s1030" type="#_x0000_t75" style='position:absolute;
 left:0;text-align:left;margin-left:210.9pt;margin-top:18pt;width:267.75pt;
 height:175.5pt;z-index:5'>
 <v:imagedata src="da08.files/image004.wmz" o:title=""/>
</v:shape><![if gte mso 9]><o:OLEObject Type="Embed" ProgID="SmartDraw.2"
 ShapeID="_x0000_s1030" DrawAspect="Content" ObjectID="_1149856469">
</o:OLEObject>
<![endif]><![endif]--><![if !vml]><span style='mso-ignore:vglayout'>

<table cellpadding=0 cellspacing=0 align=left>
 <tr>
  <td width=29 height=12></td>
  <td width=230></td>
  <td width=22></td>
  <td width=357></td>
 </tr>
 <tr>
  <td height=12></td>
  <td rowspan=3 align=left valign=top><img width=230 height=265
  src="da08.files/image005.gif" v:shapes="_x0000_s1027"></td>
 </tr>
 <tr>
  <td height=234></td>
  <td></td>
  <td align=left valign=top><img width=357 height=234
  src="da08.files/image006.gif" v:shapes="_x0000_s1030"></td>
 </tr>
 <tr>
  <td height=19></td>
 </tr>
</table>

</span><![endif]><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<br style='mso-ignore:vglayout' clear=ALL>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span
style='font-family:宋体'>图<span lang=EN-US>8-3<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span>图<span lang=EN-US>8-4<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>9</span><span
style='font-family:宋体'>． 因为<span lang=EN-US>768 % 2<sup>7+1</sup>=0</span>，所以<span
lang=EN-US>768</span>和<span lang=EN-US>768+2<sup>7</sup>=896</span>互为伙伴<span
lang=EN-US>, </span>伙伴合并后<span lang=EN-US>,</span>首址为<span lang=EN-US>768,</span>块大小为<span
lang=EN-US>2<sup>8</sup></span>。因为<span lang=EN-US>768 % 2<sup>8+1</sup>=2<sup>8</sup>,</span>所以<span
lang=EN-US>,</span>所以首址<span lang=EN-US>768</span>大小为<span lang=EN-US>2<sup>8</sup></span>的块和首址<span
lang=EN-US>512</span>大小为<span lang=EN-US>2<sup>8</sup></span>的块合并<span
lang=EN-US>,</span>成为首址<span lang=EN-US>512</span>大小为<span lang=EN-US>2<sup>9</sup></span>的空闲块。因为<span
lang=EN-US>128 % 2<sup>7+1</sup>=2<sup>7</sup></span>，其伙伴地址为<span lang=EN-US>128-2<sup>7</sup>=0,
</span>将其插入可利用空间表中。回收后该伙伴系统的状态图如下。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><!--[if gte vml 1]><v:shape id="_x0000_s1031" type="#_x0000_t75"
 style='position:absolute;left:0;text-align:left;margin-left:57pt;margin-top:0;
 width:166.45pt;height:98.35pt;z-index:6'>
 <v:imagedata src="da08.files/image007.wmz" o:title=""/>
</v:shape><![if gte mso 9]><o:OLEObject Type="Embed" ProgID="SmartDraw.2"
 ShapeID="_x0000_s1031" DrawAspect="Content" ObjectID="_1149856470">
</o:OLEObject>
<![endif]><![endif]--><![if !vml]><span style='mso-ignore:vglayout'>

<table cellpadding=0 cellspacing=0 align=left>
 <tr>
  <td width=76 height=0></td>
 </tr>
 <tr>
  <td></td>
  <td><img width=222 height=131 src="da08.files/image008.gif" v:shapes="_x0000_s1031"></td>
 </tr>
</table>

</span><![endif]><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<br style='mso-ignore:vglayout' clear=ALL>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>10</span><span
style='font-family:宋体'>．（<span lang=EN-US>1</span>）系统回收一个起始地址为<span lang=EN-US>559</span>，大小为<span
lang=EN-US>45</span>的空闲块后，因右侧起始地址<span lang=EN-US>604</span>为空闲块，应与之合并。合并后，起始地址为<span
lang=EN-US>559</span>，大小为<span lang=EN-US>167</span>的空闲块。链表状态如图</span><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'>10</span><span
style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-no-proof:yes'>．（</span><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'>1</span><span
style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-no-proof:yes'>）所示。</span><span
lang=EN-US style='font-family:宋体'><o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:10.9pt;mso-char-indent-count:1.0'><!--[if gte vml 1]><v:shape
 id="_x0000_s1028" type="#_x0000_t75" style='position:absolute;left:0;
 text-align:left;margin-left:63pt;margin-top:6.9pt;width:308.25pt;height:70.5pt;
 z-index:3'>
 <v:imagedata src="da08.files/image009.wmz" o:title=""/>
</v:shape><![if gte mso 9]><o:OLEObject Type="Embed" ProgID="SmartDraw.2"
 ShapeID="_x0000_s1028" DrawAspect="Content" ObjectID="_1149856471">
</o:OLEObject>
<![endif]><![endif]--><![if !vml]><span style='mso-ignore:vglayout'>

<table cellpadding=0 cellspacing=0 align=left>
 <tr>
  <td width=84 height=9></td>
 </tr>
 <tr>
  <td></td>
  <td><img width=411 height=94 src="da08.files/image010.gif" v:shapes="_x0000_s1028"></td>
 </tr>
</table>

</span><![endif]><span lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<br style='mso-ignore:vglayout' clear=ALL>

<p class=MsoNormal style='text-indent:10.9pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'>10</span><span
style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-no-proof:yes'>．（</span><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'>1</span><span
style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-no-proof:yes'>）</span><span
lang=EN-US style='font-family:宋体'><o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
style='font-family:宋体'>（<span lang=EN-US>2</span>）系统在接受存储块大小为<span lang=EN-US>100</span>的请求后，将大小为<span
lang=EN-US>117</span>的空闲块分出<span lang=EN-US>100</span>给予用户。在回收一个起始地址为<span
lang=EN-US>515</span>，大小为<span lang=EN-US>44</span>的空闲块之后，因左侧起始地址<span
lang=EN-US>462</span>大小<span lang=EN-US>53</span>和右侧起始地址<span lang=EN-US>559</span>大小<span
lang=EN-US>167</span>均为空闲块，应与之合并。合并后，起始地址为<span lang=EN-US>462</span>，大小为<span
lang=EN-US>264</span>的空闲块。链表状态如图</span><span lang=EN-US style='font-size:10.0pt;
mso-bidi-font-size:12.0pt;mso-no-proof:yes'>10</span><span style='font-size:
10.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-no-proof:yes'>．（</span><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'>2</span><span
style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-no-proof:yes'>）所示</span><span
style='font-family:宋体'>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><!--[if gte vml 1]><v:shape id="_x0000_s1029" type="#_x0000_t75"
 style='position:absolute;left:0;text-align:left;margin-left:71.25pt;
 margin-top:5.85pt;width:234.75pt;height:70.5pt;z-index:4'>
 <v:imagedata src="da08.files/image011.wmz" o:title=""/>
</v:shape><![if gte mso 9]><o:OLEObject Type="Embed" ProgID="SmartDraw.2"
 ShapeID="_x0000_s1029" DrawAspect="Content" ObjectID="_1149856472">
</o:OLEObject>
<![endif]><![endif]--><![if !vml]><span style='mso-ignore:vglayout'>

<table cellpadding=0 cellspacing=0 align=left>
 <tr>
  <td width=95 height=8></td>
 </tr>
 <tr>
  <td></td>
  <td><img width=313 height=94 src="da08.files/image012.gif" v:shapes="_x0000_s1029"></td>
 </tr>
</table>

</span><![endif]><span lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:
12.0pt;mso-no-proof:yes'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:
12.0pt;mso-no-proof:yes'><o:p>&nbsp;</o:p></span></p>

<br style='mso-ignore:vglayout' clear=ALL>

<p class=MsoNormal style='text-indent:10.9pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'><span
style='mso-spacerun:yes'>&nbsp;</span>10</span><span style='font-size:10.0pt;
mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-no-proof:yes'>．（</span><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'>2</span><span
style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-no-proof:yes'>）</span><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'><o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:
12.0pt;mso-no-proof:yes'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:
12.0pt;mso-no-proof:yes'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:
12.0pt;mso-no-proof:yes'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:
12.0pt;mso-no-proof:yes'><o:p>&nbsp;</o:p></span></p>

</div>

</body>

</html>