da04.htm

1800道数据结构题和答案

style='font-family:宋体'>13</span><span style='font-family:宋体'>．<span lang=EN-US>next</span>定义见题上面<span
lang=EN-US>6</span>和下面题<span lang=EN-US>20</span>。串<span lang=EN-US>p</span>的<span
lang=EN-US>next</span>函数值为：<span lang=EN-US>01212345634</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋体'>14</span><span style='font-family:宋体'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>S</span>的<span lang=EN-US>next</span>与<span
lang=EN-US>nextval</span>值分别为<span lang=EN-US>012123456789</span>和<span
lang=EN-US>002002002009</span>，<span lang=EN-US>p</span>的<span lang=EN-US>next</span>与<span
lang=EN-US>nextval</span>值分别为<span lang=EN-US>012123</span>和<span lang=EN-US>002003</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:208.5pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span style='font-family:
宋体'>（<span lang=EN-US>2</span>）利用<span lang=EN-US>BF</span>算法的匹配过程：<span
lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span>利用<span lang=EN-US>KMP</span>算法的匹配过程：<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;tab-stops:181.8pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>第一趟匹配：<span lang=EN-US> aabaabaabaac<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span>第一趟匹配：<span lang=EN-US>aabaabaabaac<o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>aabaac(i=6,j=6)<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>aabaac(i=6,j=6)
<o:p></o:p></span></p>

<p class=MsoNormal style='tab-stops:166.5pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span style='font-family:
宋体'>第二趟匹配：<span lang=EN-US> aabaabaabaac<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span>第二趟匹配：<span lang=EN-US>aabaabaabaac<o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:166.5pt'><span lang=EN-US style='font-family:
宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>aa(i=3,j=2)<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>(aa)baac <o:p></o:p></span></p>

<p class=MsoNormal style='tab-stops:166.5pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span style='font-family:
宋体'>第三趟匹配：<span lang=EN-US> aabaabaabaac<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span>第三趟匹配：<span lang=EN-US>aabaabaabaac<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:57.0pt;mso-char-indent-count:5.0;
tab-stops:166.5pt'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>a(i=3,j=1)<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>(</span><span style='font-family:宋体'>成功<span lang=EN-US>) (aa)baac<o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:22.35pt;
mso-char-indent-count:1.96'><span style='font-family:宋体'>第四趟匹配：<span
lang=EN-US> aabaabaabaac<o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='margin-left:11.4pt;mso-para-margin-left:
1.0gd;text-align:left;text-indent:45.6pt;mso-char-indent-count:4.0'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>aabaac(i=9,j=6)<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:22.35pt;
mso-char-indent-count:1.96'><span style='font-family:宋体'>第五趟匹配：<span
lang=EN-US> aabaabaabaac<o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='margin-left:11.4pt;mso-para-margin-left:
1.0gd;text-align:left;text-indent:51.2pt;mso-char-indent-count:4.49'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>aa(i=6,j=2)<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:22.35pt;
mso-char-indent-count:1.96'><span style='font-family:宋体'>第六趟匹配：<span
lang=EN-US> aabaabaabaac<o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='margin-left:11.4pt;mso-para-margin-left:
1.0gd;text-align:left;text-indent:45.6pt;mso-char-indent-count:4.0'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>a(i=6,j=1)<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:22.35pt;
mso-char-indent-count:1.96'><span style='font-family:宋体'>第七趟匹配：<span
lang=EN-US> aabaabaabaac<o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:33.5pt;
mso-char-indent-count:2.94'><span lang=EN-US style='font-family:宋体'>(</span><span
style='font-family:宋体'>成功<span lang=EN-US>)<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>aabaac(i=13,j=7)<o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp; </span>15</span><span
style='font-family:宋体'>．（<span lang=EN-US>1</span>）<span lang=EN-US>p</span>的<span
lang=EN-US>nextval</span>函数值为<span lang=EN-US>0110132</span>。（<span lang=EN-US>p</span>的<span
lang=EN-US>next</span>函数值为<span lang=EN-US>0111232</span>）。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
style='font-family:宋体'>（<span lang=EN-US>2</span>）利用<span lang=EN-US>KMP(</span>改进的<span
lang=EN-US>nextval)</span>算法，每趟匹配过程如下：<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>第一趟匹配：<span lang=EN-US> abcaabbabcabaacbacba<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>abcab(i=5,j=5)<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>第二趟匹配：<span lang=EN-US> abcaabbabcabaacbacba<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>abc(i=7,j=3)<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>第三趟匹配：<span lang=EN-US> abcaabbabcabaacbacba<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>a(i=7,j=1)<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>第四趟匹配：<span lang=EN-US> abcaabbabcabaac bacba<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span>(</span><span style='font-family:宋体'>成功<span lang=EN-US>)<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><span style='mso-spacerun:yes'>&nbsp;&nbsp;</span>abcabaa(i=15,j=8)<o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋体'>16</span><span style='font-family:宋体'>．<span lang=EN-US>KMP</span>算法的时间复杂性是<span
lang=EN-US>O</span>（<span lang=EN-US>m+n</span>）。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋体'>p</span><span style='font-family:宋体'>的<span
lang=EN-US>next</span>和<span lang=EN-US>nextval</span>值分别为<span lang=EN-US>01112212321</span>和<span
lang=EN-US>01102201320</span>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋体'>17</span><span style='font-family:宋体'>．（<span lang=EN-US>1</span>）<span
lang=EN-US>p</span>的<span lang=EN-US>nextval</span>函数值为<span lang=EN-US>01010</span>。（<span
lang=EN-US>next</span>函数值为<span lang=EN-US>01123</span>）<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;text-indent:-34.2pt;mso-char-indent-count:
-3.0;tab-stops:135.0pt'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span><span
style='font-family:宋体'>（<span lang=EN-US>2</span>）利用所得<span lang=EN-US>nextval</span>数值，手工模拟对<span
lang=EN-US>s</span>的匹配过程，与上面<span lang=EN-US>16</span>题类似，为节省篇幅，故略去。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;text-indent:-34.2pt;mso-char-indent-count:
-3.0;tab-stops:135.0pt'><span lang=EN-US style='font-family:宋体'>18</span><span
style='font-family:宋体'>．模式串<span lang=EN-US>T</span>的<span lang=EN-US>next</span>和<span
lang=EN-US>nextval</span>值分别为<span lang=EN-US>0121123</span>和<span lang=EN-US>0021002</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋体'>19</span><span style='font-family:宋体'>．第<span lang=EN-US>4</span>行的<span
lang=EN-US>p[J]=p[K]</span>语句是测试模式串的第<span lang=EN-US>J</span>个字符是否等于第<span
lang=EN-US>K</span>个字符，如是，则指针<span lang=EN-US>J</span>和<span lang=EN-US>K</span>均增加<span
lang=EN-US>1</span>，继续比较。第<span lang=EN-US>6</span>行的<span lang=EN-US>p[J]=p[K]</span>语句的意义是，当第<span
lang=EN-US>J</span>个字符在模式匹配中失配时，若第<span lang=EN-US>K</span>个字符和第<span
lang=EN-US>J</span>个字符不等，则下个与主串匹配的字符是第<span lang=EN-US>K</span>个字符；否则，若第<span
lang=EN-US>K</span>个字符和第<span lang=EN-US>J</span>个字符相等，则下个与主串匹配的字符是第<span
lang=EN-US>K</span>个字符失配时的下一个（即<span lang=EN-US>NEXTVAL[K]</span>）。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span><span
style='font-family:宋体'>该算法在最坏情况下的时间复杂度<span lang=EN-US>O</span>（<span
lang=EN-US>m</span></span><sup><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>2</span></sup><span style='font-family:宋体'>）。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋体'>20</span><span style='font-family:宋体'>．（<span lang=EN-US>1</span>）当模式串中第一个字符与主串中某字符比较不等（失配）时，<span
lang=EN-US>next[1]=0</span>表示模式串中已没有字符可与主串中当前字符<span lang=EN-US>s[i]</span>比较，主串当前指针应后移至下一字符，再和模式串中第一字符进行比较。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span><span
style='font-family:宋体'>（<span lang=EN-US>2</span>）当主串第<span lang=EN-US>i</span>个字符与模式串中第<span
lang=EN-US>j</span>个字符失配时，若主串<span lang=EN-US>i</span>不回溯，则假定模式串第<span
lang=EN-US>k</span>个字符与主串第<span lang=EN-US>i</span>个字符比较，<span lang=EN-US>k</span>值应满足条件<span
lang=EN-US>1&lt;k&lt;j</span>并且‘<span lang=EN-US>p</span><sub>１</sub>…<span
lang=EN-US>p<sub>k-1</sub></span>’<span lang=EN-US>=</span>‘<span lang=EN-US>p<sub>j-k+1</sub></span>…<span
lang=EN-US>p<sub>j-1</sub></span>’，即<span lang=EN-US>k</span>为模式串向后移动的距离，<span
lang=EN-US>k</span>值有多个，为了不使向右移动丢失可能的匹配，<span lang=EN-US>k</span>要取大，由于<span
lang=EN-US>max{k}</span>表示移动的最大距离，所以取<span lang=EN-US>max{k}</span>，<span
lang=EN-US>k</span>的最大值为<span lang=EN-US>j-1</span>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span><span style='font-family:
宋体'>（<span lang=EN-US>3</span>）在上面两种情况外，发生失配时，主串指针<span lang=EN-US>i</span>不回溯，在最坏情况下，模式串从第<span
lang=EN-US>1</span>个字符开始与主串第<span lang=EN-US>i</span>个字符比较，以便不致丢失可能的匹配。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>21</span><span
style='font-family:宋体'>．这里失败函数<span lang=EN-US>f</span>，即是通常讲的模式串的<span
lang=EN-US>next</span>函数，其定义见本章应用题的第<span lang=EN-US>6</span>题。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.75pt'><span style='font-family:宋体'>进行模式匹配时，若主串第<span
lang=EN-US>i</span>个字符与模式串第<span l