da09.htm

1800道数据结构题和答案

  <p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
  lang=EN-US style='font-size:10.5pt;font-family:宋体'>31.×<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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'>
  <p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
  lang=EN-US style='font-size:10.5pt;font-family:宋体'>32.√<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.4pt;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'>
  <p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
  lang=EN-US style='font-size:10.5pt;font-family:宋体'>33.√<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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'>
  <p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
  lang=EN-US style='font-size:10.5pt;font-family:宋体'>34.×<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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'>
  <p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
  lang=EN-US style='font-size:10.5pt;font-family:宋体'>35.√<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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'>
  <p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
  lang=EN-US style='font-size:10.5pt;font-family:宋体'>36.√<o:p></o:p></span></p>
  </td>
 </tr>
</table>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph;
text-indent:22.35pt;mso-char-indent-count:2.0'><span style='font-size:10.5pt;
font-family:宋体'>部分答案解释如下。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>4</span><span
style='font-size:10.5pt;font-family:宋体'>．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>8</span><span
style='font-size:10.5pt;font-family:宋体'>．哈希表的结点中可以包括指针，指向其元素。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>11</span><span
style='font-size:10.5pt;font-family:宋体'>．单链表不能使用折半查找方法。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>20</span><span
style='font-size:10.5pt;font-family:宋体'>．按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。这种插入就不是插入到叶子下面。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>21</span><span
style='font-size:10.5pt;font-family:宋体'>．从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于<span
lang=EN-US>1</span>。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>23</span><span
style='font-size:10.5pt;font-family:宋体'>．某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>24</span><span
style='font-size:10.5pt;font-family:宋体'>．在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>26</span><span
style='font-size:10.5pt;font-family:宋体'>．只有被删除结点是叶子结点时命题才正确。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
style='font-size:10.5pt;font-family:宋体'>三．填空题<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>1</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>n<span
style='mso-spacerun:yes'>&nbsp; </span>n+1<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>2</span>．<span
lang=EN-US>4<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>3</span>．<span lang=EN-US>6,9,11,12 <span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>4</span>．<span lang=EN-US>5<span
style='mso-spacerun:yes'>&nbsp; </span><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>5</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>26</span>（第<span
lang=EN-US>4</span>层是叶子结点，每个结点两个关键字）<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>6</span>．<span lang=EN-US>1,3,6,8,11,13,16,19<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>7</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>5,96<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>8</span>．<span
lang=EN-US>m-1,</span>「<span lang=EN-US>m/2</span></span><span lang=EN-US
style='font-size:10.5pt;font-family:Symbol;mso-ascii-font-family:宋体;mso-hansi-font-family:
宋体;mso-char-type:symbol;mso-symbol-font-family:Symbol'><span style='mso-char-type:
symbol;mso-symbol-font-family:Symbol'>ù</span></span><span lang=EN-US
style='font-size:10.5pt;font-family:宋体'>-1 <span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>9</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>2,4,3<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>10</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>(1)</span>哈希函数<span
lang=EN-US>(2)</span>解决冲突的方法 <span lang=EN-US>(3)</span>选择好的哈希函数 <span
lang=EN-US>(4)</span>处理冲突的方法 <span lang=EN-US>(5)</span>均匀<span lang=EN-US>(6)</span>简单<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>11</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>AVL</span>树<span
style='color:red'>（高度平衡树，高度平衡的二叉排序树），</span>或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于<span
lang=EN-US>1</span>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>12</span><span
style='font-size:10.5pt;font-family:宋体'>．小于等于表长的最大素数或不包含小于<span lang=EN-US>20</span>的质因子的合数<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>13</span>．<span
lang=EN-US>16<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>14</span>．</span><span lang=EN-US style='font-size:10.5pt;font-family:
Symbol;mso-ascii-font-family:宋体;mso-hansi-font-family:宋体;mso-char-type:symbol;
mso-symbol-font-family:Symbol'><span style='mso-char-type:symbol;mso-symbol-font-family:
Symbol'>&euml;</span></span><span style='font-size:10.5pt;font-family:宋体'>㏒<sub><span
lang=EN-US>2</span></sub><sup><span lang=EN-US>n</span></sup>」<span lang=EN-US>+1<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>15</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>(1)45 (2)45 (3)46</span>（块内顺序查找）<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>16</span>．<span
lang=EN-US>k(k+1)/2<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>17</span>．<span
lang=EN-US>30</span>，<span lang=EN-US>31.5</span>（块内顺序查找）<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>18</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>(1)</span>顺序存储或链式存储 <span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;</span>(2)</span>顺序存储且有序 <span
lang=EN-US>(3)</span>块内顺序存储，块间有序 <span lang=EN-US>(4) </span><span
style='color:red'>散列</span>存储<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>19</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>(n+1)/2<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>20</span>．<span lang=EN-US
style='color:red'>(n+1)/n*log<sub>2</sub>(n+1)-1</span><span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>21</span>．结点的左子树的高度减去结点的右子树的高度<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>22</span><span
style='font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>(1)</span>顺序表<span
lang=EN-US>(2)</span>树表<span lang=EN-US>(3)</span>哈希表<span lang=EN-US>(4)</span>开放定址方法<span
lang=EN-US>(5)</span>链地址方法<span lang=EN-US>(6)</span>再哈希<span lang=EN-US>(7)</span>建立公共溢出区<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>23</span><span
style='font-size:10.5pt;font-family:宋体'>．直接定址法<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>24</span>．<span
lang=EN-US>log</span></span><sub><span lang=EN-US style='font-size:10.5pt;
font-family:Symbol;mso-ascii-font-family:宋体;mso-hansi-font-family:宋体;
mso-char-type:symbol;mso-symbol-font-family:Symbol'><span style='mso-char-type:
symbol;mso-symbol-font-family:Symbol'>é</span></span></sub><sub><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>m/2</span></sub><sub><span
lang=EN-US style='font-size:10.5pt;font-family:Symbol;mso-ascii-font-family:
宋体;mso-hansi-font-family:宋体;mso-char-type:symbol;mso-symbol-font-family:Symbol'><span
style='mso-char-type:symbol;mso-symbol-font-family:Symbol'>ù</span></span></sub><span
lang=EN-US style='font-size:10.5pt;font-family:宋体'>(<sub><!--[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_i1025" type="#_x0000_t75" style='width:27pt;
 height:30.75pt' o:ole="">
 <v:imagedata src="da09.files/image001.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=36 height=41
src="da09.files/image002.gif" v:shapes="_x0000_i1025"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1025"
  DrawAspect="Content" ObjectID="_1149856479">
 </o:OLEObject>
</xml><![endif]-->)+1<span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='