第三章 栈和队列 一、选择题 1.B 9.D 21.D 33.1B 1.√ 13. × 2.1B 10.D 22.D 2.2A 11.D 23.D 2.3B 12.C 24.C 33.4C 4. √ 16.× 2.4D 13.B 25.A 2.5.C 14.C 26.A 3.B 15.B 27.D 35.C 7.√ 19.√ 4.D 28.B 5.D 29.BD 6.C 18.B 30.C 10.× 7.D 19.B 31.B 11. √ 8.B 20.D 32.C 12.× 16.D 17.B 36.A 37.AD 8. √ 20. √ 9. √ 33.2A 33.3C 2.√ 14.× 3. √ 15. √ 33.5F 34.C 5.× 17.√ 6.√ 18.× 二、判断题 部分答案解释如下。 1、 尾递归的消除就不需用栈
2、 这个数是前序序列为1,2,3,…,n，所能得到的不相似的二叉树的数目。
三、填空题
1、操作受限（或限定仅在表尾进行插入和删除操作） 后进先出 2、栈 3、3 1 2 4、23 100CH 5、0 n+1 top[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) MOD N (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）MOD M=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 1、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。 2、队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。 3、用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。 4、（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。 （2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的S×S×S×操作序列；对于合法序列BAC，我们使用SS××S×操作序列。 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 （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 =2 Hn-2+2+1 =22（2Hn-3+1）+2+1 =23 Hn-3+22+2+1 · · · = 2k Hn-k+2k-1 +2k-2 +?+21 +20 n-1n-2n-310 =2 H1+2+2+?+2+2 因为H1=1，所以原式Hn=2n-1+2n-2+?+21+20=2n-1 故总盘数为n的Hanoi塔的移动次数是2-1。 16、运行结果为：1 2 1 3 1 2 1（注：运行结果是每行一个数，为节省篇幅，放到一行。） 17、两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。 用C写的入栈操作push（i，x）如下： const MAX=共享栈可能达到的最大容量 typedef struct node {elemtype s[MAX]； int top[2]； }anode； anode ds; int push(int i,elemtype x) //ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。i的值为0或1，x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回1；否则，返 n 2 回0。 {if（ds.top[1]-ds.top[0]==1）{printf（“栈满\\n”）；return（0）；} switch（i） {case 0：ds.s[++ds.top[i]]=x；break； case 1：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）的后缀表达式是： 8 3 5 + 5 6 2 / - * - 栈的变化过程图略（请参见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)/)-)*)- ； 执行完上面第三步后为：8 3 5 + 5 6 2 / - * - 。 可用类似方法将中缀表达式转为前缀表达式。 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） 2 sum（0）+2 （x=2） 0