数据结构 第3章 栈和队列答案.doc

《数据结构 第3章 栈和队列答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第三章栈和队列答案一、选择题1.B2.1B2.2A2.3B2.4D2.5.C3.B4.D5.D6.C7.D8.B9.D10.D11.D12.C13.B14.C15.B16.D17.B18.B19.B20.D21.D22.D23.D24.C25.A26.A27.D28.B29.BD30.C31.B32.C33.1B33.2A33.3C33.4C33.5F34.C35.C36.A37.AD二、判断题1.√2.√3.√4.√5.×6.√7.√8.√9.√10.×11.√12.×13.×14.×15.√16.×17.√18.×19.√20

2、.√部分答案解释如下。1、尾递归的消除就不需用栈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/+（注

3、：表达式中的点(.)表示将数隔开，如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者，值改取M20、sq.front=(sq.front+1)%(M+1)；return(

4、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）i0（4）top

5、只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。2、队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。3、用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维

6、数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。4、（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的S×S×S×操作序列；对于合法序列BAC，我们使用SS××S×操作序列。5、三个：CDEBA，CDBEA，CDBAE6

7、、输入序列为，不能得出，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。得到的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果。7、能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。其理由为：若出栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不可能早于C出栈

8、，故不可能得到D、B、A、C、E出栈序列。8、借助栈结构，n个入栈元素可得到1/(n+1)((2n）！/（n!*n!）)种出栈序列。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种。但dabc和adbc是不可能得到的两种。9、不能得