st04.htm

1800道数据结构题和答案

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:39.1pt;mso-char-indent-count:3.43;tab-stops:34.95pt 58.25pt 69.9pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;
</span>}<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>else <u>(4)</u></span><u><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'> ___</span></u><span
lang=EN-US style='font-family:宋体'>;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>}<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><u><span
style='mso-spacerun:yes'>&nbsp;</span>(5) __<o:p></o:p></u></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:17.1pt;mso-char-indent-count:1.5'><span lang=EN-US
style='font-family:宋体'>}<span style='mso-spacerun:yes'>&nbsp; </span>}<span
style='mso-spacerun:yes'>&nbsp; </span></span><span style='font-family:宋体'>【上海大学<span
lang=EN-US> 2000 </span></span><!--[if supportFields]><span lang=EN-US
style='font-family:宋体'><span style='mso-element:field-begin'></span><span
style='mso-spacerun:yes'>&nbsp;</span>= 1 \* CHINESENUM3 <span
style='mso-element:field-separator'></span></span><![endif]--><span
style='font-family:宋体;mso-no-proof:yes'>一</span><!--[if supportFields]><span
lang=EN-US style='font-family:宋体'><span style='mso-element:field-end'></span></span><![endif]--><span
style='font-family:宋体'>、<span lang=EN-US>2 </span>（<span lang=EN-US>10</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>15</span><span
style='font-family:宋体'>．完善算法：求<span lang=EN-US>KMP</span>算法中<span lang=EN-US>next</span>数组。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:3.0gd'><span
lang=EN-US style='font-family:宋体'>PROC get _next(t:string,VAR next:ARRAY[1..t.len]
OF integer);<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:3.0gd'><span
lang=EN-US style='font-family:宋体'>BEGIN <o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:3.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;</span>j:=1; k:=<u>(1)__</u>; <span
style='mso-spacerun:yes'>&nbsp;</span>next[1]:=0;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:3.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;</span>WHILE j&lt;t.len DO <o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:3.0gd;
text-indent:5.6pt;mso-char-indent-count:.49'><span lang=EN-US style='font-family:
宋体'>IF k=0 OR t.ch[j]=t.ch[k] THEN BEGIN j:=j+1; k:=k+1; next[j]:=<span
style='color:red'>k</span>;END<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:3.0gd;
text-indent:153.55pt;mso-char-indent-count:13.47'><span lang=EN-US
style='font-family:宋体'>ELSE k:=</span><u><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>(2)___</span></u><span lang=EN-US style='font-family:
宋体'>;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:3.0gd'><span
lang=EN-US style='font-family:宋体'>END;<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
style='font-family:宋体'>【中山大学<span lang=EN-US> 1998 </span></span><!--[if supportFields]><span
lang=EN-US style='font-family:宋体'><span style='mso-element:field-begin'></span><span
style='mso-spacerun:yes'>&nbsp;</span>= 4 \* CHINESENUM3 <span
style='mso-element:field-separator'></span></span><![endif]--><span
style='font-family:宋体;mso-no-proof:yes'>四</span><!--[if supportFields]><span
lang=EN-US style='font-family:宋体'><span style='mso-element:field-end'></span></span><![endif]--><span
style='font-family:宋体'>、<span lang=EN-US>1 </span>（<span lang=EN-US>4</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>16</span><span
style='font-family:宋体'>．下面函数<span lang=EN-US>index</span>用于求<span lang=EN-US>t</span>是否为<span
lang=EN-US>s</span>的子串，若是返回<span lang=EN-US>t</span>第一次出现在<span lang=EN-US>s</span>中的序号<span
lang=EN-US>(</span>从<span lang=EN-US>1</span>开始计<span lang=EN-US>)</span>，否则返回<span
lang=EN-US>0</span>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.35pt;mso-char-indent-count:1.96'><span
style='font-family:宋体'>例如<span lang=EN-US>:s=</span>‘<span lang=EN-US>abcdefcdek</span>’，<span
lang=EN-US>t=</span>‘<span lang=EN-US>cde</span>’<span lang=EN-US>,</span>则<span
lang=EN-US>indse(s,t)=3, index(s,</span>’<span lang=EN-US>aaa</span>’<span
lang=EN-US>)=0 </span>。已知<span lang=EN-US>t</span>，<span lang=EN-US>s</span>的串长分别是<span
lang=EN-US>mt,ms<span style='mso-spacerun:yes'>&nbsp; </span><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
lang=EN-US style='font-family:宋体'>FUNC index(s,t,ms,mt);<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:34.1pt;mso-char-indent-count:2.99'><span
lang=EN-US style='font-family:宋体'>i:=1;j:=1;<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:34.1pt;mso-char-indent-count:2.99'><span
lang=EN-US style='font-family:宋体'>WHILE<span style='mso-spacerun:yes'>&nbsp;
</span>(i&lt;ms) AND (j&lt;mt) DO<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:34.1pt;mso-char-indent-count:2.99'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;
</span>IF s[i]=t[j] THEN<span style='mso-spacerun:yes'>&nbsp; </span>[ <u>(1)</u></span><u><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>__</span></u><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>;</span><span
lang=EN-US style='font-family:宋体'> <u>(2)</u></span><u><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>__</span></u><span lang=EN-US
style='font-family:宋体'>]<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:34.1pt;mso-char-indent-count:2.99'><span
lang=EN-US style='font-family:宋体'><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;</span>ELSE
[ <u>(3)</u></span><u><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>___</span></u><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>;</span><span lang=EN-US style='font-family:宋体'> <u>(4)</u></span><u><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>_</span></u><span
lang=EN-US style='font-family:宋体'> ] <o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:34.1pt;mso-char-indent-count:2.99'><span
lang=EN-US style='font-family:宋体'>IF j&gt;mt THEN<span
style='mso-spacerun:yes'>&nbsp; </span>return <u>(5)</u></span><u><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>____</span></u><span
lang=EN-US style='font-family:宋体'>; ELSE<span style='mso-spacerun:yes'>&nbsp;
</span>return <u>(6)</u></span><u><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>__</span></u><span lang=EN-US style='font-family:宋体'><o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
lang=EN-US style='font-family:宋体'>ENDF;<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
style='font-family:宋体'>【南京理工大学<span lang=EN-US> 1999 </span>三、<span lang=EN-US>2
</span>（<span lang=EN-US>6</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-right:19.3pt'><span lang=EN-US
style='font-family:宋体'>17</span><span style='font-family:宋体'>．阅读下列程序说明和<span
lang=EN-US>pascal</span>程序<span lang=EN-US>,</span>把应填入其中的（<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span></span>）处的字句写在答题纸上。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-right:19.3pt'><span style='font-family:宋体'>程序说明：<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-right:19.3pt;text-indent:22.8pt;mso-char-indent-count:
2.0'><span style='font-family:宋体'>本程序用于判别输入的字符串是否为如下形式的字符串<span lang=EN-US>:<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-right:19.3pt;text-indent:22.8pt;mso-char-indent-count:
2.0'><span lang=EN-US style='font-family:宋体'>W&amp;M$ </span><span
style='font-family:宋体'>其中<span lang=EN-US>,</span>子字符串<span lang=EN-US>M</span>是子字符串<span
lang=EN-US>W</span>的字符反向排列<span lang=EN-US>,</span>在此假定<span lang=EN-US>W</span>不含有字符<span
lang=EN-US>&amp;</span>和字符<span lang=EN-US>$,</span>字符<span lang=EN-US>&amp;</span>用作<span
lang=EN-US>W</span>与<span lang=EN-US>M</span>的分隔符<span lang=EN-US>,</span>字符<span
lang=EN-US>$</span>用作字符串的输入结束符。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:11.4pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
1.0gd;mso-para-margin-bottom:.0001pt;text-indent:11.4pt;mso-char-indent-count:
1.0'><span style='font-family:宋体'>例如<span lang=EN-US>,</span>对输入字符串<span
lang=EN-US>ab&amp;ba$</span>、<span lang=EN-US>11&amp;12$</span>、<span
lang=EN-US>ab&amp;dd$</span>、<span lang=EN-US>&amp;$,</span>程序将分别输出<span
lang=EN-US>Ok.(</span>是<span lang=EN-US>),No.(</span>不是<span lang=EN-US>)</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:11.4pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
1.0gd;mso-para-margin-bottom:.0001pt;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-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:45.6pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
4.0gd;mso-para-margin-bottom:.0001pt'><span lang=EN-US style='font-family:宋体'>PROGRAM<span
style='mso-spacerun:yes'>&nbsp; </span>accept(input,output);<o:p></o:p></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:45.6pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
4.0gd;mso-para-margin-bottom:.0001pt'><span lang=EN-US style='font-family:宋体'>CONST<span
style='mso-spacerun:yes'>&nbsp; </span>midch=</span><span style='font-family:
宋体'>’<span lang=EN-US>&amp;</span>’<span lang=EN-US>;<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>endch=</span>’<span lang=EN-US>$</span>’<span
lang=EN-US>;<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:45.6pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
4.0gd;mso-para-margin-bottom:.0001pt'><span lang=EN-US style='font-family:宋体'>VAR<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>an:boolean;<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>ch:char;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:45.6pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
4.0gd;mso-para-margin-bottom:.0001pt'><span lang=EN-US style='font-family:宋体'>PROCEDURE<span
style='mso-spacerun:yes'>&nbsp; </span>match(VAR<span
style='mso-spacerun:yes'>&nbsp; </span>answer: boolean);<o:p></o:p></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:45.6pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
4.0gd;mso-para-margin-bottom:.0001pt'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>VAR<span
style='mso-spacerun:yes'>&nbsp; </span>ch1,ch2:char;<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>f:boolean;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:45.6pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
4.0gd;mso-para-margin-bottom:.0001pt'><span lang=EN-US style='font-family:宋体'>BEGIN<o:p></o:p></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:45.6pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
4.0gd;mso-para-margin-bottom:.0001pt'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>read(ch1);<o:p></o:p></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:45.6pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
4.0gd;mso-para-margin-bottom:.0001pt'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>IF<span style='mso-spacerun:yes'>&nbsp;
</span>ch1&lt;&gt;endch<o:p></o:p></span></p>

<p class=MsoNormal style='margin-top:0cm;margin-right:19.3pt;margin-bottom:
0cm;margin-left:45.6pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;
mso-para-margin-right:19.3pt;mso-para-margin-bottom:0cm;mso-para-margin-left:
4.0gd;mso-para-margin-bot