栈与队列答案

《栈与队列答案》由会员分享，可在线阅读，更多相关《栈与队列答案（5页珍藏版）》请在装配图网上搜索。

1、第三章栈和队列一、选择题二、判断题1.V2.V3.J4.、/5.x677.V8.V9.J10.x11.V12.x13.x14.x15.、/16.x17.V18.x19.V20.部份答案解释如下。1、1、尾递归的消除就不需用栈2、二、那个数是前序序列为L2,3，,n,所能取得的不相似的二叉树的数量。三、填空题1、操作受限(或限定仅在表尾进行插入和删除操作)后进先出2、栈3、3124、23100CH5、0n+1topl+l=top26、两栈顶指针值相减的绝对值为1(或两栈顶指针相邻)。7、(1)满(2)空(3)n(4)栈底(5)两栈顶指针相邻(即值之差的绝对值为1)8、链式存储结构9、SXSSXS

2、XX10、data+top=x：11、(注：表达式中的点(.)表示将数隔开，如是三个数)12、假溢出时大量移动数据元素。13、(M+l)MODN(M+l)%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=FR0NT(数组下标。到M-1,若必然利用1到M,则取模为0者,值改取M20=+l)%(M+l)；return):+1)%(M+l)=：21、栈22、(rear-front+m)%m：23、(R

3、-P+N)%N；24、(1)ai或(2)ai(3)pop(s)或sl：25、(1)PUSH(OPTR,w)(2)POP(OPTR)(3)PUSH(OPND,operate(a,theta,b)26、(1)T0(2)i0(4)topn(5)top+1(6)true(7)i-1(8)top-1(9)T+wi(10)false四、应用题1、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LIFO)表。2、队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开(删除)

4、，故队列也常称先进先出(FIFO)表。3、用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成“假溢出”现象，即队尾已抵达一维数组的高低标，不能再插入，但是队中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”的一种方式。通常把一维数组看成首尾相接。在循环队列下，通常采用“捐躯一个存储单元”或“作标记”的方式解决“队满”和“队空”的判定问题。4、(1)通常有两条规则。第一是给定序列中S的个数和X的个数相等：第二是从给定序列的开始，到给定序列中的任一名置，S的个数要大于或等于X的个数。(2)能够取得相同的输出元素序列。例如，输入元素为A,B,C,则两个

5、输入的合法序列ABC和BAC都可取得输出元素序列ABC。对于合法序列ABC,咱们利用本题约定的SXSXSX操作序列：对于合法序列BAC,咱们利用SSXXSX操作序列。5、三个：CDEBA,CDBEA,CDBAE6、输入序列为123456,不能得出435612,其理由是，输出序列最后两元素是12,前面4个元素(4356)取得后，栈中元素剩12,且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。取得135426的进程如下：1入栈并出栈，取得部份输出序列1：然后2和3入栈，3出栈，部份输出序列变成：13：接着4和5入栈，5,4和2依次出栈，部份输出序列变成13542：最后6入栈并退栈，得最终结果13

6、5426。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个入栈元素可取得l/(n+l)(2n)!/(n!*n!)种出栈序列。本题4个元素，可有14种出栈序列，abed和dcba就是其中两种。但dabc和adbc是不可能取得的两种。9、不能取得序列2,5,3,4,60栈能够用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。10、若是i=?O9)(num=num+(ord(x)-ord(O)/scale;scale=scale*10;scanf(a%c,&x);/elsepush(OPND,num);num二;/数压入栈，下个数初始化casex=:break;/遇空格，继续读下一个字符。casex=+:push(OPND,pop(OPND)+pop(OPND);break；casex=-：xl=pop(OPND);x2=pop(OPND);push(OPND,x2-xl);break;