第三章 栈和队列答案Word文档下载推荐.docx
《第三章 栈和队列答案Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《第三章 栈和队列答案Word文档下载推荐.docx（22页珍藏版）》请在冰点文库上搜索。
2.√
3.√
4.√
5.×
6.√
7.√
8.√
9.√
10.×
11.√
12.×
13.×
14.×
15.√
16.×
17.√
18.×
19.√
20.√
部分答案解释如下。
1、1、尾递归的消除就不需用栈
2、2、这个数是前序序列为1,2,3,…,n，所能得到的不相似的二叉树的数目。
三、填空题
1、操作受限（或限定仅在表尾进行插入和删除操作）后进先出
2、栈3、3124、23100CH5、0n+1top[1]+1=top[2]
6、两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）。
7、
（1）满
（2）空（3）n（4）栈底（5）两栈顶指针相邻（即值之差的绝对值为1）
8、链式存储结构9、S×
SS×
S×
×
10、data[++top]=x；
11、23.12.3*2-4/34.5*7/++108.9/+（注：
表达式中的点（.）表示将数隔开，如23.12.3是三个数）
12、假溢出时大量移动数据元素。
13、（M+1）MODN（M+1）%N；
14、队列15、先进先出16、先进先出
17、s=（LinkedList）malloc（sizeof（LNode））；
s->
data=x;
s->
next=r->
next；
r->
next=s；
r=s；
18、牺牲一个存储单元设标记
19、（TAIL+1）MODM=FRONT（数组下标0到M-1，若一定使用1到M，则取模为0者，值改取M
20、sq.front=（sq.front+1）%（M+1）；
return（sq.data（sq.front））；
（sq.rear+1）%（M+1）==sq.front；
21、栈22、（rear-front+m）%m；
23、（R-P+N）%N；
24、
（1）a[i]或a[1]
（2）a[i]（3）pop（s）或s[1]；
25、
（1）PUSH（OPTR，w）
（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b））
26、
（1）T>
0
（2）i<
n（3）T>
0（4）top<
n（5）top+1（6）true（7）i-1（8）top-1（9）T+w[i]（10）false
四、应用题
1、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。
最后插入的元素最先删除，故栈也称后进先出（LIFO）表。
2、队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。
最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。
3、用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。
循环队列是解决“假溢出”的一种方法。
通常把一维数组看成首尾相接。
在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。
4、
（1）通常有两条规则。
第一是给定序列中S的个数和X的个数相等；
第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。
（2）可以得到相同的输出元素序列。
例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。
对于合法序列ABC，我们使用本题约定的S×
操作序列；
对于合法序列BAC，我们使用SS×
操作序列。
5、三个：
CDEBA，CDBEA，CDBAE
6、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。
得到135426的过程如下：
1入栈并出栈，得到部分输出序列1；
然后2和3入栈，3出栈，部分输出序列变为：
13；
接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；
最后6入栈并退栈，得最终结果135426。
7、能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。
其理由为：
若出栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。
8、借助栈结构，n个入栈元素可得到1/（n+1）（（2n）！
/（n!
*n!
））种出栈序列。
本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种。
但dabc和adbc是不可能得到的两种。
9、不能得到序列2，5，3，4，6。
栈可以用单链表实现，这就是链栈。
由于栈只在栈顶操作，所以链栈通常不设头结点。
10、如果i<
j，则对于pi<
pj情况，说明pi在pj入栈前先出栈。
而对于pi>
pj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。
这就说明，对于i<
j<
k，不可能出现pj<
pk<
pi的输出序列。
换句话说，对于输入序列1，2，3，不可能出现3，1，2的输出序列。
11、
（1）能得到325641。
在123依次进栈后，3和2出栈，得部分输出序列32；
然后4，5入栈，5出栈，得部分出栈序列325；
6入栈并出栈，得部分输出序列3256；
最后退栈，直到栈空。
得输出序列325641。
其操作序列为AAADDAADADDD。
（2）不能得到输出顺序为154623的序列。
部分合法操作序列为ADAAAADDAD，得到部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。
12、
（1）一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。
例如，函数f在执行中，又调用函数f自身，这称为直接递归；
若函数f在执行中，调用函数g，而g在执行中，又调用函数f，这称为间接递归。
在实际应用中，多为直接递归，也常简称为递归。
（2）递归程序的优点是程序结构简单、清晰，易证明其正确性。
缺点是执行中占内存空间较多，运行效率低。
（3）递归程序执行中需借助栈这种数据结构来实现。
（4）递归程序的入口语句和出口语句一般用条件判断语句来实现。
递归程序由基本项和归纳项组成。
基本项是递归程序出口，即不再递归即可求出结果的部分；
归纳项是将原来问题化成简单的且与原来形式一样的问题，即向着“基本项”发展，最终“到达”基本项。
13、函数调用结束时vol=14。
执行过程图示如下：
vol（4）vol（4）=vol（3）+5
14=vol
（2）+3+5
=vol
（1）+4+3+5
vol（3）+5=vol（0）+2+4+3+5
9=0+2+4+3+5
=14
vol
（2）+3
6
vol
（1）+4
2
vol（0）+2
0
14、过程p递归调用自身时，过程p由内部定义的局部变量在p的2次调用期间，不占同一数据区。
每次调用都保留其数据区，这是递归定义所决定，用“递归工作栈”来实现。
15、设Hn为n个盘子的Hanoi塔的移动次数。
（假定n个盘子从钢针X移到钢针Z，可借助钢针Y）
则Hn=2Hn-1+1//先将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z
=2（2Hn-2+1）+1
=22Hn-2+2+1
=22（2Hn-3+1）+2+1
=23Hn-3+22+2+1
·
=2kHn-k+2k-1+2k-2+…+21+20
=2n-1H1+2n-2+2n-3+…+21+20
因为H1=1，所以原式Hn=2n-1+2n-2+…+21+20=2n-1
故总盘数为n的Hanoi塔的移动次数是2n-1。
16、运行结果为：
1213121（注：
运行结果是每行一个数，为节省篇幅，放到一行。
）
17、两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。
设共享数组为S[MAX]，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。
用C写的入栈操作push（i，x）如下：
constMAX=共享栈可能达到的最大容量
typedefstructnode
{elemtypes[MAX]；
inttop[2]；
}anode；
anodeds;
intpush（inti,elemtypex）
//ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。
i的值为0或1，x为类型为elemtype的元素。
本算法将x压入栈中。
如压栈成功，返回1；
否则，返回0。
{if（ds.top[1]-ds.top[0]==1）{printf（“栈满\n”）；
return（0）；
}
switch（i）
{case0：
ds.s[++ds.top[i]]=x；
break；
case1：
ds.s[--ds.top[i]]=x；
return
（1）；
}//入栈成功。
}
18、本程序段查找栈S中有无整数为k的元素，如有，则删除。
采用的办法使用另一个栈T。
在S栈元素退栈时，若退栈元素不是整数k，则压入T栈。
遇整数k，k不入T栈，然后将T栈元素全部退栈，并依次压入栈S中，实现了在S中删除整数k的目的。
若S中无整数k，则在S退成空栈后，再将T栈元素退栈，并依次压入S栈。
直至T栈空。
这后一种情况下S栈内容操作前后不变。
19、中缀表达式8-（3+5）*（5-6/2）的后缀表达式是：
835+562/-*-
栈的变化过程图略（请参见22题），表达式生成过程为：
中缀表达式exp1转为后缀表达式exp2的规则如下：
设操作符栈s，初始为空栈后，压入优先级最低的操作符‘#’。
对中缀表达式从左向右扫描，遇操作数，直接写入exp2；
若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。
（1）w为一般操作符（’+’，’-‘，’*’，’/’等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；
否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。
（2）w为左括号（’（’），w入栈。
（3）w为右括号（’）’），操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入exp2），右括号也丢掉，达到exp2中消除括号的目的。
（4）w为‘#’，表示中缀表达式exp1结束，操作符栈退栈到exp2，直至碰到‘#’，退栈，整个操作结束。
这里，再介绍一种简单方法。
中缀表达式转为后缀表达式有三步：
首先，将中缀表达式中所有的子表达式按计算规则用嵌套括号括起来；
接着，顺序将每对括号中的运算符移到相应括号的后面；
最后，删除所有括号。
例如，将中缀表达式8-（3+5）*（5-6/2）转为后缀表达式。
按如上步骤：
执行完上面第一步后为：
（8-（（3+5）*（5-（6/2））））；
执行完上面第二步后为：
（8（（35）+（5（62）/）-）*）-；
执行完上面第三步后为：
835+562/-*-。
可用类似方法将中缀表达式转为前缀表达式。
20、中缀表达式转为后缀表达式的规则基本上与上面19题相同，不同之处是对运算符**优先级的规定。
在算术运算中，先乘除后加减，先括号内后括号外，相同级别的运算符按从左到右的规则运算。
而对**运算符，其优先级同常规理解，即高于加减乘除而小于左括号。
为了适应本题中“从右到左计算”的要求，规定栈顶运算符**的级别小于正从表达式中读出的运算符**，即刚读出的运算符**级别高于栈顶运算符**，因此也入栈。
下面以A**B**C为例说明实现过程。
读入A，不是操作符，直接写入结果表达式。
再读入*，这里规定在读入*后，不能立即当乘号处理，要看下一个符号，若下个符号不是*，则前个*是乘号。
这里因为下一个待读的符号也是*，故认为**是一个运算符，与运算符栈顶比较（运算符栈顶初始化后，首先压入‘#’作为开始标志），其级别高于‘#’，入栈。
再读入B，直接进入结果表达式。
接着读入**，与栈顶比较，均为**，我们规定，后读入的**级别高于栈顶的**，因此**入栈。
接着读入C，直接到结果表达式。
现在的结果（后缀）表达式是ABC。
最后读入‘#’，表示输入表达式结束，这时运算符栈中从栈顶到栈底有两个**和一个‘#’。
两个运算符**退栈至结果表达式，结果表达式变为ABC****。
运算符栈中只剩‘#’，退栈，运算结束。
21、
（1）sum=21。
当x为局部变量时，每次递归调用，都要给局部变量分配存储单元，故x数值4，9，6和2均保留，其递归过程示意图如下：
sum（4）
21
sum（3）+4（x=4）
17
sum
（2）+9（x=9）
8
sum
（1）+6（x=6）
sum（0）+2（x=2）
（2）sum=8,当x为全局变量时，在程序的整个执行期间，x只占一个存储单元，先后读入的4个数（4,9,6,2）,仅最后一个起作用。
当递归调用结束，逐层返回时sum:
=sum（n-1）+x表达式中，x就是2，所以结果为sum=8。
22、设操作数栈是opnd，操作符栈是optr，对算术表达式A-B*C/D-E↑F求值，过程如下：
步骤
opnd栈
optr栈
输入字符
主要操作
初始
#
A-B*C/D-E↑F#
PUSH（OPTR,’#’）
1
A
PUSH（OPND,A）
2
#-
-B*C/D-E↑F#
PUSH（OPTR,’-’）
3
AB
B*C/D-E↑F#
PUSH（OPND,B）
4
#-*
*C/D-E↑F#
PUSH（OPTR,’*’）
5
ABC
C/D-E↑F#
PUSH（OPND,C）
6
AT（T=B*C）
#-/
/D-E↑F#
PUSH（OPND,POP（OPND）*POP（OPND））
PUSH（OPTR,’/’）
7
ATD
D-E↑F#
PUSH（OPND,D）
8
AT（T=T/D）
T（T=A-T）
#-
-E↑F#
x=POP（OPND）;
y=POP（OPND）
PUSH（OPND,y/x）;
y=POP（OPND）;
PUSH（OPND,y-x）
9
TE
E↑F#
PUSH（OPND,E）
10
#-↑
↑F#
PUSH（OPTR,‘↑’）
11
TEF
F#
PUSH（OPND,F）
12
TS（S=E↑F）
R（R=T-S）
#-
#
X=POP（OPND）Y=POP（OPND）
POP（OPTR）PUSH（OPND,y↑x）
x=POP（OPND）y=POP（OPND）
POP（OPTR）PUSH（OPND,y-x）
23、
栈S1
栈S2
输入的算术表达式（按字符读入）
®
A-B*C/D+E/F®
-
-B*C/D+E/F®
B*C/D+E/F®
-*
*C/D+E/F®
C/D+E/F®
AT1（注：
T1=B*C）
-/
/D+E/F®
AT1D
D+E/F®
AT2（注：
T2=T1/D）
T3（注：
T3=A-T2）
+
+E/F®
T3E
E/F®
+/
/F®
T3EF
F®
T3T4（注：
T4=E/F）
T5（注：
T5=T3+T4）
24、XSXXXSSSXXSXXSXXSSSS
25、S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。
26、设栈S1和栈S2共享向量V[1..m]，初始时，栈S1的栈顶指针top[0]=0，栈S2的栈顶指针top[1]=m+1，当top[0]=0为左栈空，top[1]=m+1为右栈空；
当top[0]=0并且top[1]=m+1时为全栈空。
当top[1]-top[0]=1时为栈满。
27、
（1）每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。
（2）多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个栈满时要向左、右栈查询有无空闲单元。
如果有，则要移动元素和修改相关的栈底和栈顶指针。
当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。
（3）多个链栈一般不考虑栈的溢出（仅受用户内存空间限制），缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。
28、设top1和top2分别为栈1和2的栈顶指针
（1）入栈主要语句
if（top2-top1==1）{printf（“栈满\n”）;
exit（0）;
case1:
top1++；
SPACE[top1]=x;
//设x为入栈元素。
case2:
top2--；
SPACE[top2]=x;
出栈主要语句
case1：
if（top1==-1）{printf（“栈空\n”）；
exit（0）；
top1--；
return（SPACE[top1+1]）；
//返回出栈元素。
case2：
if（top2==N）{printf（“栈空\n”）；
top2++；
return（SPACE[top2-1]）；
（2）栈满条件：
top2-top1=1
栈空条件：
top1=-1并且top2=N//top1=-1为左栈空，top2=N为右栈空
29、设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。
设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。
当front等于-1时队空，rear等于m-1时为队满。
由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。
这时若再有入队操作，会造成假“溢出”。
其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；
二是将队列看成首尾相连，即循环队列（0..m-1）。
在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。
另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；
tag=1情况下，若因插入导致front=rear则为队满。
30、见上题29的解答。
31、参见上面29题。
32、typedefstructnode
{elemtypeelemcq[m];
//m为队列最大可能的容量。
intfront,rear;
//front和rear分别为队头和队尾指针。
}cqnode;
cqnodecq;
（1）
（1）初始状态
cq.front=cq.rear=0;
（2）
（2）队列空
cq.front==cq.rear;
（3）（3）队列满
（cq.rear+1）%m==cq.front;
33、栈的特点是后进先出，队列的特点是先进先出。
初始时设栈s1和栈s2均为空。
（1）用栈s1和s2模拟一个队列的输入：
设s1和s2容量相等。
分以下三种情况讨论：
若s1未满，则元素入s1栈；
若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；
若s1满，s2不空（已有出队列元素），则不能入队。
（2）用栈s1和s2模拟队列出队（删除）：
若栈s2不空，退栈，即是队列的出队；
若s2为空且s1不空，则将s1栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。
若栈s1为空并且s2也为空，队列空，不能出队。
（3）判队空若栈s1为空并且s2也为空，才是队列空。
讨论：
s1和s2容量之和是队列的最大容量。
其操作是，s1栈满后，全部退栈并压栈入s2（设s1和s2容量相等）。
再入栈s1直至s1满。
这相当队列元素“入队”完毕。
出队时，s2退栈完毕后，s1栈中元素依次退栈到s2，s2退栈完毕，相当于队列中全部元素出队。
在栈s2不空情况下，若要求入队操作，只要s1不满，就可压入s1中。
若s1满和s2不空状态下要求队列的入队时，按出错处理。
34、
（1）队空s.front=s.rear；
//设s是sequeuetp类型变量
（2）队满：
（s.rear+1）MODMAXSIZE=s.front//数组下标为0..MAXSIZE-1
具体参见本章应用题第29题
35、typedefstruct
{elemtpq[m];
intfront,count;
//front是队首指针，count是队列中元素个数。
//定义类型标识符。
（1）判空：
intEmpty（cqnodecq）//cq是cqnode类型的变量
{if（cq.count==0）return
（1）；
elsereturn（0）;
//空队列}
入队:
intEnQueue（cqnodecq，elemtpx）
{if（count==m）{printf（“队满\n”）；
exit（0）;
cq.q[（cq.front+count）%m]=x;
//x入队
count++;
return
（1）;
//队列中元素个数增加1,入队成功。
出队:
intDelQueue（
升级会员 