da03.htm

1800道数据结构题和答案

  style='mso-bidi-font-size:10.5pt;mso-fareast-font-family:黑体'><o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>2.√<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>3. √<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>4. √<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.4pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>5.×<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>6.√<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>7.√<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>8. √<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.4pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>9. √<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>10.×<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>11. √<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;border:solid windowtext 1.0pt;
  border-left:none;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;
  mso-fareast-font-family:黑体'>12.×<o:p></o:p></span></p>
  </td>
 </tr>
 <tr style='mso-yfti-irow:1;mso-yfti-lastrow:yes'>
  <td width=47 valign=top style='width:35.4pt;border:solid windowtext 1.0pt;
  border-top:none;mso-border-top-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;
  mso-fareast-font-family:黑体'>13. ×<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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:黑体'>14</span><span lang=EN-US style='mso-bidi-font-size:10.5pt;
  mso-fareast-font-family:黑体'>.×<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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;
  mso-fareast-font-family:黑体'>15. √<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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;
  mso-fareast-font-family:黑体'>16.×<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.4pt;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;
  mso-fareast-font-family:黑体'>17.√<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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;
  mso-fareast-font-family:黑体'>18.×<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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;
  mso-fareast-font-family:黑体'>19.√<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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;
  mso-fareast-font-family:黑体'>20. √<o:p></o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.4pt;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;
  mso-fareast-font-family:黑体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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;
  mso-fareast-font-family:黑体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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;
  mso-fareast-font-family:黑体'><o:p>&nbsp;</o:p></span></p>
  </td>
  <td width=47 valign=top style='width:35.45pt;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;
  mso-fareast-font-family:黑体'><o:p>&nbsp;</o:p></span></p>
  </td>
 </tr>
</table>

<p class=MsoNormal><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>部分答案解释如下。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:18.0pt;text-indent:-18.0pt;mso-list:l2 level1 lfo9;
tab-stops:list 18.0pt'><![if !supportLists]><span lang=EN-US style='mso-fareast-font-family:
"Times New Roman"'><span style='mso-list:Ignore'>1、<span style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>尾递归的消除就不需用栈</span></p>

<p class=MsoNormal style='margin-left:18.0pt;text-indent:-18.0pt;mso-list:l2 level1 lfo9;
tab-stops:list 18.0pt'><![if !supportLists]><span lang=EN-US style='font-family:
宋体;mso-bidi-font-family:宋体'><span style='mso-list:Ignore'>2、<span
style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>这个数是前序序列为</span><span lang=EN-US>1,2,3,…,n</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，所能得到的不相似的二叉树的数目。</span><span lang=EN-US style='font-family:
宋体'><o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><!--[if supportFields]><span lang=EN-US style='font-family:
黑体'><span style='mso-element:field-begin'></span><span
style='mso-spacerun:yes'>&nbsp;</span>= 3 \* CHINESENUM3 <span
style='mso-element:field-separator'></span></span><![endif]--><span
style='font-family:黑体;mso-no-proof:yes'>三</span><!--[if supportFields]><span
lang=EN-US style='font-family:黑体'><span style='mso-element:field-end'></span></span><![endif]--><span
style='font-family:黑体'>、填空题<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US><span style='mso-spacerun:yes'>&nbsp;
</span>1</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>、操作受限（或限定仅在表尾进行插入和删除操作）</span><span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>后进先出</span><span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span></span></p>

<p class=MsoNormal><span lang=EN-US><span style='mso-spacerun:yes'>&nbsp;
</span>2</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>、栈</span><span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>3</span><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US>3 1 2<span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>4</span><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US>23<span style='mso-spacerun:yes'>&nbsp; </span>100CH <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;</span>5</span><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US>0<span style='mso-spacerun:yes'>&nbsp; </span>n+1<span
style='mso-spacerun:yes'>&nbsp; </span></span><span lang=EN-US
style='font-family:宋体'>top[1]+1=top[2]<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:19.5pt;text-indent:-19.5pt;mso-char-indent-count:
-1.71'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>6</span><span style='font-family:宋体'>、两栈顶指针值相减的绝对值为<span
lang=EN-US>1</span>（或两栈顶指针相邻）。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:19.5pt;mso-para-margin-left:1.0gd;
text-indent:-8.1pt;mso-char-indent-count:-.71'><span lang=EN-US
style='font-family:宋体'>7</span><span style='font-family:宋体'>、<span lang=EN-US>(1)</span>满<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span>(2)</span>空<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span>(3)n<span
style='mso-spacerun:yes'>&nbsp; </span>(4)</span>栈底<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span>(5)</span>两栈顶指针相邻（即值之差的绝对值为<span
lang=EN-US>1</span>）<span lang=EN-US><o:p></o:p></span></span></p>