📄 cs4da.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>第四章</title>
</head>
<body>
<p class="MsoPlainText">第四章</p>
<p class="MsoPlainText">解答：</p>
<p class="MsoPlainText">一、填空题</p>
<p class="MsoPlainText"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>1．①线性<span style="mso-spacerun: yes"> </span>②任何<span style="mso-spacerun: yes">
</span>⑧栈顶<span style="mso-spacerun: yes"> </span>④队尾<span style="mso-spacerun: yes">
</span>⑤队头</span></p>
<p class="MsoPlainText"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>2．①后进先出<span style="mso-spacerun: yes"> </span>②队尾<span style="mso-spacerun: yes">
</span>③队头或队首<span style="mso-spacerun: yes"> </span>④先进先出</span></p>
<p class="MsoPlainText"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>3．①溢出或栈满<span style="mso-spacerun: yes"> </span>②s-->top=maxsize-1
⑧栈顶指针 ④栈顶单元 ⑤栈空</span></p>
<p class="MsoPlainText" style="text-indent:42.0pt;mso-char-indent-count:4.0;
mso-char-indent-size:10.5pt">⑥<span lang="EN-US">s-->top=-l<span style="mso-spacerun: yes">
</span>⑦栈顶指针<span style="mso-spacerun: yes"> </span>⑧修改栈顶指针</span></p>
<p class="MsoPlainText"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>4．①值参<span style="mso-spacerun: yes"> </span>②局部变量<span style="mso-spacerun: yes">
</span>③返回地址<span style="mso-spacerun: yes"> </span>④无条件转向</span></p>
<p class="MsoPlainText"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>5．①栈满<span style="mso-spacerun: yes"> </span>②栈空<span style="mso-spacerun: yes">
</span>⑧m<span style="mso-spacerun: yes"> </span>④栈底<span style="mso-spacerun: yes">
</span>⑤两个栈的栈顶在栈空间的某一位置相遇</span></p>
<p class="MsoPlainText"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>6. ①2, 3</span></p>
<p class="MsoPlainText"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>7.①3、2、5、6、4、1<span style="mso-spacerun: yes"> </span>②2,4,3,5,1,6<span style="mso-spacerun: yes">
</span>③4,5,3,6,2,1</span></p>
<p class="MsoPlainText"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>8.①front=(rear+1)％n<span style="mso-spacerun: yes"> </span>②rear=front</span></p>
<p class="MsoPlainText"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>9.①O(1)</span></p>
<p class="MsoPlainText">二选择题</p>
<p class="MsoPlainText"><span lang="EN-US">1．(C)<span style="mso-spacerun: yes">
</span>2．(C)<span style="mso-spacerun: yes"> </span>3．(c)<span style="mso-spacerun: yes">
</span>4、(d)<span style="mso-spacerun: yes"> </span>5、(c)<span style="mso-spacerun: yes">
</span>6.(b)<span style="mso-spacerun: yes"> </span>7.(c)<span style="mso-spacerun: yes">
</span>8.(a)</span></p>
<p class="MsoPlainText"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText">三、应用题</p>
<p class="MsoNormal" style="line-height:15.5pt"><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">、</span><!--[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_s1026" type="#_x0000_t75" style='position:absolute;
left:0;text-align:left;margin-left:167.75pt;margin-top:14.95pt;width:146.9pt;
height:17.9pt;z-index:-1;mso-wrap-edited:f;mso-position-horizontal-relative:text;
mso-position-vertical-relative:text' wrapcoords="3491 2107 3055 3688 3491 7902 7418 10537 873 10537 218 11063 1091 19493 6982 19493 10909 18966 20727 13171 20509 10537 21382 7902 19636 6849 4364 2107 3491 2107"
o:allowincell="f">
<v:imagedata src="file:///C:/DOCUME~1/wangsj/LOCALS~1/Temp/msoclip1/01/clip_image001.wmz"
o:title=""/>
<v:textbox style='mso-next-textbox:#_x0000_s1026'/>
<w:wrap type="tight"/>
</v:shape><![if gte mso 9]><o:OLEObject Type="Embed" ProgID="Equation.3"
ShapeID="_x0000_s1026" DrawAspect="Content" ObjectID="_1083003420">
</o:OLEObject>
<![endif]><![endif]-->
<img src="../tp/cs4da.5.gif" align="left" hspace="12" v:shapes="_x0000_s1026" width="196" height="24"><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 lang="EN-US"><span style="mso-tab-count:1">
</span>(1) </span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">可能的不同出栈序列有</span>
<span style="mso-spacerun: yes" lang="EN-US"> </span><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 lang="EN-US"><span style="mso-tab-count:1">
</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">435612</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">和</span><span lang="EN-US">154623</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">这样的出栈序列。因为若在</span><span lang="EN-US">4,
3, 5, 6</span><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</span><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</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">必须一直在栈中，此时</span><span lang="EN-US">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">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">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">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">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">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">154623</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">也是这种情况。出栈序列</span><span lang="EN-US">325641</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">和</span><span lang="EN-US">135426</span><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 lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt"> <o:p>
</o:p>
</span></p>
<table border="1" cellspacing="0" cellpadding="0" style="margin-left:41.4pt;
border-collapse:collapse;mso-table-layout-alt:fixed;border:none;mso-border-alt:
solid windowtext .5pt;mso-padding-alt:0cm 5.4pt 0cm 5.4pt">
<tr>
<td width="24" valign="top" style="width:18.0pt;border: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">3<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-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-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:solid windowtext .5pt;
border-left:none;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">5<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-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:solid windowtext .5pt;
border-left:none;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>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -