da02.htm

1800道数据结构题和答案

<p class=MsoNormal style='margin-left:9.4pt'><span lang=EN-US style='font-family:
宋体'>6</span><span style='font-family:宋体'>．<span lang=EN-US>O(1)</span>，<span
lang=EN-US>O(n)<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>7</span>．单链表，<span style='color:red'>多重</span>链表，（动态）链表，静态链表<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>8</span><span style='font-family:宋体'>．<span
lang=EN-US>f-&gt;next=p-&gt;next; f-&gt;prior=p; p-&gt;next-&gt;prior=f; p-&gt;next=f;<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>9</span><span style='font-family:宋体'>．<span
lang=EN-US>p^.prior<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;
</span>s^.prior^.next<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>10</span><span style='font-family:宋体'>． 指针<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>11</span>．物理上相邻<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span>指针<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>12</span>．<span lang=EN-US>4<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>2<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>13</span><span style='font-family:宋体'>．从任一结点出发都可访问到链表中每一个元素。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>14</span><span style='font-family:宋体'>．<span
lang=EN-US>u=p-&gt;next; p-&gt;next=u-&gt;next; free(u);<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>15</span>．<span
lang=EN-US>L-&gt;next-&gt;next==L<span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span>16</span>．<span lang=EN-US>p-&gt;next!=null<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:宋体'>17</span><span style='font-family:宋体'>．<span
lang=EN-US>L-&gt;next==L &amp;&amp; L-&gt;prior==L<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>18</span>．<span lang=EN-US>s-&gt;next=p-&gt;next;p-&gt;next=s;<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:宋体'>19</span><span style='font-family:宋体'>．<span
lang=EN-US>(1) <b style='mso-bidi-font-weight:normal'>IF </b>pa=NIL <b
style='mso-bidi-font-weight:normal'>THEN</b> <b style='mso-bidi-font-weight:
normal'>return</b>(true);<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span lang=EN-US style='font-family:宋体'>(2) pb&lt;&gt;NIL <b
style='mso-bidi-font-weight:normal'>AND</b> pa^.data&gt;=pb^.data<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span lang=EN-US style='font-family:宋体'>(3) <b
style='mso-bidi-font-weight:normal'>return</b>(inclusion(pa,pb));<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span lang=EN-US style='font-family:宋体'>(4) pb:=pb^.next;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span lang=EN-US style='font-family:宋体'>(5) <b
style='mso-bidi-font-weight:normal'>return</b>(false);<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span style='font-family:宋体'>非递归算法：<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:28.5pt;mso-char-indent-count:2.5'><span
lang=EN-US style='font-family:宋体'>(1)pre:=pb; (2) pa&lt;&gt;NIL AND
pb&lt;&gt;NIL AND pb^.data&gt;=pa^.data<span style='mso-spacerun:yes'>&nbsp;
</span>(3)pa:=pa^.next; pb:=pb-&gt;next;<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:28.5pt;mso-char-indent-count:2.5'><span
lang=EN-US style='font-family:宋体'>(4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)<b
style='mso-bidi-font-weight:normal'>IF </b>pa=NIL <b style='mso-bidi-font-weight:
normal'>THEN</b> <b style='mso-bidi-font-weight:normal'>return</b>(true) <b
style='mso-bidi-font-weight:normal'>ELSE</b> <b style='mso-bidi-font-weight:
normal'>return</b>(false);<o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>[</span><span
style='font-family:宋体'>注<span lang=EN-US>]</span>：本题是在链表上求模式匹配问题。非递归算法中用指针<span
lang=EN-US>pre</span>指向主串中开始结点（初始时为第一元素结点）。若主串与子串对应数据相等，两串工作指针<span lang=EN-US>pa</span>和<span
lang=EN-US>pb</span>后移；否则，主串工作指针从<span lang=EN-US>pre</span>的下一结点开始（这时<span
lang=EN-US>pre</span>又指向新的开始结点），子串工作指针从子串第一元素开始，比较一直继续到循环条件失败。若<span
lang=EN-US>pa</span>为空，则匹配成功，返回<span lang=EN-US>true</span>，否则，返回<span
lang=EN-US>false</span>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'>20</span><span style='font-family:宋体'>．<span
lang=EN-US>A</span>．<b style='mso-bidi-font-weight:normal'><span lang=EN-US>VAR</span></b><span
lang=EN-US> head:ptr<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>B. new(p)<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>C. p^.data:=k<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>D. q^.next:=p<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>E. q:=p(</span>带头结点<span
lang=EN-US>)<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'>21</span><span style='font-family:宋体'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>new(h);∥</span>生成头结点，以便于操作。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt'><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>r^.next:=p; <span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span>(3) r^.next:=q;<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>(4) <b style='mso-bidi-font-weight:
normal'><span style='color:red'>IF </span></b>(q=NIL) <b style='mso-bidi-font-weight:
normal'><span style='color:red'>THEN</span></b> r^.next:=p;<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'>22</span><span style='font-family:宋体'>．<span
lang=EN-US>A: r^.link^.data&lt;&gt;max <b style='mso-bidi-font-weight:normal'>AND</b>
q^.link^.data&lt;&gt;max<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:34.2pt;mso-char-indent-count:3.0'><span
lang=EN-US style='font-family:宋体'>B: r:=r^.link<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>C: q^.link <span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>D: q^.link <span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>E: r^.link <span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>F: r^.link<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:34.2pt;mso-char-indent-count:3.0'><span
lang=EN-US style='font-family:宋体'>G: r:=s</span><span style='font-family:宋体'>（或<span
lang=EN-US>r:= r^.link</span>）<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>H: r:=r^.link <span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>I: q^.link:=s^.link<o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:27.0pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp; </span>23</span><span
style='font-family:宋体'>．<span lang=EN-US>(1)la<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>(2)0<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>(3)j&lt;i-1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>(4)p</span>↑<span lang=EN-US>.next
<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>(5)i&lt;1<o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:27.0pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp; </span>24.(1)head^.left:=s<span
style='mso-spacerun:yes'>&nbsp; </span>∥head</span><span style='font-family:
宋体'>的前驱指针指向插入结点<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(2)j:=<span style='color:red'>1</span>;<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(3)p:=p^.right<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='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(4)s^.left:=p<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(5)p^.right^.left:=s;<span
style='mso-spacerun:yes'>&nbsp; </span></span><span style='font-family:宋体'>∥<span
lang=EN-US>p</span>后继的前驱是<span lang=EN-US>s<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(6)s^.left:=p;<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>25.(1)i&lt;=L.last<span
style='mso-spacerun:yes'>&nbsp; </span>∥L.last </span><span style='font-family:
宋体'>为元素个数 <span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>(2)j:=j+1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span
style='font-family:宋体'>∥有值不相等的元素<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:40.8pt;mso-char-indent-count:3.58;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(3)L.elem[j]:=L.elem[i]<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='text-indent:40.8pt;mso-char-indent-count:3.58;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(4)L.last:=j<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='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>26.(A)p^.link:=q;∥</span><span
style='font-family:宋体'>拉上链，前驱指向后继<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span>(B)p:=q;</span><span style='font-family:宋体'>∥新的前驱<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span>(C)p^.link:=head;</span><span style='font-family:宋体'>∥形成循环链表<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span>(D)j:=0;<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span><span
style='font-family:宋体'>∥计数器，记被删结点<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span>(E)q:=p^.link</span><span style='font-family:宋体'>∥记下被删结点<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span>(F)p^.link=q^.link<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span><span
style='font-family:宋体'>∥删除结点<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>27. (1)p:=r;∥r</span><span style='font-family:
宋体'>指向工作指针<span lang=EN-US>s</span>的前驱，<span lang=EN-US>p</span>指向最小值的前驱。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>(2)q:=s;</span><span
style='font-family:宋体'>∥<span lang=EN-US>q</span>指向最小值结点，<span lang=EN-US>s</span>是工作指针<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:46.05pt;mso-char-indent-count:4.04;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(3)s:=s^.link</span><span
style='font-family:宋体'>∥工作指针后移<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:46.05pt;mso-char-indent-count:4.04;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(4)head:=head^.next;</span><span
style='font-family:宋体'>∥第一个结点值最小；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:46.05pt;mso-char-indent-count:4.04;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(5)p^link:=q^.link;</span><span
style='font-family:宋体'>∥跨过被删结点（即删除一结点）<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>28</span><span style='font-family:宋体'>．<span
lang=EN-US>(1) l^.key:=x;∥</span>头结点<span lang=EN-US>l</span>这时起监视哨作用<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>(2) l^.freq:=p^.freq<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>∥</span><span style='font-family:
宋体'>头结点起监视哨作用<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:45.85pt;mso-char-indent-count:4.02;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(3) q-&gt;pre-&gt;next=q-&gt;next;
q-&gt;next-&gt;pre=q-&gt;pre;<span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体'>∥先将<span lang=EN-US>q</span>结点从链表上摘下<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:68.15pt;mso-char-indent-count:5.98;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>q^.next:=p;
q^.pre:=p^.pre; p^.pre-&gt;next:=q; p^.pre:=q; ∥</span><span style='font-family:
宋体'>结点<span lang=EN-US>q</span>插入结点<span lang=EN-US>p</span>前<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:46.05pt;mso-char-indent-count:4.04;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(4) q^.freq=0<span
style='mso-spacerun:yes'>&nbsp; </span>∥</span><span style='font-family:宋体'>链表中无值为<span
lang=EN-US>x</span>的结点，将新建结点插入到链表最后（头结点前）。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>29</span><span style='font-family:宋体'>．<span
lang=EN-US>(1)a^.key:=’@’∥a</span>的头结点用作监视哨，取不同于<span lang=EN-US>a</span>链表中其它数据域的值<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&