3.3.2 答案解析
一、单项选择题
1、C。根据栈的“后进先出”的特性，d最先出栈，则进栈顺序一定是a、b、c、d，栈顶元素为d，所以d出栈后，c接着出栈，然后将e入栈，再将e出栈，接着出栈元素为b和a，只可能是b先出栈，最后才会是a出栈，所以C不正确。其余选项均是可能的出栈顺序。
2、D。主要考查栈的后进先出特征。
3、D。主要考查采用链式存储的栈的出栈基本操作。
4、A。根据栈的后进先出的特性，将a和b入栈之后，栈中有两个元素a和b，然后将栈顶元素出栈，栈中只有一个元素a，取栈顶元素存入x，因此选择A。
5、C。因为p2=3，表明第二个出栈的元素为3。第一个出栈的元素可能是1或2，若将1入栈，再出栈，然后将2和3先后入栈，将3出栈，此时栈中的元素为2，则先后出栈的元素依次是1、3、…；若将1和2入栈，再出栈，则出栈的元素为2，然后将3入栈，再出栈，此时栈中的元素为1，则先后出栈的元素依次是2、3、…。p3即第3个出栈的元素可能是1、2、4、…、n，因此p3的可能取值个数为n-1个。
6、C。根据入栈顺序为abcdefg和出栈顺序为bdcfeag，可知a和b入栈后，栈中元素为a和b，然后将b出栈；将c和d入栈，则栈中元素为a、c和d，再分别将d和c出栈，此时栈中元素为a，再将e和f入栈，则栈中元素为a、e和f，将f、e和a出栈，此时栈为空，最后将g入栈，再将g出栈。
7、B。将中缀表达式转换为后缀表达式可以利用栈的后进先出思想进行转换，也可以通过建立对应的二叉树进行后序遍历得到。利用栈的后进先出思想，将a*（b+c）-d转换为对应的后缀表达式的过程如表3-4所示。
表3-4 中缀表达式a*（b+c）-d转换为后缀表达式的过程
也可以利用二叉树的遍历思想，先创建二叉树，然后根据后序遍历得到对应的后缀表达式。a*（b+c）-d对应的二叉树如图3-6所示。二叉树的中序遍历序列就是a*（b+c）-d，后序遍历序列a b c+*d–就是后缀表达式。
图3-6 二叉树
8、D。主要考查递归的定义。
9、B。主要考查栈与递归的关系。
10、B。在递归调用过程中，其函数是作为递归函数func的参数使用的。要计算func（func（1）），首先计算func函数中参数部分，将1代入func，在func函数中，因为1>0，则应返回1*func（0），将0传递给func函数，将2返回，得到func（1）的值为1*2，即2。此时，原主调函数变成了func（2），继续将2传递给func函数，因为2>0，则该层返回2*func（1），继续将1传递给func函数，以此类推，直至func函数的参数为0，得到返回值2返回到上一层，其实刚才已经知道func（1）的值为2，从而得到func（2）的返回值为2*2，即4。
11、C。主要考查链式存储的栈的入栈基本操作。
12、A。主要考查栈为空的条件。
13、C。主要考查递归与栈的主要特点。对于I，将递归程序转换为非递归程序，如果是简单的尾递归，如求n！，可以直接使用循环实现，不需要使用栈。对于II，在递归调用时，系统会利用栈保存函数参数和函数地址。对于III，已知入栈次序，可能有多个出栈序列。对于IV，栈是一种受限的线性表，但是只允许在一端（即栈顶）进行操作。
14、B。执行3次F（）的过程如图3-7所示。
图3-7 算术运算过程中栈的变化过程
15、A。主要考查函数调用过程中，系统是如何利用栈来保存函数信息的。
16、ABD。对于A，令1入栈，再将其出栈，然后将2入栈并出栈，接着让3入栈并出栈，最后让4入栈并出栈，则得到的出栈序列就是1、2、3、4，则p2和p4分别是2和4。对于B，依次先让1、2、3入栈，再将栈顶元素出栈两次，分别得到3和2，此时栈中只有1，然后将4入栈并将其出栈，最后将1出栈，则出栈顺序依次为3、2、4、1，p2和p4分别是2和1。对于D，先将1、2入栈，再将栈顶元素出栈，得到2，接着让3入栈并出栈，再将栈底元素1出栈，最后将4入栈并出栈，得到的出栈序列依次是2、3、1、4，则p2和p4分别是3和4。对于C，为了使出栈元素p2是4，需要依次先将1、2、3先入栈，再将栈顶元素出栈，得到3，然后将4入栈并出栈，此时栈中剩下2和1两个元素，故出栈序列是3、4、2、1，则p2和p4分别是4和1。
17、D。主要考查链栈的入栈操作。
18、C。对于A，若先将1、2、3依次入栈，再将3、2出栈，则p1为3，p2为2。若将3出栈后，继续将4入栈，则p2为4。不可能出现p2为1的情况。
二、综合分析题
1、（1）Push（N%8）；（2）!StackEmpty（S）
2、如果队列不为空，则将队列中的队头元素出队。
3、Convert（）函数的作用是通过调用自身，将得到的整数n依次除以10以缩小问题规模，将前面的数依次存放到字符数组a中。为了让整数n的百、十、个位数字逆序后，依次存放在字符数组a中，可在递归调用Convert（）函数时，将前n-1个数字存放在第i个下标后面的位置上，个位数字存放在数组a中的第一个位置。
（1）a+1；（2）n%10+'0'
4、（1）将中缀表达式转换为后缀表达式的过程如表3-5所示。
表3-5 中缀表达式转换为后缀表达式的过程
（2）利用得到的后缀表达式5 12 3-*4+2/求解表达式的值时，栈中元素变化情况如图3-8所示。
图3-8 栈中元素变化过程
三、算法设计题
1、主要考查栈的顺序存储结构、动态分配及栈的基本操作。若使用栈顶指针、栈底指针和数组来存储栈的元素、表示栈，通常使用栈底指针base表示数组的基地址，栈顶指针top指向栈顶，另外引入stacksize表示栈的最大容量。栈的顺序存储结构定义如下：
栈的初始化、入栈、出栈操作实现如下：
测试代码如下：
2、主要考查栈的链式存储及基本操作。入栈和出栈操作如下，完整代码可从下载代码中获取。
（1）将元素e入栈。先动态生成一个结点，用p指向该结点，将元素e值赋给*p结点的数据域，然后将新结点插入到链表的第一个结点之前。把新结点插入到链表中的步骤如下：①p->next=top->next；②top->next=p，如图3-9所示。
图3-9 入栈操作
注 意
在插入新结点时，需要注意的是插入结点的顺序不能颠倒。
将元素e入栈的算法实现如下：
（2）将栈顶元素出栈。出栈操作前，先判断栈是否为空，如果栈为空，则返回0表示出栈操作失败，否则，将栈顶元素出栈，并将栈顶元素值赋给e，最后释放结点空间，返回1表示出栈操作成功。出栈操作如图3-10所示。
图3-10 出栈操作
3、主要考查递归与非递归的转换。斐波那契数列的前N项非递归算法可通过迭代得到，递归算法可根据斐波那契数列的定义得到。
如果要打印出斐波那契数列的前40项，常规的迭代方法实现代码如下：
以上代码比较简单，不用过多解释，如果用递归实现，代码会更加简洁。
从结构上看，递归要比非递归代码逻辑上更清晰，但是想要真正搞明白需要好好思考一下。遇到这种情况，可以先动手在纸上画一画，模拟代码的执行过程，例如，当n=4时，代码执行过程如图3-11所示。
图3-11 斐波那契数列的执行过程
4、n的阶乘递归与非递归算法实现如下：
程序运行结果如图3-12所示。
图3-12 n的阶乘程序运行结果
5、组合数C（n，m）的递归算法是：
C(n,m)=C(n-1,m)+C(n-1,m-1)，当n>m、n≥0、m≥0时
已知条件是：当n≥0时，有C（n，0）=1，C（n，n）=1。
计算C（n，m）的值利用递归很容易实现，为了模拟递归的运算过程，可利用一个栈stack来实现。定义一个二维数组stack［MAXSIZE］［3］来模拟栈，其中stack［top］［1］用来存放当前层组合数的值，stack［top］［2］存放当前层n的值，stack［top］［3］存放当前层m的值，即表示C（n，m）的值存放在stack［top］［1］中。
假设要计算C（4，3）的值，首先初始化stack，将0、4、3分别入编号为1、2、3号栈，然后分以下3种情况讨论：
（1）若编号为0的栈顶元素值为0，需要对其分解，将（0，n-1，m）入栈，也就是计算C（n，m-1）的值。
（2）若编号为1的栈顶元素值大于0，且次栈顶编号为1的元素值为0，表示已得到C（n，m-1）的值，需要求C（n-1，m-1）部分，将（0，n-1，m-1）入栈。
（3）若编号为1的栈顶和次栈顶元素值都大于0，则退栈两次，计算新的编号为1的栈顶元素值，就是计算C（n，m）=C（n，m-1）+C（n-1，m-1）。
6、（1）Ack（2，1）的计算过程如下：
（2）Ack（m，n）的非递归算法实现如下：
7、分析：主要考查共享栈的算法设计。在使用顺序栈时，定义的空间过大，可能造成有些栈空闲空间并没有有效利用。为了使栈的空间能充分利用，可以让多个栈共享一个足够大的连续存储空间，通过移动栈顶指针，从而使多个栈空间互相补充，存储空间得到有效利用，这就是共享栈的设计思想。
最常见的是两个栈的共享。栈的共享原理是利用栈底固定，栈顶迎面增长的方式。可通过两个栈共享一个一维数组实现，两个栈的栈底设置在数组的两端，当有元素进栈时，栈顶位置从栈的两端迎面增长，当两个栈的栈顶相遇时，栈满。
用一维数组表示的共享栈如图3-13所示。
图3-13 共享栈
【存储结构】
其中，top［0］和top［1］分别是两个栈的栈顶指针。
其中，共享栈的基本运算实现在文件SSeqStack.h中，其代码如下：
