分析：该题目主要考查栈在递归中的应用。对于尾递归可以将其转化成递推，不需栈。所以这种说法是正确的。
尾递归是指一个递归函数的递归调用语句是递归函数的最后一句可执行语句。 例如下面是一个输出数组元素的递归函数。
void RPrintArray(int list[],int n) {
if(n>=0)
{
printf(“%d”,list[n]); RPrintArray(list,--n);
} }
此程序是尾递归程序，消除尾递归很简单，只需首先计算新的n值，n=n-1，然后程序转到函数的开始处执行就行了，可以使用while语句来实现。
相应非递归函数如下：
void PrintArray(int list[],int n) {
while (n>=0)
{
printf(“%d”,list[n]); --n; } }
2．栈和队列都是限制存取点的线性结构。 正确
分析：该题目主要考查栈和队列的定义。它们都只能在一端或两端存取数据的线性结构。见选择题第1题解答。
3．入栈操作、出栈操作算法的时间复杂性均为O(n)。 错误
分析：该题目主要考查栈的操作算法。入栈与出栈操作都在确定的栈顶位置进行，算法的时间复杂性均为O(1)。所以这种说法是错误的。
4．队列逻辑上是一个下端和上端既能增加又能减少的线性表。 错误 分析：该题目主要考查队列的逻辑结构和操作。队列是上端只能进行入队操作(即增加操作)，下端只能进行出队操作(即减少操作)。
5．用I代表入栈操作，O代表出栈操作，栈的初始状态和栈的最终状态都为空，则使用栈的入栈和出栈可能出现的操纵序列为IOIOIOOI。 错误
分析：该题目主要考查栈的操作和“溢出”问题。在栈的操作中，保证出栈前提是栈中有元素，否则会造成栈的下溢，IOIOIOOI会出现下溢。 6．任何一个递归过程都可以转换为非递归过程。 正确 分析：该题目主要考查栈在递归过程非递归化中的应用。任何一个递归过程都可以按照一定的步骤机械地转换为非递归过程。由于栈的后进先出特性吻合递归算法的执行过程，因而可
以用非递归算法替代递归算法。递归过程转换为非递归过程的实质就是将递归中隐含的栈机制转化为由用户直接控制的栈，利用堆栈保存参数。
3.2.3 填空题
1．已知一个栈ｓ的输入序列为abcd，判断下面两个序列能否通过栈的Push_Stack和Pop_Stack操作输出：
(1)dbca (1) (2)cbda (2) 答案：(1)不能 (2)能
分析：该题目主要考查栈的操作。(1)不能，因为弹出d时，abc均已依次压入栈，下一个弹出的元素只能是c而不是b。(2)能，Push_Stack (s,a)，Push_Stack (s,b)，Push_Stack (s,c)，Pop_Stack (s)，Pop_Stack (s)，Push_Stack (s,d), Pop_Stack (s), Pop_Stack (s)。 2．对循环队列Q(设循环队列空间大小为MAXSIZE)，如何修改队头指针? (1) ；
如何修改队尾指针? (2)
答案：(1)front=(front+1)% MAXSIZE (2)rear=(rear+1)% MAXSIZE
分析：该题目主要考查循环队列的操作。具体解答请参见选择题第11和12题。
3．设长度为n的链队列用单循环链表表示，若只设头指针，则入队列出队列操作的时间分别为 (1) 和 (2) ；若只设尾指针，则入队列出队列操作的时间分别为 (3) 和 (4) 。
答案：(1)O(n) (2)O(n) (3)O(1) (4)O(1)
分析：该题目主要考查链队列和单循环链表的综合知识。当只设头指针时(如图3.3(a)所示)，入队相当于在an结点之后执行结点插入操作，根据链表的插入操作特点可知，插入操作前必须知道结点a1和an的地址，获取结点an的地址的时间复杂度为O(n)；出队则相当于删除结点a1的操作，因此必须获取结点an的地址，同样其时间复杂度为O(n)。若设置尾指针(如图3.3(b)，入队相当于在结点a1之前和an之后执行结点插入操作，通过rear和rear->next可以获得结点an和a1的地址，则其时间复杂度为O(1)；出队则相当于删除结点a1的操作，同样其时间复杂度为O(1)。
head
a1 a2 ??. an
(a)
a1 a2 ??. an rear
(b)
图3.3单循环链表表示的链队列示意图
4．对于循环向量中的循环队列，写出求队列中元素个数的公式___________。 答案： (rear-front＋MAXSIZE)% MAXSIZE，其中MAXSIZE表示队列的存储空间。 分析：该题目主要考查循环队列的存储结构特点。
5．向顺序栈插入新元素分为三步：第一步，进行 (1) 判断，判断条件是 (2) ；第二步是修改 (3) ；第三步把新元素赋给 (4) 。同样从顺序堆栈删除元素分为三步；第一步，进行 (5) 判断，判断条件是 (6) ；第二步是把 (7) 值返回；第三步 (8) 。
答案：(1)栈是否满(2)s->top= MAXSIZE -1(3)栈顶指针(top++)(4)栈顶对应的数组元
素(5)栈是否空(6)s—>top=-1(7)栈顶元素(8)修改栈顶指针(top--)
分析：该题目是考虑栈的运算规则及其入出栈的实现步骤。入栈时一般考虑判断栈满否，条件是是否超出最大空间。如果没有超出应该修改栈顶指针，然后将元素压入堆栈。出栈时，应首先考虑堆栈是否空。如果不空，先保留栈顶元素，然后修改栈顶指针。
6．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈。对于前者，进入栈的元素为表达式中的 (1) ，而对于后者，进入栈的元素为 (2) 。中缀表达式(a+b)/c-(f-d/e)所对应的后缀表达式是 (3) 。 答案：(1)运算符 (2)操作数 (3)ab+c/fde/--
分析：该题目主要考查栈的应用。中缀表达式就是将运算符写于参与运算的操作数的中间，操作数依原序排列。后缀表达式就是将运算符列于参与运算的操作数之后，操作数的排列依原序。因此计算后缀表达式值的过程为：从左向右扫描后缀表达式，遇到操作数就进栈，遇到运算符就从栈中弹出两个操作数，执行该运算符所规定的运算，并将所得结果进栈。如此下去，直到表达式结束。所以对于计算后缀表达式，进栈的元素为操作数。
7．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，e，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_______。 答案：bceda
分析：该题目主要考查入栈和出栈操作。入栈和出栈操作只能在栈顶位置进行。根据操作序列，首先a，b进栈，然后b出栈；接着c进栈、c出栈；d、e相继进栈，栈顶元素为e，最后e、d、a相继出栈。这样，得到出栈序列为bceda。
3.2.4 应用题
1．将整数1、2、3、4依次入栈或出栈，请回答下述问题： (1)当入、出栈次序为Push_Stack(S，1)、Pop_Stack(S)、Push_Stack(S，2)、Push_Stack(S，x3)、Pop_Stack(S)、Push_Stack(S，4)、Pop_Stack(S)，出栈的数字序列为何？ (2)能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。
(3)设有n个数据元素的序列顺序进栈，试给出可能输出序列的个数和不可能输出序列的个数。当n=4(1、2、3、4)有24种排列，哪些序列是可以通过相应的入出栈操作得到的。 分析与解答：该题目主要考查栈的性质、结构和操作。
(1) 出栈序列为l、3、4。
(2) 序列1、4、2、3不可能得到。因为4和2之间隔了3，当4出栈后，栈顶元素是3，而2在3的下面。序列1、4、3、2可以得到：Push_Stack(S，1)、Pop_Stack(S)、Push_Stack(S，2)、Push_Stack(S，3)、Push_Stack(S，4)、Pop_Stack(S)、Pop_Stack(S)、Pop_Stack(S)。
(3) 设有n个数据元素的序列(假设这个序列为1，2，3，4，5??n)顺序进栈，那么输出序列个数f(n)可以递推求出：为讨论方便, 设n=0, f(0)=1，当，
n=1：显然f(1)=1 n=2：容易得知f(2)=2
n=3：1最后出栈的序列有f(2)种，2最后出栈的序列有f(1)* f(1)种，3最后出栈的序列有f(2)种，所以 f(3)=2* f(2)+f(1)*f(1)=5
n=4：1最后出栈的序列有f(3)种，2 最后出栈的序列有f(1)* f(2)种，3最后出栈的序列有f(2)*f(1)种，4最后出栈的序列有f(3)种，所以f(4)= 2*f(3)+ f(1)* f(2)+ f(2)* f(1)=14
可以看出i(i=1,2,3,??n)最后出栈的序列有f(i-1)*f(n-i)
所以f(n)=f(0)*f(n-1)+ f(1)*f(n-2)+f(2)*f(n-3)+f(3)*f(n-4)+?? + f(n-1)*f(0)，
用数学方法可得到
f(n)= Cn??2n?! 11?C2n??nn?1n?1n!?2n?n?!对有n个数据元素的序列，全部可能的排列个数为：Pn=n!
所以，不可能输出序列的个数为：Pn-Cn。 因此4个元素的出栈序列数为： C4?18！??14 4?14!?4!这14种出栈序列如下：
1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321
Cn??2n?! 1?n?1?n!?22．试说明下述运算的结果
(1) Pop_Stack(Push_Stack(S，A))； (2) Push_Stack(S，Pop_Stack(S))；
(3) Push_Stack(S，Pop_Stack(Push_Stack(S，B))) 分析与解答：该题目主要考查栈的操作。
(1) 首先要实现运算Push_Stack(S，A)，其结果是将元素A压入栈S中。若栈S满，则出现上溢现象的处理；否则把元素A压入栈顶，且元素个数加1。然后作Pop_Stack(S)运算， 将栈顶元素弹出，且元素个数减1。
(2) 首先作Pop_Stack(S)运算。若栈A为空，则作下溢处理；否则弹出栈顶元素。然后再进行压入运算，将刚才弹出的元素压入栈S中。
(3) 这种复合运算复杂一些，在(1)、(2)的基础上可知，这种运算的结果使栈S增加了一个栈顶元素B。
3．何谓队列的上溢现象，一般有几种解决方法，试简述之。 分析与解答：该题目主要考查队列的存储结构。
在队列的顺序存储结构中，设队列指针为front，队尾指针为rear，队列的容量(即存储的空间大小)为MAXSIZE。当有元素要加入队列(即入队)时，若rear==MAXSIZE-1，则队列已满，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。
一般地，要解决队列的上溢现象可有以下几种方法：
(1) 可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，
浪费存储空间，一般不采用这种方法。
(2) 采用移动元素的方法，每当有一个新元素入队，就将队列中已有的元素向对头移
动一个位置，假定空余空间足够。每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。
(3) 采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，利用一维
数组顺序存储并用取模运算实现。
4．设栈S={1,2,3,4,5,6,7},其中7为栈顶元素。请写出调用 algo(&S)后栈S的状态。
void algo(PseqStack S) { int x;
PseqQueue Q； PseqStack T；
Q=Init_SeqQueue( )； T=Init_SeqStack( )； while(!Empty_SeqStack(S))
{ Pop_ SeqStack(S,&x);
if (x/2!=0) Push_SeqStack(T，x)；
else En_SeqQueue(Q，x)； }
while(!Empty_SeqQueue(Q)) { Out_ SeqQueue(Q,&x); Push_SeqStack(S，x)； }
while(!Empty_SeqStack(T)) { Pop_ SeqStack(T,&x); Push_SeqStack(S，x)； } }
分析与解答：本函数的功能是将顺序栈S中递增有序的整数中的所有偶数调整到所有奇数之前，并且要求偶数按递减序排列，奇数按递增序排列。
算法首先设置并初始化中间栈T和中间队列Q，然后将S栈中的整数出栈，若整数为奇数，入栈T,若为偶数，入队列Q。这样S=Φ,T={7,5,3,1},其中1为栈顶元素,Q={6,4,2},其中6为队头元素。然后，将Q中整数出队列并入栈S, 这样S={6,4,2},其中2为栈顶元素,再将T中元素出栈，并入栈S, 这样S={6,4,2,1,3,5,7},其中7为栈顶元素。
最后S栈的状态如图3.4所示。
top
1 6 2 4 3 2 4 1 5 3 6 5 7 7 8 9 10 图3.4 调用algo(&S)后栈S的状态
5．假设两个队列共享一个循环向量空间(如图3.5所示)，其类型Queue2定义如下：
rear[1] front[1] …
typedef struct{
DateType data[MAXSIZE]; int front[2],rear[2]; } Queue2;
front[0] … rear[0] 图3.5双循环队列示意图 对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。
int EnQueue (Queue2 *Q, int i, DateType x)
{ /*若第i个队列不满，则元素x入队列，并返回1；否则返回0*/