da10.htm

2000题经典数据结构试题

  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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>58.A<o:p></o:p></span></p>
  </td>
  <td colspan=5 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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>59.1C 59.2A 59.3D 59.4B 59.5G<o:p></o:p></span></p>
  </td>
 </tr>
 <tr style='mso-yfti-irow:5;mso-yfti-lastrow:yes;height:5.15pt'>
  <td colspan=3 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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>60.1B 60.2C 60.3A<o:p></o:p></span></p>
  </td>
  <td colspan=5 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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>61.1B 61.2D 61.3B 61.4C 61.5F<o:p></o:p></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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>62.A<o:p></o:p></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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>63.A<o:p></o:p></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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>64.B<o:p></o:p></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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>65.A<o:p></o:p></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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>66.A<o:p></o:p></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:5.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
 </tr>
</table>

<p class=MsoNormal><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>部分答案解释如下：<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>18. </span><span
style='font-family:宋体'>对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。 <span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>20. </span><span
style='font-family:宋体'>本题为步长为<span lang=EN-US>3</span>的一趟希尔排序。<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>24.</span>枢轴是<span
lang=EN-US>73</span>。</span><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span><o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>49. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于</span><sub><span lang=EN-US
style='font-family:宋体'><!--[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:5.25pt;
 height:13.5pt' fillcolor="window">
 <v:imagedata src="da10.files/image001.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=7 height=18
src="da10.files/image002.gif" v:shapes="_x0000_i1025"><![endif]></span></sub><span
lang=EN-US style='font-family:宋体'>n/2<sub><!--[if gte vml 1]><v:shape id="_x0000_i1026"
 type="#_x0000_t75" style='width:5.25pt;height:13.5pt' fillcolor="window">
 <v:imagedata src="da10.files/image003.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=7 height=18
src="da10.files/image004.gif" v:shapes="_x0000_i1026"><![endif]></sub></span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>的结点上。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>64. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>因组与组之间已有序，故将<span lang=EN-US>n/k</span>个组分别排序即可，基于比较的排序方法每组的时间下界为<span
lang=EN-US>O(klog<sub>2</sub>k),</span>全部时间下界为<span lang=EN-US>O(nlog<sub>2</sub>k)</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

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

<p class=MsoNormal><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>二、判断题<span
lang=EN-US><o:p></o:p></span></span></p>

<table class=MsoNormalTable border=1 cellspacing=0 cellpadding=0
 style='border-collapse:collapse;border:none;mso-border-alt:solid windowtext .5pt;
 mso-yfti-tbllook:191;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'>
  <td valign=top style='border:solid windowtext 1.0pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>1.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>√<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>2.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>3.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>4.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>5.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>6.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>7.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>8.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>9.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>10.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>11.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>12.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>13.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></span></p>
  </td>
 </tr>
 <tr style='mso-yfti-irow:1'>
  <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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>14.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>√<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>15.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>√<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>16.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>17.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>18.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>19.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>20.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span></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'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>21.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>×<span lang=EN-US><o:p></o:p></span>