da04.htm

1800道数据结构题和答案

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:宋体'>9</span><span style='font-family:
宋体'>．<span lang=EN-US>(1)</span>其数据元素都是字符<span lang=EN-US>(2)</span>顺序存储<span
lang=EN-US>(3)</span>和链式存储<span lang=EN-US>(4)</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:宋体'>10</span><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:宋体'>11</span><span style='font-family:
宋体'>．<span lang=EN-US>’xyxyxywwy’<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>12</span>．<span lang=EN-US>*s++=*t++
</span>或（<span lang=EN-US>*s++=*t++</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='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='font-family:宋体'>13</span><span style='font-family:
宋体'>．（<span lang=EN-US>1</span>）<b style='mso-bidi-font-weight:normal'><span
lang=EN-US>char</span></b><span lang=EN-US> s[ ]<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>(2) j++ <span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>(3) i &gt;= j<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>14</span><span
style='font-family:宋体'>．<span lang=EN-US>[</span>题目分析<span lang=EN-US>]</span>本题算法采用顺序存储结构求串<span
lang=EN-US>s</span>和串<span lang=EN-US>t</span>的最大公共子串。串<span lang=EN-US>s</span>用<span
lang=EN-US>i</span>指针（<span lang=EN-US>1&lt;=i&lt;=s.len</span>）。<span
lang=EN-US>t</span>串用<span lang=EN-US>j</span>指针（<span lang=EN-US>1&lt;=j&lt;=t.len</span>）。算法思想是对每个<span
lang=EN-US>i</span>（<span lang=EN-US>1&lt;=i&lt;=s.len</span>，即程序中第一个<b
style='mso-bidi-font-weight:normal'><span lang=EN-US>WHILE</span></b>循环），来求从<span
lang=EN-US>i</span>开始的连续字符串与从<span lang=EN-US>j</span>（<span lang=EN-US>1&lt;=j&lt;=t.len</span>，即程序中第二个Ｗ<span
lang=EN-US>HILE</span>循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的<b style='mso-bidi-font-weight:
normal'><span lang=EN-US>WHILE</span></b>循环，是当<span lang=EN-US>s</span>中某字符（<span
lang=EN-US>s</span>［<span lang=EN-US>i</span>］）与<span lang=EN-US>t</span>中某字符（<span
lang=EN-US>t</span>［<span lang=EN-US>j</span>］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:11.15pt;mso-char-indent-count:.98'><span style='font-family:宋体'>程序（<span
lang=EN-US>a</span>）：（<span lang=EN-US>1</span>）（<span lang=EN-US>i+k&lt;=s.len</span>）<span
lang=EN-US>AND(j+k&lt;=t.len) AND(s[i+k]=t[j+k])<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>//</span><span style='font-family:宋体'>如果在<span
lang=EN-US>s</span>和<span lang=EN-US>t</span>的长度内，对应字符相等，则指针<span lang=EN-US>k </span>后移（加<span
lang=EN-US>1</span>）。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span></span><span
style='font-family:宋体'>（<span lang=EN-US>2</span>）<span lang=EN-US>con:=false <span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>//s</span>和<span lang=EN-US>t</span>对应字符不等时置标记退出<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span><span style='font-family:宋体'>（<span lang=EN-US>3</span>）<span
lang=EN-US>j:=j+k <span style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span>//</span>在<span
lang=EN-US>t</span>串中，从第<span lang=EN-US>j+k</span>字符再与<span lang=EN-US>s[i]</span>比较<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span><span style='font-family:宋体'>（<span lang=EN-US>4</span>）<span
lang=EN-US>j:=j+1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>//t</span>串取下一字符<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:61.35pt;mso-char-indent-count:5.38'><span style='font-family:宋体'>（<span
lang=EN-US>5</span>）<span lang=EN-US>i</span>：<span lang=EN-US>=i+1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>//s</span>串指针<span
lang=EN-US>i</span>后移（加<span lang=EN-US>1</span>）。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
style='font-family:宋体'>　程序（<span lang=EN-US>b</span>）：<span lang=EN-US>(1)
i+k&lt;=s.len &amp;&amp; j+k&lt;=t.len &amp;&amp; s[i+k]==t[j+k]<span
style='mso-spacerun:yes'>&nbsp; </span>//</span>所有注释同上（<span lang=EN-US>a</span>）<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>(2) con=0<span style='mso-spacerun:yes'>&nbsp; </span>(3) j+=k<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>(4) j++<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>(5) i++<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'>15</span><span style='font-family:宋体'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>0<span style='mso-spacerun:yes'>&nbsp;
</span></span>（<span lang=EN-US>2</span>）<span lang=EN-US>next[k]<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'>16</span><span style='font-family:宋体'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>i</span>：<span lang=EN-US>=i+1<span
style='mso-spacerun:yes'>&nbsp; </span></span>（<span lang=EN-US>2</span>）<span
lang=EN-US>j:=j+1<span style='mso-spacerun:yes'>&nbsp; </span>(3)i:=i-j+2<span
style='mso-spacerun:yes'>&nbsp; </span>(4)j:=1;<span
style='mso-spacerun:yes'>&nbsp; </span>(5)i-mt</span>（或<span lang=EN-US>i:=i-j+1</span>）<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span>(6)0<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'>17.</span><span style='font-family:宋体'>程序中递归调用<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>（<span lang=EN-US>1</span>）<span lang=EN-US>ch1&lt;&gt;midch<span
style='mso-spacerun:yes'>&nbsp; </span>//</span>当读入不是分隔符<span lang=EN-US>&amp;</span>和输入结束符<span
lang=EN-US>$</span>时，继续读入字符<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><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>ch1=ch2<span
style='mso-spacerun:yes'>&nbsp; </span>//</span>读入分隔符<span lang=EN-US>&amp;</span>后，判<span
lang=EN-US style='color:red'>ch1</span>是否等于<span lang=EN-US>ch2</span>，得出真假结论。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>（<span lang=EN-US>3</span>）<span lang=EN-US>answer</span>：<span
lang=EN-US>=true<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>（<span lang=EN-US>4</span>）<span lang=EN-US>answer</span>：<span
lang=EN-US>=false<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>（<span lang=EN-US>5</span>）<span lang=EN-US>read</span>（<span
lang=EN-US>ch</span>）<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>（<span lang=EN-US>6</span>）<span lang=EN-US>ch=endch<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'>18</span><span style='font-family:宋体'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>initstack</span>（<span lang=EN-US>s</span>）<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span>/</span>／栈<span
lang=EN-US>s</span>初始化为空栈。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span style='font-family:宋体'>　<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span>(2) setnull (exp) <span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>//</span>串<span lang=EN-US>exp</span>初始化为空串。<span
lang=EN-US> <o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:2.5gd;
text-indent:-5.7pt;mso-char-indent-count:-.5'><span lang=EN-US
style='font-family:宋体'>(3) ch in opset<span style='mso-spacerun:yes'>&nbsp;
</span><span style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>//</span><span style='font-family:宋体'>判取出字符是否是操作符。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;
</span>(4) push (s,ch)<span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>//</span><span
style='font-family:宋体'>如<span lang=EN-US>ch</span>是运算符，则入运算符栈<span lang=EN-US>s</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;
</span>(5) sempty (s)<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>//</span><span
style='font-family:宋体'>判栈<span lang=EN-US>s</span>是否为空。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;
</span>(6) succ := false <span style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>//</span><span
style='font-family:宋体'>若读出<span lang=EN-US>ch</span>是操作数且栈为空，则按出错处理。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;
</span>(7) exp<span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>(8)ch<span
style='mso-spacerun:yes'>&nbsp; </span>//</span><span style='font-family:宋体'>若<span
lang=EN-US>ch</span>是操作数且栈非空，则形成部分中缀表达式。<span lang=EN-US><o:p></o:p></span></span></p>