da04.htm

1800道数据结构题和答案

3686'>

<p class=MsoNormal align=center style='text-align:center'><span
style='font-size:14.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-bidi-font-weight:
bold'>第四章 串<span lang=EN-US> <o:p></o:p></span></span></p>

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

<table class=MsoNormalTable border=1 cellspacing=0 cellpadding=0
 style='margin-left:23.3pt;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;mso-yfti-lastrow:yes;
  height:7.15pt'>
  <td width=53 valign=top style='width:39.55pt;border:solid windowtext 1.0pt;
  mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt;height:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>1.B<o:p></o:p></span></p>
  </td>
  <td width=53 valign=top style='width:39.65pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>2.E<o:p></o:p></span></p>
  </td>
  <td width=53 valign=top style='width:39.55pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>3.C<o:p></o:p></span></p>
  </td>
  <td width=53 valign=top style='width:39.55pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>4.A<o:p></o:p></span></p>
  </td>
  <td width=53 valign=top style='width:39.55pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>5.C<o:p></o:p></span></p>
  </td>
  <td width=49 valign=top style='width:36.45pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>6.A<o:p></o:p></span></p>
  </td>
  <td width=45 valign=top style='width:33.85pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>7.1D<o:p></o:p></span></p>
  </td>
  <td width=45 valign=top style='width:33.85pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>7.2F<o:p></o:p></span></p>
  </td>
  <td width=65 valign=top style='width:49.0pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>8.B</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体'>注<span lang=EN-US><o:p></o:p></span></span></p>
  </td>
  <td width=46 valign=top style='width:34.55pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>9.D<o:p></o:p></span></p>
  </td>
  <td width=45 valign=top style='width:33.8pt;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:7.15pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>10.B<o:p></o:p></span></p>
  </td>
  <td width=45 valign=top style='width:33.85pt;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:7.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 lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。</span><span
style='font-family:宋体'>若字符串长度为<span lang=EN-US>n</span>（<span lang=EN-US>n&gt;0</span>），长为<span
lang=EN-US>n</span>的子串有<span lang=EN-US>1</span>个，长为<span lang=EN-US>n-1</span>的子串有<span
lang=EN-US>2</span>个，长为<span lang=EN-US>n-2</span>的子串有<span lang=EN-US>3</span>个，……，长为<span
lang=EN-US>1</span>的子串有<span lang=EN-US>n</span>个。由于空串是任何串的子串，所以本题的答案为：<span
lang=EN-US>8*</span>（<span lang=EN-US>8+1</span>）<span lang=EN-US>/2+1=37</span>。故选<span
lang=EN-US>B</span>。但某些教科书上认为“</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体'>空串是任意串的子串</span><span lang=EN-US style='font-family:宋体'>”</span><span
style='font-family:宋体'>无意义，所以认为选<span lang=EN-US>C</span>。为避免考试中的二意性，编者认为第<span
lang=EN-US>9</span>题出得好。</span><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'><o:p></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='margin-left:23.3pt;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;mso-yfti-lastrow:yes'>
  <td width=47 valign=top style='width:35.4pt;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 width=52 valign=top style='width:39.1pt;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.√<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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.√<o:p></o:p></span></p>
  </td>
  <td width=52 valign=top style='width:39.1pt;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:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=53 valign=top style='width:39.7pt;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:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=52 valign=top style='width:39.1pt;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:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=53 valign=top style='width:39.7pt;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:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.4pt;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:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
 </tr>
</table>

<p class=MsoNormal style='margin-left:11.4pt;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='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span style='font-family:宋体'>三．填空题<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='font-family:宋体'>1</span><span style='font-family:
宋体'>．<span lang=EN-US>(1) </span>由空格字符（<span lang=EN-US>ASCII</span>值<span
lang=EN-US>32</span>）所组成的字符串<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>(2)</span>空格个数<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>2</span>．字符<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='font-family:宋体'>3</span><span style='font-family:
宋体'>．任意个连续的字符组成的子序列<span lang=EN-US><span style='mso-spacerun:yes'>&nbsp;
</span><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;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>4</span>．<span lang=EN-US>5<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>5.O(m+n)<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>6</span><span
style='font-family:宋体'>．<span lang=EN-US>01122312<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>7</span>．<span lang=EN-US>01010421<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>8</span>．<span lang=EN-US>(1)</span>模式匹配<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>(2)</span>模式串<span