da08.htm

1800道数据结构题和答案

style='mso-spacerun:yes'>&nbsp;&nbsp; </span></sup><span
style='mso-spacerun:yes'>&nbsp;</span>(</span><span style='font-family:宋体'>若<span
lang=EN-US>p % 2<sup>k+1</sup>=0),</span>或<span lang=EN-US>buddy(p,k)=p-2<sup>k<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span></sup><span
style='mso-spacerun:yes'>&nbsp;</span>(</span>若<span lang=EN-US>p % 2<sup>k+1</sup>=2<sup>k</sup>)<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>2</span><span
style='font-family:宋体'>．首次拟合法；从链表头指针开始查找，找到第一个≥所需空间的结点即分配。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:6.4pt;mso-para-margin-left:.56gd;
text-indent:11.5pt;mso-char-indent-count:1.01'><span style='font-family:宋体'>最佳拟合法：链表结点大小增序排列，找到第一个≥所需空间的结点即分配。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:6.4pt;mso-para-margin-left:.56gd;
text-indent:11.5pt;mso-char-indent-count:1.01'><span style='font-family:宋体'>最差拟合法：链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
style='font-family:宋体'>首次拟合法适合事先不知道请求分配和释放信息的情况<span lang=EN-US>,</span>分配时需查询<span
lang=EN-US>,</span>释放时插在表头。 最佳拟合法适用于请求分配内存大小范围较宽的系统<span lang=EN-US>,</span>释放时容易产生存储量很小难以利用的内存碎片<span
lang=EN-US>,</span>同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。 最差拟合法适合请求分配内存大小范围较窄的系统<span
lang=EN-US>,</span>分配时不查询<span lang=EN-US>,</span>回收时查询<span lang=EN-US>,</span>以便插入适当位置。<span
lang=EN-US><o:p></o:p></span></span></p>

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

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>5</span><span
style='font-family:宋体'>．（<span lang=EN-US>1</span>）<span lang=EN-US>buddy(1664,7)=1664-128=1536<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span>（<span lang=EN-US>2</span>）<span
lang=EN-US>buddy(2816,6)=2816+64=2880<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:5.5pt;text-indent:-5.5pt'><span
lang=EN-US style='font-family:宋体'>6</span><span style='font-family:宋体'>．动态存储分配伙伴系统的基本思想请参见上面题<span
lang=EN-US>1</span>。边界标识法在每块的首尾均有“占用”<span lang=EN-US>/</span>“空闲”标志，空闲块合并方便。伙伴系统算法简单，速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>7</span><span
style='font-family:宋体'>．组织成循环链表的可利用空间表的结点大小按递增序排列时<span lang=EN-US>, </span>首次适配策略就转变为最佳适配策略。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>8</span><span
style='font-family:宋体'>．因为<span lang=EN-US>512=2<sup>9</sup>,</span>可利用空间表的初始状态图如<span
lang=EN-US>8-1</span>所示。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
style='font-family:宋体'>当用户申请大小为<span lang=EN-US>23</span>的内存块时<span lang=EN-US>,</span>因<span
lang=EN-US>2<sup>4</sup>&lt;23&lt;=2<sup>5</sup>,</span>但没有大小为<span lang=EN-US>2<sup>5</sup></span>的块<span
lang=EN-US>,</span>只有大小为<span lang=EN-US>2<sup>9</sup></span>的块<span
lang=EN-US>,</span>故将<span lang=EN-US>2<sup>9</sup></span>的块分裂成两个大小为<span
lang=EN-US>2<sup>8</sup></span>的块<span lang=EN-US>,</span>其中大小为<span
lang=EN-US>2<sup>8</sup></span>的一块挂到可利用空间表上<span lang=EN-US>,</span>另一块再分裂成两个大小为<span
lang=EN-US>2<sup>7</sup></span>的块。又将其中大小为<span lang=EN-US>2<sup>7</sup></span>的一块挂到可利用空间表上<span
lang=EN-US>,</span>另一块再分裂成两个大小为<span lang=EN-US>2<sup>6</sup></span>的块<span
lang=EN-US>,</span>一块<span lang=EN-US>2<sup>6</sup></span>的块挂到可利用空间表上<span
lang=EN-US>,</span>另一块分裂成两个大小为<span lang=EN-US>2<sup>5</sup></span>的块<span
lang=EN-US>,</span>其中一块挂到可利用空间表上<span lang=EN-US>,</span>另一块分给用户<span
lang=EN-US>(</span>地址<span lang=EN-US>0—31)</span>。如此下去<span lang=EN-US>,</span>最后每个用户得到的存储空间的起始地址如图<span
lang=EN-US>8-2, 6</span>个用户分配所需要的存储空间后可利用空间表的状态如图<span lang=EN-US>8-3</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
style='font-family:宋体'>在回收时<span lang=EN-US>,</span>因为给申请<span lang=EN-US>45</span>的用户分配了<span
lang=EN-US>2<sup>6</sup>,</span>其伙伴地址是<span lang=EN-US style='color:red'>0</span><span
lang=EN-US>,</span>在占用中<span lang=EN-US>,</span>不能合并<span lang=EN-US>,</span>只能挂到可利用空间表上。在回收大小为<span
lang=EN-US>52</span>的占用块时<span lang=EN-US>,</span>其伙伴地址是<span lang=EN-US>192,</span>也在占用。回收大小为<span
lang=EN-US>11</span>的占用块时<span lang=EN-US>,</span>其伙伴地址是<span lang=EN-US>48,</span>可以合并为大小<span
lang=EN-US>2<sup>5</sup></span>的块<span lang=EN-US>, </span>挂到可利用空间表上。回收<span
lang=EN-US>3</span>个占用块之后可利用空间表的状态如图<span lang=EN-US>8-4</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.8pt;mso-char-indent-count:2.0'><!--[if gte vml 1]><v:shapetype
 id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"
 path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
 <v:stroke joinstyle="miter"/>
 <v:formulas>
  <v:f eqn="if lineDrawn pixelLineWidth 0"/>
  <v:f eqn="sum @0 1 0"/>
  <v:f eqn="sum 0 0 @1"/>
  <v:f eqn="prod @2 1 2"/>
  <v:f eqn="prod @3 21600 pixelWidth"/>
  <v:f eqn="prod @3 21600 pixelHeight"/>
  <v:f eqn="sum @0 0 1"/>
  <v:f eqn="prod @6 1 2"/>
  <v:f eqn="prod @7 21600 pixelWidth"/>
  <v:f eqn="sum @8 21600 0"/>
  <v:f eqn="prod @7 21600 pixelHeight"/>
  <v:f eqn="sum @10 21600 0"/>
 </v:formulas>
 <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
 <o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_s1026" type="#_x0000_t75" style='position:absolute;
 left:0;text-align:left;margin-left:228pt;margin-top:14.85pt;width:108pt;
 height:124.75pt;z-index:1'>
 <v:imagedata src="da08.files/image001.wmz" o:title=""/>
</v:shape><![if gte mso 9]><o:OLEObject Type="Embed" ProgID="SmartDraw.2"
 ShapeID="_x0000_s1026" DrawAspect="Content" ObjectID="_1149856467">
</o:OLEObject>
<![endif]><![endif]--><![if !vml]><span style='mso-ignore:vglayout'>

<table cellpadding=0 cellspacing=0 align=left>
 <tr>
  <td width=304 height=20></td>
 </tr>
 <tr>
  <td></td>
  <td><img width=144 height=166 src="da08.files/image002.gif" v:shapes="_x0000_s1026"></td>
 </tr>
</table>

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

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

<table class=MsoNormalTable border=1 cellspacing=0 cellpadding=0 align=left
 style='border-collapse:collapse;border:none;mso-border-alt:solid windowtext .5pt;
 mso-table-lspace:9.0pt;margin-left:6.75pt;mso-table-rspace:9.0pt;margin-right:
 6.75pt;mso-table-anchor-vertical:paragraph;mso-table-anchor-horizontal:margin;
 mso-table-left:left;mso-table-top:11.45pt;mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
 mso-border-insideh:.5pt solid windowtext;mso-border-insidev:.5pt solid windowtext'>
 <tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes;height:10.6pt'>
  <td valign=top style='border:solid windowtext 1.0pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:10.6pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span style='font-family:宋体;mso-ascii-font-family:
  "Times New Roman";mso-hansi-font-family:"Times New Roman"'>存储大小</span></p>
  </td>
  <td valign=top style='border:solid windowtext 1.0pt;border-left:none;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:10.6pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span style='font-family:宋体;mso-ascii-font-family:
  "Times New Roman";mso-hansi-font-family:"Times New Roman"'>起始地址</span></p>
  </td>
 </tr>
 <tr style='mso-yfti-irow:1;height:11.1pt'>
  <td valign=top style='border:solid windowtext 1.0pt;border-top:none;
  mso-border-top-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:11.1pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>23</span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:11.1pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>0</span></p>
  </td>
 </tr>
 <tr style='mso-yfti-irow:2;height:10.6pt'>
  <td valign=top style='border:solid windowtext 1.0pt;border-top:none;
  mso-border-top-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:10.6pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>45</span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:10.6pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>64</span></p>
  </td>
 </tr>
 <tr style='mso-yfti-irow:3;height:11.1pt'>
  <td valign=top style='border:solid windowtext 1.0pt;border-top:none;
  mso-border-top-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:11.1pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>52</span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:11.1pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>128</span></p>
  </td>
 </tr>
 <tr style='mso-yfti-irow:4;height:10.6pt'>
  <td valign=top style='border:solid windowtext 1.0pt;border-top:none;
  mso-border-top-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:10.6pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>100</span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:10.6pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>256</span></p>
  </td>
 </tr>
 <tr style='mso-yfti-irow:5;height:11.1pt'>
  <td valign=top style='border:solid windowtext 1.0pt;border-top:none;
  mso-border-top-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:11.1pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>11</span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:11.1pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>32</span></p>
  </td>
 </tr>
 <tr style='mso-yfti-irow:6;mso-yfti-lastrow:yes;height:11.1pt'>
  <td valign=top style='border:solid windowtext 1.0pt;border-top:none;
  mso-border-top-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:11.1pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>19</span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt;height:11.1pt'>
  <p class=MsoNormal align=left style='text-align:left;mso-element:frame;
  mso-element-frame-hspace:9.0pt;mso-element-wrap:around;mso-element-anchor-vertical:
  paragraph;mso-element-anchor-horizontal:margin;mso-element-top:11.45pt;
  mso-height-rule:exactly'><span lang=EN-US><span
  style='mso-spacerun:yes'>&nbsp; </span>192</span></p>
  </td>
 </tr>
</table>

<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>