📄 cs4.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" style="line-height: 150%"><span style="mso-spacerun: yes" lang="EN-US">
</span><b><span lang="EN-US" style="font-size:14.0pt;mso-bidi-font-size:
10.5pt"><span style="mso-spacerun: yes"> </span>第四章<span style="mso-spacerun: yes">
</span>栈和队列<o:p>
</o:p>
</span></b></p>
<p class="MsoPlainText" style="line-height: 150%"><b>一、填空题<span lang="EN-US"><o:p>
</o:p>
</span></b></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>1．线性表、栈和队列都是<u><span style="mso-spacerun: yes">
</span>①<span style="mso-spacerun: yes"> </span></u>结构，可以在线性表的<u><span style="mso-spacerun:
yes"> </span>②<span style="mso-spacerun: yes"> </span></u>位置插入和删除元素；对于栈只能在工<u><span style="mso-spacerun: yes">
</span>③<span style="mso-spacerun: yes"> </span></u>插入和删除元素；对于队列只能在<u><span style="mso-spacerun: yes">
</span>④<span style="mso-spacerun: yes"> </span></u>插入元素和在<u><span style="mso-spacerun: yes">
</span>⑤<span style="mso-spacerun: yes"> </span></u>删除元素。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>2．栈的插入和删除只能在栈的顶端进行，后进栈的元素必定先被删除，所以又把栈称作业表；队列的插入和删除运算分别在两端进行，进行插入的一端叫做<u><span style="mso-spacerun: yes">
</span>②<span style="mso-spacerun: yes"> </span></u>，进行删除的一端叫做<u><span style="mso-spacerun: yes">
</span>③<span style="mso-spacerun: yes"> </span></u>，先进队的元素必定先出队，所以又把队列称作<u><span style="mso-spacerun: yes">
</span>④<span style="mso-spacerun: yes"> </span></u>表。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>3．向顺序栈中插入新的元素分三步：第一步，进行<u><span style="mso-spacerun: yes">
</span>①<span style="mso-spacerun: yes"> </span></u>判断，判断条件是
<u><span style="mso-spacerun:
yes"> </span>② </u><span style="mso-spacerun: yes"> </span>；第二步是修改<u><span style="mso-spacerun: yes">
</span>③<span style="mso-spacerun: yes"> </span></u>；第三步即把新元素赋给<u><span style="mso-spacerun: yes">
</span>④ </u><span style="mso-spacerun:
yes"> </span>。同样从顺序栈中删除元素的过程可分三步：第一步进行<u><span style="mso-spacerun: yes">
</span>⑤<span style="mso-spacerun: yes"> </span></u>判断，判断条件为<u><span style="mso-spacerun: yes">
</span>⑥<span style="mso-spacerun: yes"> </span></u>，第二步是把<u><span style="mso-spacerun: yes">
</span>⑦ </u><span style="mso-spacerun:
yes"> </span>的值返回，第三步是<u><span style="mso-spacerun: yes">
</span>⑧ </u>。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>4，在递归算法中，每次递归调用前，系统自动把<u><span style="mso-spacerun: yes">
</span>①<span style="mso-spacerun: yes"> </span></u>，且的当前值以及调用后的<u><span style="mso-spacerun: yes">
</span>③ </u><span style="mso-spacerun:
yes"> </span>压入栈；在每次递归调用结束后，又自动作退栈处理，恢复值参和局部变量的原值，接羞④由返回地址所决定的位置执行。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>5．对于一个栈作进栈运算时，应先判别栈是否为<u><span style="mso-spacerun: yes">
</span>① </u><span style="mso-spacerun: yes"> </span>，作退栈运算时，应先判别栈是否为<u><span style="mso-spacerun:
yes"> </span>②<span style="mso-spacerun: yes"> </span></u>，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为<u><span style="mso-spacerun: yes">
</span>③ </u>。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的<u><span style="mso-spacerun: yes">
</span>④<span style="mso-spacerun: yes"> </span></u>分别设在这片内存空间的两端，这样只有当<u><span style="mso-spacerun: yes">
</span>⑤<span style="mso-spacerun: yes"> </span></u>时才产生上溢。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun:
yes"> </span>6.设有——空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，push，push后，输出序列是<u><span style="mso-spacerun: yes">
</span>①<span style="mso-spacerun: yes"> </span></u><span style="mso-spacerun: yes"> </span>。</span></p>
<p class="MsoPlainText" style="text-indent: -21.0pt; mso-char-indent-count: -2.0; mso-char-indent-size: 10.5pt; line-height: 150%; margin-left: 21.0pt"><span lang="EN-US"><span style="mso-spacerun:
yes"> </span>7．设一个数列的顺序为1，2，3，4，5，6，通过栈结构可以排成的顺序数列为<u>
①， ②,<span style="mso-spacerun: yes"> </span>③<span style="mso-spacerun: yes">
</span></u><span style="mso-spacerun: yes"> </span>。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>8．有一个循环队列如下图，其队满条件是<u><span style="mso-spacerun: yes">
</span>① </u><span style="mso-spacerun: yes"> </span>，队列空的条件是<u><span style="mso-spacerun: yes">
</span>②<span style="mso-spacerun: yes"> </span></u>。</span></p>
<p class="MsoPlainText" align="center" style="line-height: 150%"><span lang="EN-US"><!--[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:148.5pt;
height:63pt'>
<v:imagedata src="file:///C:/DOCUME~1/wangsj/LOCALS~1/Temp/msoclip1/01/clip_image001.gif"
o:title="dl"/>
</v:shape><![endif]-->
<img src="../tp/cs4.ht2.gif" v:shapes="_x0000_i1025" width="198" height="84"></span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>9．无论对于顺序存储还是链接存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为<u><span style="mso-spacerun:
yes"> </span>①<span style="mso-spacerun: yes"> </span></u>。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoPlainText" style="line-height: 150%">二、选择题<span style="mso-spacerun: yes" lang="EN-US"> </span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>1．若有—个栈的输入序列是1，2，3，…，n，输出序列出元素是____。</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">(A)n-i<span style="mso-spacerun:
yes"> </span>(B)<span style="mso-spacerun: yes"> </span>n-i-1<span style="mso-spacerun: yes">
</span>(C)<span style="mso-spacerun: yes"> </span>n-i+l<span style="mso-spacerun: yes">
</span>(D)不确定</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun:
yes"> </span>2．设有一个栈，元素的进栈次序为A，B，C，D，E，下列___是不可能的出栈序列</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">(A)A，B，C，D，E<span style="mso-spacerun:
yes"> </span>(B)B，C，D，E，A</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US">(C)E，<span style="mso-spacerun: yes">
</span>A，<span style="mso-spacerun: yes"> </span>B，<span style="mso-spacerun:
yes"> </span>C，<span style="mso-spacerun: yes"> </span>D<span style="mso-spacerun: yes">
</span>(D)E，<span style="mso-spacerun: yes"> </span>D，<span style="mso-spacerun: yes">
</span>C，<span style="mso-spacerun:
yes"> </span>B，<span style="mso-spacerun: yes"> </span>A</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun:
yes"> </span>3．在一个具有n个单元的顺序栈中，假定以地址低端(即0单元)作为栈底，以top作为栈顶指针，则当做出栈处理时，top变化为_______.</span></p>
<p class="MsoPlainText" style="line-height: 150%"><span lang="EN-US"><span style="mso-spacerun: yes">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -