📄 cs4da.htm
字号:
</span></p>
</td>
<td width="32" valign="top" style="width:24.0pt;border:none;border-right:solid windowtext .5pt;
mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="24" valign="top" style="width:18.0pt;border-top:none;border-left:none;
border-bottom:solid windowtext .5pt;border-right:solid windowtext .5pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt">2<o:p>
</o:p>
</span></p>
</td>
<td width="32" valign="top" style="width:24.0pt;border:none;border-right:solid windowtext .5pt;
mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="24" valign="top" style="width:18.0pt;border-top:none;border-left:none;
border-bottom:solid windowtext .5pt;border-right:solid windowtext .5pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt">2<o:p>
</o:p>
</span></p>
</td>
<td width="32" valign="top" style="width:24.0pt;border:none;border-right:solid windowtext .5pt;
mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="24" valign="top" style="width:18.0pt;border-top:none;border-left:none;
border-bottom:solid windowtext .5pt;border-right:solid windowtext .5pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="32" valign="top" style="width:24.0pt;border:none;border-right:solid windowtext .5pt;
mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="24" valign="top" style="width:18.0pt;border-top:none;border-left:none;
border-bottom:solid windowtext .5pt;border-right:solid windowtext .5pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt">6<o:p>
</o:p>
</span></p>
</td>
<td width="32" valign="top" style="width:24.0pt;border:none;border-right:solid windowtext .5pt;
mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="24" valign="top" style="width:18.0pt;border-top:none;border-left:none;
border-bottom:solid windowtext .5pt;border-right:solid windowtext .5pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.5pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt"><o:p>
</o:p>
</span></p>
</td>
</tr>
</table>
<p class="MsoNormal" style="line-height:15.5pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt"><span style="mso-spacerun:
yes">
</span><span style="mso-spacerun: yes"> </span>1<span style="mso-spacerun: yes">
</span>1<span style="mso-spacerun: yes">
</span><span style="mso-spacerun:
yes"> </span>13<span style="mso-spacerun: yes"> </span><span style="mso-spacerun:
yes"> </span>135<span style="mso-spacerun: yes">
</span>1354 <span style="mso-spacerun: yes"> </span><span style="mso-spacerun:
yes"> </span>13542<span style="mso-spacerun: yes"> </span><span style="mso-spacerun:
yes"> </span>13542<span style="mso-spacerun: yes"> </span>135426<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height:15.5pt"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height:15.5pt"><span lang="EN-US" style="mso-font-kerning:8.0pt">4-3</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">、试证明：若借助栈可由输入序列</span><span lang="EN-US" style="mso-font-kerning:8.0pt">1,
2, 3, </span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">…</span><span lang="EN-US" style="mso-font-kerning:8.0pt">,
<i style="mso-bidi-font-style:normal">n</i></span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">得到一个输出序列</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p</span></i><sub><span lang="EN-US" style="mso-font-kerning:8.0pt">1</span></sub><span lang="EN-US" style="mso-font-kerning:
8.0pt">, <i style="mso-bidi-font-style:normal">p</i><sub>2</sub>, <i style="mso-bidi-font-style:normal">p</i><sub>3</sub>,
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">…</span><span lang="EN-US" style="mso-font-kerning:8.0pt">,
<i style="mso-bidi-font-style:normal">p<sub>n</sub></i><sub> </sub>(</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">它是输入序列的某一种排列</span><span lang="EN-US" style="mso-font-kerning:8.0pt">)</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">，则在输出序列中不可能出现以下情况，即存在</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">i</span></i><span lang="EN-US" style="mso-font-kerning:8.0pt">
< <i style="mso-bidi-font-style:
normal">j</i> < <i style="mso-bidi-font-style:normal">k</i></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">，使得</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p<sub>j</sub> </span></i><span lang="EN-US" style="mso-font-kerning:8.0pt"><
<i style="mso-bidi-font-style:
normal">p<sub>k</sub></i><sub> </sub>< <i style="mso-bidi-font-style:normal">p<sub>i</sub></i></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">。</span><span lang="EN-US" style="mso-font-kerning:8.0pt">(</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-font-kerning:
8.0pt">提示：用反证法</span><span lang="EN-US" style="mso-font-kerning:8.0pt">)<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height:15.5pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">【解答】</span></p>
<p class="MsoNormal" style="line-height:15.5pt"><span style="mso-tab-count: 1; mso-font-kerning: 8.0pt" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">因为借助栈由输入序列</span><span lang="EN-US" style="mso-font-kerning:8.0pt">1,
2, 3, </span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">…</span><span lang="EN-US" style="mso-font-kerning:8.0pt">,
<i style="mso-bidi-font-style:normal">n</i></span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">，可得到输出序列</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p</span></i><sub><span lang="EN-US" style="mso-font-kerning:8.0pt">1</span></sub><span lang="EN-US" style="mso-font-kerning:
8.0pt">, <i style="mso-bidi-font-style:normal">p</i><sub>2</sub>, <i style="mso-bidi-font-style:normal">p</i><sub>3</sub>,
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">…</span><span lang="EN-US" style="mso-font-kerning:8.0pt">,
<i style="mso-bidi-font-style:normal">p<sub>n</sub></i><sub> </sub></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">，如果存在下标</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">i</span></i><span lang="EN-US" style="mso-font-kerning:8.0pt">, <i style="mso-bidi-font-style:normal">j</i>,
<i style="mso-bidi-font-style:normal">k</i></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">，满足</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">i </span></i><span lang="EN-US" style="mso-font-kerning:8.0pt"><
<i style="mso-bidi-font-style:
normal">j</i> < <i style="mso-bidi-font-style:normal">k</i></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">，那么在输出序列中，可能出现如下</span><span lang="EN-US" style="mso-font-kerning:8.0pt">5</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">种情况：</span><span lang="EN-US" style="mso-font-kerning:
8.0pt"><o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:21.25pt;line-height:15.5pt"><span style="mso-char-type: symbol; mso-symbol-font-family: Monotype Sorts; font-size: 12.0pt; font-family: Monotype Sorts; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-font-kerning: 8.0pt" lang="EN-US">¬</span><span lang="EN-US" style="mso-font-kerning:8.0pt">
<i style="mso-bidi-font-style:normal">i</i></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">进栈，</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">i</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">出栈，</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">j</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">进栈，</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">j</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">出栈，</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">k</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">进栈，</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">k</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">出栈。此时具有最小值的排在最前面</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">p<sub>i</sub></span></i><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-font-kerning:
8.0pt">位置，具有中间值的排在其后</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p<sub>j</sub></span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">位置，具有最大值的排在</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">p<sub>k</sub></span></i><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-font-kerning:
8.0pt">位置，有</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p<sub>i</sub></span></i><span lang="EN-US" style="mso-font-kerning:8.0pt">
< <i style="mso-bidi-font-style:normal">p<sub>j</sub></i> < <i style="mso-bidi-font-style:normal">p<sub>k</sub></i>,
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">不可能出现</span><i style="mso-bidi-font-style:
normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p<sub>j </sub></span></i><span lang="EN-US" style="mso-font-kerning:8.0pt"><
<i style="mso-bidi-font-style:
normal">p<sub>k</sub></i> < <i style="mso-bidi-font-style:normal">p<sub>i</sub></i></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">的情形；</span><span lang="EN-US" style="mso-font-kerning:8.0pt"><o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:21.25pt;line-height:15.5pt"><span style="mso-char-type: symbol; mso-symbol-font-family: Monotype Sorts; font-size: 12.0pt; font-family: Monotype Sorts; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-font-kerning: 8.0pt" lang="EN-US">­</span><span lang="EN-US" style="font-size:12.0pt;mso-font-kerning:8.0pt">
</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">i</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">进栈，</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">i</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">出栈，</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">j</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">进栈，</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">k</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">进栈，</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">k</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">出栈，</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">j</span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">出栈。此时具有最小值的排在最前面</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:
8.0pt">p<sub>i</sub></span></i><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-font-kerning:
8.0pt">位置，具有最大值的排在</span><i style="mso-bidi-font-style:normal"><span lang="EN-US" style="mso-font-kerning:8.0pt">p<sub>j</sub></span></i><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">位置，具有中间值的排在最后</span><i⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -