st04.htm

1800道数据结构题和答案

<p class=MsoNormal align=left style='text-align:left;mso-layout-grid-align:
none;text-autospace:none'><span lang=EN-US style='font-family:宋体'>13</span><span
style='font-family:宋体'>．</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>下列程序判断字符串<span lang=EN-US>s </span>是否对称，对称则返回<span
lang=EN-US>1</span>，否则返回<span lang=EN-US>0</span>；如<span lang=EN-US>
f(&quot;abba&quot;)</span>返回<span lang=EN-US>1</span>，<span lang=EN-US>f(&quot;abab&quot;)</span>返回<span
lang=EN-US>0</span>；<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:19.5pt;
mso-char-indent-count:1.71;mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'><span style='mso-spacerun:yes'>&nbsp;</span>int f(<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:宋体;color:black;
mso-font-kerning:0pt'>)<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:19.5pt;
mso-char-indent-count:1.71;mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;
</span>{int<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>i=0,j=0;<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:19.5pt;
mso-char-indent-count:1.71;mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>while (s[j])<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='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'>;<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:19.5pt;
mso-char-indent-count:1.71;mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for(j--;
i&lt;j<span style='mso-spacerun:yes'>&nbsp; </span>&amp;&amp; s[i]==s[j];
i++,j--);<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:11.4pt;
mso-char-indent-count:1.0;mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>return(<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:宋体;color:black;
mso-font-kerning:0pt'>)<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:19.5pt;
mso-char-indent-count:1.71;mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;
</span>}<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span><span
style='font-family:宋体'>【</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>浙江大学</span><span
style='font-family:宋体'> </span><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>1999</span><span lang=EN-US
style='font-family:宋体'> </span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>一、<span lang=EN-US>6 (3</span>分<span
lang=EN-US>)</span>】</span><span lang=EN-US style='font-family:宋体'><o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>14</span><span
style='font-family:宋体'>．下列算法实现求采用顺序结构存储的串<span lang=EN-US>s</span>和串<span
lang=EN-US>t</span>的一个最长公共子串。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
style='font-family:宋体'>程序（<span lang=EN-US>a</span>）<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd'><span
lang=EN-US style='font-family:宋体'>PROCEDURE<span
style='mso-spacerun:yes'>&nbsp; </span>maxcomstr(VAR s,t : orderstring; VAR
index,length : integer);<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:宋体'>VAR i,j,k,length1:integer;<span
style='mso-spacerun:yes'>&nbsp; </span>con:boolean;<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:宋体'>BEGIN <o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:5.7pt;mso-char-indent-count:.5'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;</span>index :=0; length :=0;<span
style='mso-spacerun:yes'>&nbsp; </span>i :=1;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:11.4pt;mso-char-indent-count:1.0'><span lang=EN-US
style='font-family:宋体'>WHILE(i&lt;=s.len) DO <o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:22.8pt;mso-char-indent-count:2.0'><span lang=EN-US
style='font-family:宋体'>[j:=1;<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; </span>WHILE (j&lt;=t.len) DO
<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:45.25pt;mso-char-indent-count:3.97'><span lang=EN-US
style='font-family:宋体'>[ IF (s[i]=t[j])<span style='mso-spacerun:yes'>&nbsp;
</span>THEN<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:62.0pt;mso-char-indent-count:5.44'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;</span>[ k:=1;<span
style='mso-spacerun:yes'>&nbsp; </span>length1:=1;<span
style='mso-spacerun:yes'>&nbsp; </span>con:=true;<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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>WHILE<span style='mso-spacerun:yes'>&nbsp; </span>con<span
style='mso-spacerun:yes'>&nbsp; </span>DO<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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>IF <u>(1)__</u>THEN [length1:=length1+1;k:=k+1;] ELSE<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='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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>IF (length1&gt;length) THEN [index:=i; length:=length1; ]<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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><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='font-family:宋体'>; <o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:72.6pt;mso-char-indent-count:6.37;tab-stops:81.55pt'><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;&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='mso-bidi-font-size:
10.5pt;font-family:宋体'>;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:39.1pt;mso-char-indent-count:3.43'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span></span><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;
text-indent:33.85pt;mso-char-indent-count:2.97'><u><span lang=EN-US
style='font-family:宋体'>(5)</span></u><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:宋体'>;<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:33.5pt;mso-char-indent-count:2.94'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span></span><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:宋体'>END;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd'><span
style='font-family:宋体'>程序<span lang=EN-US>(b)<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd'><span
lang=EN-US style='font-family:宋体'>void<span style='mso-spacerun:yes'>&nbsp;
</span>maxcomstr(orderstring *s,*t; int index, length)<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:5.7pt;mso-char-indent-count:.5'><span lang=EN-US style='font-family:
宋体'>{int i,j,k,length1,con;<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;
</span>index=0;length=0;i=1;<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;
</span>while (i&lt;=s.len)<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:11.4pt;mso-char-indent-count:1.0'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;</span>{j=1;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:22.8pt;mso-char-indent-count:2.0'><span lang=EN-US
style='font-family:宋体'>while(j&lt;=t.len)<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:28.5pt;mso-char-indent-count:2.5'><span lang=EN-US
style='font-family:宋体'>{ if (s[i]= =t[j]) <o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:45.25pt;mso-char-indent-count:3.97'><span lang=EN-US
style='font-family:宋体'>{ k=1;length1=1;con=1;<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;&nbsp;&nbsp;&nbsp;
</span>while(con)<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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>if<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='font-family:宋体'> {
length1=length1+1;k=k+1; }<span style='mso-spacerun:yes'>&nbsp; </span>else<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='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;&nbsp;&nbsp;&nbsp;
</span>if (length1&gt;length) { index=i;<span style='mso-spacerun:yes'>&nbsp;
</span>length=length1; }<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;&nbsp;&nbsp;&nbsp;
</span><u>(3)</u></span><u><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>____</span></u><u><span lang=EN-US style='font-family:宋体'>;</span></u><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span><o:p></o:p></span></p>