da05.htm

1800道数据结构题和答案

  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'>14.</span><span style='mso-bidi-font-size:10.5pt;font-family:
  宋体;color:red'>√</span><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p></o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td valign=top style='border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;
  border-right:solid windowtext 1.0pt;mso-border-top-alt:solid windowtext .5pt;
  mso-border-left-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'>
  <p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  font-family:宋体'><o:p>&nbsp;</o:p></span></p>
  </td>
 </tr>
</table>

<p class=MsoNormal style='text-indent:16.2pt;mso-char-indent-count:1.46'><span
style='mso-bidi-font-size:10.5pt;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><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>4. </span><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:宋体'>5. </span><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:宋体'>6. </span><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:宋体'>8. </span><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:宋体'>9. </span><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:宋体'>10. </span><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:宋体'>11. </span><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:宋体'><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><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>2.</span>（<span
lang=EN-US>1</span>）<span lang=EN-US>9572</span>（<span lang=EN-US>2</span>）<span
lang=EN-US>1228<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>3.</span>（<span lang=EN-US>1</span>）<span
lang=EN-US>9174</span>（<span lang=EN-US>2</span>）<span lang=EN-US>8788<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>4. 1100<o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>5. 1164
</span><span style='mso-hansi-font-family:宋体'>公式：<span lang=EN-US>LOC(a<sub>ijk</sub>)=LOC(a<sub>000</sub>)+[v2*v3*(i-c<sub>1</sub>)+v3*(j-c<sub>2</sub>)+(k-c<sub>3</sub>)]*l
(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:宋体'>6. 232<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>7. 1340<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>8. 1196<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>9. </span><span style='mso-hansi-font-family:
宋体'>第<span lang=EN-US>1</span>行第<span lang=EN-US>3</span>列<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>10.
(1)270 (2)27 (3)2204<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>11. i(i-1)/2+j (1&lt;=i,j&lt;=n)<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>12. (1)n(n+1)/2
(2)i(i+1)/2 (</span><span style='mso-hansi-font-family:宋体'>或<span lang=EN-US>j(j+1)/2)
(3)i(i-1)/2+j (4)j(j-1)/2+i (1&lt;=i,j&lt;=n)<o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>13. 1038
</span><span style='mso-hansi-font-family:宋体'>三对角矩阵按行存储：<span lang=EN-US>k=2(i-1)+j
(1&lt;=i,j&lt;=n) <o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>14. 33 (k=i(i-1)/2+j)
(1&lt;=i,j&lt;=n)<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;
</span><o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>15. </span><span
style='mso-hansi-font-family:宋体'>非零元很少<span lang=EN-US>(t&lt;&lt;m*n)</span>且分布没有规律<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>16. </span>节省存储空间。<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>17. </span><span
style='mso-hansi-font-family:宋体'>上三角矩阵中，主对角线上第<span lang=EN-US>r(1</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'>&pound;</span></span><span lang=EN-US
style='mso-hansi-font-family:宋体'>r</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'>&pound;</span></span><span lang=EN-US style='mso-hansi-font-family:宋体'>n) </span><span
style='mso-hansi-font-family:宋体'>行有<span lang=EN-US>n-r+1</span>个元素，<span
lang=EN-US>a<sub>ij</sub></span>所在行的元素数是<span lang=EN-US>j-i+1</span>。所以，元素在一维数组的下标<span
lang=EN-US>k</span>和二维数组下标关系<span lang=EN-US>:k=((i-1)*(2n-i+2))/2+(j-i+1)=(i-1)(2n-i)/2+j<span
style='mso-spacerun:yes'>&nbsp; </span>(i</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'>&pound;</span></span><span lang=EN-US
style='mso-hansi-font-family:宋体'>j)<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>18.
93<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>19. i(i-1)/2+j <span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>20.
</span><span style='mso-hansi-font-family:宋体'>线性表<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>21.
</span>其余元素组成的表<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>22. </span><span
style='mso-hansi-font-family:宋体'>（<span lang=EN-US>1</span>） 原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。<span
lang=EN-US> <o:p></o:p></span></span></p>

<p class=MsoPlainText style='text-indent:10.85pt;mso-char-indent-count:.98'><span
style='mso-hansi-font-family:宋体'>（<span lang=EN-US>2</span>）大写字母 （<span
lang=EN-US>3</span>）小写字母 （<span lang=EN-US>4</span>）表中元素的个数（<span lang=EN-US>5</span>）表展开后所含括号的层数<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>23. </span><span
style='mso-hansi-font-family:宋体'>深度 <span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>24.</span>（<span lang=EN-US>1</span>）（） （<span
lang=EN-US>2</span>）（（））<span lang=EN-US><span style='mso-spacerun:yes'>&nbsp;
</span></span>（<span lang=EN-US>3</span>）<span lang=EN-US>2<span
style='mso-spacerun:yes'>&nbsp; </span></span>（<span lang=EN-US>4</span>）<span
lang=EN-US>2<o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:54.0pt'><span lang=EN-US style='font-family:
宋体'>25. head</span><span style='font-family:宋体'>（<span lang=EN-US>head</span>（<span
lang=EN-US>tail</span>（<span lang=EN-US>tail</span>（<span lang=EN-US>head</span>（<span
lang=EN-US>tail</span>（<span lang=EN-US>tail</span>（<span lang=EN-US>A</span>）））））））<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>26. </span><span
style='mso-hansi-font-family:宋体'>表展开后所含括号的层数<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>27.</span>（<span lang=EN-US>1</span>）<span
lang=EN-US>5<span style='mso-spacerun:yes'>&nbsp; </span></span>（<span
lang=EN-US>2</span>）<span lang=EN-US>3<o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='mso-hansi-font-family:宋体'>28. head(head(tail(LS)))<span