da05.htm

1800道数据结构题和答案

style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>29. head(tail(tail(head(tail(head(A))))))<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>30. head(tail(head(tail(H))))<span
style='mso-spacerun:yes'>&nbsp; </span>31. (b) <span
style='mso-spacerun:yes'>&nbsp;</span>32. (x,y,z)<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>33. (d,e)<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>34. GetHead(GetHead(GetTail(L)))<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>35. </span><span
style='mso-hansi-font-family:宋体'>本算法中，首先数组<span lang=EN-US>b</span>中元素以逆置顺序放入<span
lang=EN-US>d</span>数组中，然后数组<span lang=EN-US>a</span>和数组<span lang=EN-US>d</span>的元素比较，将大者拷贝到数组<span
lang=EN-US>c</span>。第一个<span lang=EN-US>WHILE</span>循环到数组<span lang=EN-US>a</span>或数组<span
lang=EN-US>d</span>结尾，第二个和第三个<span lang=EN-US>WHILE</span>语句只能执行其中的一个。<span
lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>1</span>）<span
lang=EN-US>b[m-i+1]</span>（<span lang=EN-US>2</span>）<span lang=EN-US>x:=a[i]</span>（<span
lang=EN-US>3</span>）<span lang=EN-US>i:=i+1</span>（<span lang=EN-US>4</span>）<span
lang=EN-US>x:=d[j]</span>（<span lang=EN-US>5</span>）<span lang=EN-US>j:=j+1 </span>（<span
lang=EN-US>6</span>）<span lang=EN-US>k:=k+1</span>（<span lang=EN-US>7</span>）<span
lang=EN-US>i&lt;=l</span>（<span lang=EN-US>8</span>）<span lang=EN-US>j&lt;=m<o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>36.</span><span
style='mso-hansi-font-family:宋体'>（<span lang=EN-US>1</span>）<span lang=EN-US>(i==k)
<b style='mso-bidi-font-weight:normal'>return</b></span>（<span lang=EN-US>2</span>）<span
lang=EN-US>i+1</span>（<span lang=EN-US>3</span>）<span lang=EN-US>i-1</span>（<span
lang=EN-US>4</span>）<span lang=EN-US>i!=k<o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span></span><span style='mso-hansi-font-family:
宋体'>本算法利用快速排序思想，找到第<span lang=EN-US>k</span>个元素的位置（下标<span lang=EN-US>k-1</span>因而开初有<span
lang=EN-US>k--</span>）。内层<span lang=EN-US>do</span>循环以<span lang=EN-US>t(t=a[low])</span>为“枢轴”找到其应在<span
lang=EN-US>i</span>位置。这时若<span lang=EN-US>i</span>等于<span lang=EN-US>k</span>，则算法结束。（即第一个空格处<span
lang=EN-US>if(i==k) <b style='mso-bidi-font-weight:normal'>return</b>)</span>。否则，若<span
lang=EN-US>i&lt;k</span>，就在<span lang=EN-US>i+1</span>至<span lang=EN-US>high</span>中间去查；若<span
lang=EN-US>i&gt;k</span>，则在<span lang=EN-US>low</span>到<span lang=EN-US>i-1</span>间去找，直到找到<span
lang=EN-US>i=k</span>为止。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>37.</span><span
style='mso-hansi-font-family:宋体'>逆置广义表的递归模型如下<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText style='tab-stops:right 510.2pt'><span lang=EN-US
style='mso-hansi-font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span>f(LS)=<sub><!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600"
 o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f"
 stroked="f">
 <v:stroke joinstyle="miter"/>
 <v:formulas>
  <v:f eqn="if lineDrawn pixelLineWidth 0"/>
  <v:f eqn="sum @0 1 0"/>
  <v:f eqn="sum 0 0 @1"/>
  <v:f eqn="prod @2 1 2"/>
  <v:f eqn="prod @3 21600 pixelWidth"/>
  <v:f eqn="prod @3 21600 pixelHeight"/>
  <v:f eqn="sum @0 0 1"/>
  <v:f eqn="prod @6 1 2"/>
  <v:f eqn="prod @7 21600 pixelWidth"/>
  <v:f eqn="sum @8 21600 0"/>
  <v:f eqn="prod @7 21600 pixelHeight"/>
  <v:f eqn="sum @10 21600 0"/>
 </v:formulas>
 <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
 <o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:381pt;
 height:75.75pt' o:ole="">
 <v:imagedata src="da05.files/image001.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=508 height=101
src="da05.files/image002.gif" v:shapes="_x0000_i1025"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1025"
  DrawAspect="Content" ObjectID="_1149856324">
 </o:OLEObject>
</xml><![endif]--> <span style='mso-tab-count:1'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><o:p></o:p></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>上面<span
lang=EN-US>app<b style='mso-bidi-font-weight:normal'>END</b>(a,b)</span>功能是将广义表<span
lang=EN-US>a</span>和<span lang=EN-US>b</span>作为元素的广义表连接起来。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>1</span>）<span
lang=EN-US>(p-&gt;tag==0)<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><span style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>//</span>处理原子<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>2</span>）<span
lang=EN-US>h=reverse(p-&gt;val.<span style='color:red'>ptr</span>.hp)<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>//</span>处理表头<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>3</span>）<span
lang=EN-US>(p-&gt;val.<span style='color:red'>ptr</span>.tp)<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>//</span>产生表尾的逆置广义表<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>4</span>）<span
lang=EN-US>s-&gt;val.<span style='color:red'>ptr</span>.tp=t;<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>//</span>连接<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>5</span>）<span
lang=EN-US>q-&gt;val.<span style='color:red'>ptr</span>.hp=h<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>//</span>头结点指向广义表<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>38. </span><span
style='mso-hansi-font-family:宋体'>本题要求将<span lang=EN-US>1</span>，<span
lang=EN-US>2</span>，<span lang=EN-US>...,n*n</span>个自然数，按蛇型方式存放在二位数组<span
lang=EN-US>A[n][n]</span>中。“蛇型”方式，即是按“副对角线”平行的各对角线，从左下到右上，再从右上到左下，存放<span
lang=EN-US>n<sup>2</sup></span>个整数。对角线共<span lang=EN-US>2n-1</span>条，在副对角线上方的对角线，题目中用<span
lang=EN-US>k</span>表示第<span lang=EN-US>k</span>条对角线（最左上角<span lang=EN-US>k=1</span>），数组元素<span
lang=EN-US>x</span>和<span lang=EN-US>y</span>方向坐标之和为<span lang=EN-US>k+1</span>（即题目中的<span
lang=EN-US>i+j=k+1</span>）。副对角线下方第<span lang=EN-US>k</span>条对角线与第<span
lang=EN-US>2n-k</span>条对角线对称，其元素的下标等于其对称元素的相应坐标各加<span lang=EN-US>(k-n)</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>1</span>）<span
lang=EN-US>k&lt;=2*n-1 //</span>共填<span lang=EN-US>2*n-1</span>条对角线<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>2</span>）<span
lang=EN-US>q=2*n-k<span style='mso-spacerun:yes'>&nbsp; </span>//</span>副对角线以下的各条对角线上的元素数<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>3</span>）<span
lang=EN-US>k%2</span>！<span lang=EN-US>=0<span style='mso-spacerun:yes'>&nbsp;
</span>//k</span>为偶数时从右上到左下，否则从左下向右上填数。（本处计算下标<span lang=EN-US>i</span>和<span
lang=EN-US>j</span>）<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>4</span>）<span
lang=EN-US>k&gt;=n<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;
</span>//</span>修改副对角线下方的下标<span lang=EN-US>i</span>和<span lang=EN-US>j</span>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>5</span>）<span
lang=EN-US>m++</span>；或<span lang=EN-US>m=m+1 //</span>为填下个数作准备，<span
lang=EN-US>m</span>变化范围<span lang=EN-US>1..n*n</span>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>本题解法的另一种思路见本章算法设计题第<span
lang=EN-US>9</span>题。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>39.</span><span
style='mso-hansi-font-family:宋体'>本题难点有二：一是如何求下一出圈人的位置，二是某人出圈后对该人的位置如何处理。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText style='text-indent:22.2pt;mso-char-indent-count:2.0'><span
style='mso-hansi-font-family:宋体'>按题中要求，从第<span lang=EN-US>s</span>个人开始报数，报到第<span
lang=EN-US>m</span>个人，此人出圈。<span lang=EN-US>n</span>个人围成一圈，可看作环状，则下个出圈人，其位置是<span
lang=EN-US>(s+m-1)%n</span>。<span lang=EN-US>n</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=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>1</span>）<span
lang=EN-US>(s+m-1) MOD i <span style='mso-spacerun:yes'>&nbsp;</span>//</span>计算出圈人<span
lang=EN-US>s1<o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>2</span>）<span
lang=EN-US>s1:=i<span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span>//</span>若<span
lang=EN-US>s1=0,</span>说明是第<span lang=EN-US>i</span>个人出圈（<span lang=EN-US>i%i=0</span>）<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>3</span>）<span
lang=EN-US>s1 TO i-1 <span style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>//</span>从<span lang=EN-US>s1</span>到<span
lang=EN-US>i</span>依次前移，使人数减<span lang=EN-US>1</span>，并将出圈人放到当前最后一个位置<span
lang=EN-US>A[i]=w</span>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>40. </span><span
style='mso-hansi-font-family:宋体'>若第<span lang=EN-US>n</span>件物品能放入背包，则问题变为能否再从<span
lang=EN-US>n-1</span>件物品中选出若干件放入背包（这时背包可放入物品的重量变为<span lang=EN-US>s-w[n]</span>）。若第<span
lang=EN-US>n</span>件物品不能放入背包，则考虑从<span lang=EN-US>n-1</span>件物品选若干件放入背包（这时背包可放入物品仍为<span
lang=EN-US>s</span>）。若最终<span lang=EN-US>s=0,</span>则有一解；否则，若<span lang=EN-US>s&lt;0</span>或虽然<span
lang=EN-US>s&gt;0</span>但物品数<span lang=EN-US>n&lt;1,</span>则无解。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>1</span>）<span
lang=EN-US>s-w[n],n-1<span style='mso-spacerun:yes'>&nbsp; </span>//Knap(s-w[n],n-1)=true<o:p></o:p></span></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>（<span lang=EN-US>2</span>）<span
lang=EN-US>s,n-1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>// Knap</span>←<span
lang=EN-US>Knap(s,n-1)<o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoPlainText><span style='mso-hansi-font-family:宋体'>四、应用题<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>1</span><span
style='mso-hansi-font-family:宋体'>、<span lang=EN-US>958<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span>三维数组以行为主序存储，其元素地址公式为：<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText style='text-indent:49.6pt;mso-char-indent-count:4.47'><span
lang=EN-US style='mso-hansi-font-family:宋体'>LOC(A<sub>ijk</sub>)=LOC(A<sub>c1c2c3</sub>)+[(i-c<sub>1</sub>)V<sub>2</sub>V<sub>3</sub>+(j-c<sub>2</sub>)V<sub>3</sub>+(k-c<sub>3</sub>)]*L+1<o:p></o:p></span></p>

<p class=MsoPlainText style='text-indent:22.2pt;mso-char-indent-count:2.0'><span
style='mso-hansi-font-family:宋体'>其中<span lang=EN-US>c<sub>i</sub>,d<sub>i</sub></span>是各维的下界和上界，<span
lang=EN-US>V<sub>i</sub>=d<sub>i</sub>-c<sub>i</sub>+1</span>是各维元素个数，<span
lang=EN-US>L</span>是一个元素所占的存储单元数。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>2. b</span><span
style='mso-hansi-font-family:宋体'>对角矩阵的<span lang=EN-US>b</span>条对角线，在主对角线上方和下方各有</span><span
lang=EN-US style='font-family:Symbol;mso-ascii-font-family:宋体;mso-hansi-font-family:
宋体;mso-char-type:symbol;mso-symbol-font-family:Symbol'><span style='mso-char-type:
symbol;mso-symbol-font-family:Symbol'>&euml;</span></span><span lang=EN-US
style='mso-hansi-font-family:宋体'>b/2</span><span lang=EN-US style='font-family:
Symbol;mso-ascii-font-family:宋体;mso-hansi-font-family:宋体;mso-char-type:symbol;
mso-symbol-font-family:Symbol'><span style='mso-char-type:symbol;mso-symbol-font-family:
Symbol'>&ucirc;</span></span><span style='mso-hansi-font-family:宋体'>条对角线<span
lang=EN-US>(</span>为叙述方便，下面设<span lang=EN-US>a=</span></span><span lang=EN-US
style='font-family:Symbol;mso-ascii-font-family:宋体;mso-hansi-font-family:宋体;
mso-char-type:symbol;mso-symbol-font-family:Symbol'><span style='mso-char-type:
symbol;mso-symbol-font-family:Symbol'>&euml;</span></span><span lang=EN-US
style='mso-hansi-font-family:宋体'>b/2</span><span lang=EN-US style='font-family:
Symbol;mso-ascii-font-family:宋体;mso-hansi-font-family:宋体;mso-char-type:symbol;
mso-symbol-font-family:Symbol'><span style='mso-char-type:symbol;mso-symbol-font-family:
Symbol'>&ucirc;</span></span><span lang=EN-US style='mso-hansi-font-family:宋体'>)</span><span
style='mso-hansi-font-family:宋体'>。从第<span lang=EN-US>1</span>行至第<span
lang=EN-US>a</span>行，每行上的元素数依次是<span lang=EN-US>a+1,a+2,...,b-2,b-1,</span>最后的<span
lang=EN-US>a</span>行上的元素个数是<span lang=EN-US> b-1</span>，<span lang=EN-US>b-2,...,a+1</span>。中间的<span
lang=EN-US>(n-2a )</span>行，每行元素个数都是<span lang=EN-US>b</span>。