<div class=Section1 style='layout-grid:15.1pt .9pt;mso-layout-grid-char-alt:
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