B

[解析] 连续执行3次元素进栈操作后，栈内的数据为5，2，4，此时执行退栈操作1次，栈内元素为5和2，栈顶读到x中应为2。

D

[解析] 此题可以用排除法来解决。由选项A、B、C所得出的栈序列分别为(1，2，4，3)、(3，2，4，1)、(1，3，2，4)，可以看出都是错误的。选项D得到的出栈序列为1，3，4，2。

D

[解析] i出栈时，1，2，…，i-l都在栈内，之后的过程中还可能有i之后的元素进栈，但究竟第j个出栈元素是哪个，不能确定。

D

[解析] 元素3第一个出栈时，元素1，2一定在栈内，下一个出栈的元素是2，不可能是1。当然还可以是元素2暂时不出栈，元素4，5，…进栈。

C

[解析] p₃=1，输入序列为p₁，p₂，1，p₄，…，因为p₃=1，所以p₃出栈前，p₁，p₂必在栈中。若p₁出栈，则p₂必先于p₁出栈，因此p₁不可能为2。

A

[解析] 对于选项A，n个元素进栈后，出栈顺序必然与进栈的顺序相反，因此选项A正确；对于选项B，如果某元素进栈后很快又出栈，则进栈和出栈操作可以多于n次；对于选项C，栈并未对进栈和出栈次序做限制，而仅仅对进栈和出栈的位置做了限制；对于选项D，栈顶指针属于栈结构的一个分量，不会由于栈的状态变化而消失。

B

[解析] 在元素进栈之前先判断栈是否已满，栈满再进栈就会发生上溢。出栈之前先判断栈是否为空，如果栈已空再出栈就会发生下溢。

C

[解析] 在栈顶插入元素即在链表首元结点前插入，必须首先让s后面链接上原栈顶top，再让栈顶指针指向新栈顶s，所以有s→link=top;top=s;。

C

[解析] 在不能附加其他任何数据成员的前提下，只能用牺牲一个队列元素的整除取余的方式来区分队空和队满的条件。因此，选项C正确。选项A是判断队列是否为空的条件，选项B和D则是干扰项。

A

[解析] 由队列的FIFO性质可知，出队序列为1，2，3，4。

D

[解析] 对于链式队列，一般插入元素仅仅需要修改尾指针，但向空队列插入新元素时，需要同时修改队头指针和队尾指针。所以本题选D。

B

[解析] 在链头删除元素，在链尾插入元素，因此需要队头指针和队尾指针。这种情况下使用非循环单链表比较方便。

A

[解析] 即使是双向链表，如果是非循环链表，只有队头指针也是不够的。

B

[解析] 通常用于输入或输出的缓冲区都是采用先进先出的队列。

B

[解析] 在递归程序时作为递归工作栈是栈的一个典型应用，用于开辟每一层递归程序调用时需要的局部变量空间、实际参数的拷贝空间和记录返回上一层调用的返回地址等。

B

[解析] 递归算法必须包括递归体和结束条件。结束条件是可以直接求解的，无需再递归处理；递归体在不能直接求解的情况下把问题通过递归调用化为更简单的子问题求解，每递归一层就向问题的最终解决推进一步。

C

[解析] 可以将二维数组视为一组行向量和列向量的纵横交织，每个元素既处于一个行向量中，又处于一个列向量中。因此，需要用两个下标i和j以确定该数组元素在数组中的位置。

A

[解析] 多维数组本质上是一维数组，是由一维数组实现的，是数组元素为一维数组的一维数组。

D

[解析] 本题属于计算存储地址的典型题目，假设求元素a的地址，首先按行存储，求a所在行之前的所有行中元素的总和sum1，然后求a所在行a之前所有元素的总和sum2，最后用首地址加上(sum1+sum2)×每个元素所占存储空间的大小即可。
   由以上分析可知：A[8][5]的地址=SA+(8×10+5)×3=SA+255。

B

[解析] 用S表示进栈操作，用X表示出栈操作，选项A、C和D的输出序列可以用操作序列SXSXSXSX、SSSSXXXX和SXSSXSXX来导出，且都是合法操作序列。只有选项B的输出序列找不到合法的操作序列。

C

[解析] 一个出栈元素是n，则1，2，3，…，n-1都在栈内，可知后续出栈的元素依次为n-1，n-2，…，则第i个出栈元素应为n-i+1。

B

[解析] 当p₃=3时，输入序列为p1，p₂，3，p₄，…因为输出的第三个元素是3，所以有多种可能：当p₁=1，p₂=2时，允许的进栈或出栈顺序是p₁进栈，p₁出栈，p₂进栈，p₂出栈；当p₁=2，p₂=1时，允许的进栈或出栈顺序是p₁进栈，p₂进栈，p₂出栈，p₁出栈；当p₁，p₂，3进栈不出，p₄=2，p₅=1时，允许的进栈或出栈顺序可以是p₄进栈，p₅进栈，p₅出栈，p₄出栈。因此可以断定p₁=1或p₁=2是可能的，但不是一定的。

A

[解析] 当p_n=1时，输入序列为p₁，p₂，p₃，p₄，…，p_n-1，1，因为输出序列为1，2，3，…，n，所以第一次输出l时p₁，p₂，p₃，p₄，…，p_n-1都应在栈内，这样可得p_n-1=2，p_n-2=3，…，p_n-i=i+1，…，p_i=n-i+1。

B

[解析] 根据题意，栈底应在下标n-1的位置上，因此进栈时栈顶指针应该先减1，向栈空间的底端延伸。

C

[解析] 初始时，两个栈的栈顶设置在栈空间的两端，元素进栈时，栈顶指针相向而行，当两个栈的栈顶在栈空间的某一位置相遇时，为栈满状态。

A

[解析] 出栈操作由两部分组成：取元素存储在其他空间和调整栈顶指针位置。为完成这两部分可以执行以下语句：
   x=top→data;//取元素存储在其他空间
   top=top→link;//调整栈顶指针位置

D

[解析] 随着队列中元素的进队出队的交替进行，对于rear与front两指针，其相对位置不定。当rear＜front时，Q.reai-Q.front+ maxSize正好是队列元素个数；当rear＞front时，可以用(Q.rear-Q.front+maxSize)%maxSize得到队列元素个数。

B

[解析] 当front==NULL或者rear==NULL时，链为空，则对应的链队也为空。

C

[解析] 对一个空队列，执行两次进队操作和两次出队操作后，显然栈变为空状态，此时执行判断队列是否为空的操作Q.isEmpty()，函数返回true。

C

[解析] 根据队列的FIFO性质，出队顺序与入队顺序一致，也就是说，与出栈顺序一致。如果用S表示进栈，用X表示出栈，按照题意，进栈和出栈序列见下表。

进栈与出栈情况

进栈序列

a

b

进出操作

S

S

X

S

S

X

X

S

S

X

X

X

S

X

栈的内容

a

ab

a

ac

acd

ac

a

ae

aef

ae

a

g

出栈序列

b

d

c

f

e

a

g

   由表可知，栈中最多时有3个元素，所以栈的容量最少为3。

A

[解析] 设双端队列的两端为e1和e2，e1端允许输入，e1和e2端都允许输出。若在e1端输出，相当于栈；若在e2端输出，相当于队列。
   对于选项A(4231)，要求先输出4，有一种进队方案：1_e12_e13_e14_e1，然后从e1端输出4，但由于2夹在1和3之间，下一个输出的不可能是2，所以选项A是不可能的输出序列。
   对于选项B(1324)，一种操作顺序是1_e1进1_e1出2_e1进3_e1进3_e1出2_e1出4_e1进4_e1出。
   对于选项C(3214)，一种操作顺序是1_e1进2_e1进3_e1进3_e1出2_e1出1_e1出4_e1进4_e1出。
   对于选项D(2341)，一种操作顺序是1_e1进2_e1进2_e1出3_e1进3_e1出4_e1进4_e1出1_e1出。

B

[解析] 设双端队列的两端为e1和e2，e2端允许输出，e1和e2两端都允许输入。若在e1端输入，相当于队列；若在e2端输入，相当于栈。
   对于选项A(dacb)，要求先输出d，必须abc都输入后再执行操作d_e2进d_e2出(相当于进栈出栈)，但下一个要输出a，就必须执行操作a_e1进b_e1进c_e1进，队列中是cba，再执行a_e2出，然而下一个不可能输出c，所以选项A是不可能的输出序列。
   对于选项B(cadb)，一种操作顺序是a_e1进b_e1进c_e2进c_e2出a_e2出d_e2进d_e2出b_e2出，是可能的输出序列。
   对于选项C(dbca)，相当于上一题中的A项(4231)，是不可能的输出序列。
   对于选项D(dbac)，与选项A类似，要求先输出d，必须先输入abc后再执行操作d_e2进d_e2出；若要求下一个输出b，应执行操作a_e1进b_e2进c_e1进，队列中是cab，输出b后，下一个输出的不可能是c，选项D是不可能的输出序列。

C

[解析] 根据题目中程序代码的递归框架可知，该程序把一个规模为n的问题转化为两个规模为n-1的同样问题外加一个常量复杂度的操作来求解，因此其递推关系为T(n)=2T(n-1)+O(1)，可近似为T(n)=2T(n-1)+1。

B

[解析] 此类型题目基础题部分已经讲过，A[6][2]的地址=200+6×20+2=322。

A

[解析] 此类型题目基础题部分已经讲过，A[6][2]的地址=200+2×10+6=226。

A

[解析] 第i行前面存有i行，元素个数为1+2+…+i=(i+1)×i/2，第i行中第i列前有i个元素，则A[i][i]在B中的存放位置为(i+1)×i/2+i=(i+3)×i/2。

B

[解析] 三对角线矩阵属于带状矩阵，如图所示。带状矩阵下标范围可以表示为i-1≤j≤i+1，因此本题选B。
   

两个栈可以模拟一个队列，但反之不可。
   原因如下：
   栈是一种先进后出的线性结构，可以使用一个栈把一个输入序列逆转，同样可以使用另一个栈把逆转后的序列再逆转回来，因此用两个具有先进后出特性的栈可以模拟一个先进先出的队列。反之，两个先进先出的队列无法模拟一个栈。

原顺序栈的结构体中是用静态数组来存放数据，现在题目需要动态创建数组，因此需要把静态数组改掉，代码如下：
   typedef struct
   {
   int *data;                  //指向动态数组的指针
   int top;                    //栈顶指针
   int maxSize;                //因data数组是动态变化的，所以将maxSize改为变量
   }SqStack;
   修改后的Push()函数代码如下：
   int Push(SqStack &st,int x)
   {
   if(st.top==st.maxSize-1) //栈满执行stackFull()
   {
   if(stackFull(st)==0)     //栈满，且stackFull()函数失败，返回0
   return 0;                //否则只执行stackFull()
   }
   ++(st.top);              //先移动指针，再进栈
   st.data[st.top]=x;
   return 1;
   }
   stackFull()函数代码如下：
   int StackFull(SqStack& st)
   {
   int *temp=(int*)malloc(2* st.maxSize * sizeof(int));
   //申请一个动态数组空间长度为2倍的maxSize，由temp指向其首地址
   if(temp==NULL)
   return 0;                //空间申请失败，返回0
   for(int i=0;i＜=st.top;++i)
   temp[i]=st.data[i];      //复制原栈中元素到新空间的前一半地址
   free(st.data);           //释放原栈元素空间
   st.data=temp;            //用data指针指向新空问首地址
   return 1;                //成功，返回1
   }

(1)结构定义。
   typedef struct        //双栈的结构定义
   {
   int top[2],bot[2];    //双栈的栈顶指针和栈底指针
   int *elem;            //栈数组
   int m;                //栈数组最大可容纳元素个数
   }DblStack;
   (2)初始化栈。
   void initStack(DblStack& S,int sz)
   {//初始化函数：建立一个最大尺寸为sz的空栈，若分配不成功则进行错误处理
   S.elem=(int*)malloc(sizeof(int)*sz);  //创建栈的数组空间
   if(S.elem==NULL){cout＜＜"memory assign fail"＜＜endl;exit(1);}
   S.m=sz;
   S.top[0]=S.bot[0]=-1;
   S.top[1]=S.bot[1]=sz;
   };
   (3)判断栈空。
   bool isEmpty(DblStack& S,int i)//判断栈i是否空
   {
   return S.top[i]==S.bot[i];
   }
   (4)判断栈满。
   bool isFull(DblStack& S)    //判断栈是否满
   {
   return S.top[0]+1==S.top[1];
   }
   (5)元素入栈。
   bool Push(DblStack& S,int x,int i)
   {//进栈，如果isFull(S)，则报错；否则把x插入到栈i的栈顶
   if(isFull(S))
   return false;            //栈满则返回false
   if(i==0)
   S.elem[++S.top[0]]=x;    //栈0：栈顶指针先加，再进栈
   else
   S.elem[--S.top[1]]=x;    //栈1：栈顶指针先减，再进栈
   return true;
   }
   (6)元素出栈。
   bool Pop(nblStack& S,int& x,int i)
   {//如果栈空，则不执行退栈，返回false；否则退掉栈i栈顶元素到x，返回true
   if(isEmpty(S,i))         //判断栈i是否空，若栈空则返回false
   return false;
   if(i==0)
   x=S.elem[S.top[0]--；    //栈0：先出栈，栈顶指针再减
   else
   x=S.elem[S.top[1]++];    //栈1：先出栈，栈顶指针再加
   return true;
   }
   (7)取栈顶元素。
   bool getTop(DblStack& S,int& x,int i)
   (//若栈不空，则函数通过x返回该栈栈顶元素的内容
   if(isEmpty(S,i))
   return false;          //判断栈i是否空，若栈空则返回false
   x=S.elem[S.top[i]];    //栈顶元素的值通过x返回
   return true;
   }
   (8)清空栈。
   void makeEmpty(DblStack& S,int i)
   {
   if(i==0)
   S.top[0]=S.bot[0]=-1;
   else
   S.top[1]=S.bot[1]=S.m;
   }

设该循环队列的结构定义如下：
   #define maxSize 100
   typedef struct
   {
                               //循环队列的结构定义
   int elem[maxSize]；         //队列存储数组
   int rear,length;            //队列的队尾指针和队列长度
   }SqQueue;
   /*rear是实际的队尾位置，其队空条件和队满条件分别为Q-length==0和
   Q.length==maxSize。*/
   //该队列的插入和删除函数代码如下：
   int enQueue(SqQueue& Q,int x)
   {
                               //元素x存放到队列尾部。若进队成功，函数返回true，否则返回false
   if(Q.length==maxSize)        
   return 0;                   //判断队列是否已满，满则出错
   Q.rear=(Q.rear+1)%maxSize; //队尾指针进
   Q.elem[Q.rear]=x;           //进队列
   ++Q.length;                 //队列长度加
   return 1;
   }
   int deQueue(SqQueue& Q,int& x)
   {//从队列队头退出元素，由x返回。若退队成功，函数返回true，否则返回false
   if(Q.length==0)
   return 0;                   //判断队列是否为空，空则出错
   --(Q.length);               //队列长度减
   x=Q.elem[(Q.rear-Q.length+1+maxSize)%maxSize];
                               //返回原队头元素值
   return 1;
   }

本题采用牺牲一个单元以区分队空还是队满的循环队列结构。
   (1)元素数组可以动态增长的循环队列结构定义如下：
   typedef struct
   {
                     //循环队列的结构定义
   int *data;        //因为数组长度会变，所以要用指针，以便动态申请
   int front,rear;   //队列的队尾指针和队列长度
   int maxSize;     //因为动态申请，所以将数组长度由常量改为变量
   }SqQueue;
   (2)这里假定进队列的方式是先按rear指示的位置加元素，然后rear加1，数组大小为maxSize。
   实现代码如下：
   int enQueue(SqQueue& Q,int x)
   {
   if((Q.rear-Q.front+Q.maxSize)%Q.maxSize==Q.maxSize)
   {  //队列已满
   int newSize=2*Q.maxSize;    //创建大一倍的数组
   int *newArray=(int*)malloc(newSize *sizeof(int));
   if(newArray==NULL)
   return 0;
   int newRear=Q.front,newFront=Q.front;
   //向新数组传递数据
   while(Q.rear!=Q.front)
   {  //老队列不空
   newArray[newRear ]=Q.data[Q.front];
   Q.front=(Q.front+1) % Q.maxSize;
   newRear=(newRear+1) % newSize;
   }
   free(Q.data);
   Q.data=newArray;
   Q.rear=newRear;
   Q.front=newFront;
   Q.maxSize=newSize;
   }
   Q.data[Q.rear]=x;
   Q.rear=(Q.rear+1)%Q.maxSize;
   return 1;
   }
   (3)设front指示实际队尾的位置。实现代码如下：
   int deQueue(SqQueue& Q,int& x)
   {
   int newSize=Q.maxSize/2;
   int *newArray=(int*)malloc(newSize * sizeof(int));
   if(newArray==NULL)
   return 0;
   int newRear=Q.front;
   int newFront=Q.front;
   while(Q.front !=Q.rear)
   {
   newArray[newRear]=Q.data[Q.front];
   Q.front=(Q.front+1)%Q.maxSize;
   newRear=(newRear+1)% newSize;
   free(Q.data);
   Q.data=newArray;
   Q.rear=newRear;
   Q.front=newFront;
   Q.maxSize=newSize;
   if(Q.rear==Q.front)
   return 0;
   x=Q.data[Q.rear];
   Q.front=(Q.front+1)%Q.maxSize;
   return 1;
   }

按对称性考虑，上三角部分按列压缩存放于一个一维数组B中，共有n(n+1)/2个元素，B[k]与A[i][j]的关系如下：
   
   当i≤j时，max(i,j)=j,min(i,j)=i，此时：
   k=(max(i,j)+1)max(i,j)/2+min(i,j)
   当i＞j时，max(i,j)=i,min(i,j)=j，此时：
   k=(max(i,j)+1)max(i,j)/2+min(i,j)
   综上所述，k=(max(i,j)+1)max(i,j)/2+min(i,j)。

中缀表达式：a+b*(c-d)+e/f#转换为后缀表达式时的处理过程及栈的相应变化见下表。isp是栈内优先(in stackpriority)数，icp是栈外优先(in coming priority)数。左括号“(”的栈外优先数最高，它一来到立即进栈，但当它进入栈中后，其栈内优先数变得极低，以便括号内的其他操作符进栈。其他操作符进入栈中后优先数都升1，体现在中缀表达式中相同优先级的操作符自左向右计算的要求，让位于栈顶的操作符先退栈并输出。操作符优先数相等的情况只出现在括号配对或栈底的“#”号与输入流最后的“#”号配对时。前者将连续退出位于栈顶的操作符，直到遇到“)”为止。然后将“)”退栈以对消括号，后者将结束算法。

处理过程及栈的相应变化
步序	扫描项	类型项	动作	栈的变化	输出
0			'#'进栈，读下一符号	#
1	a	操作数	直接输出，读下一符号	#	a
2	+	操作符	isp('#')＜lcp('+')，进栈，读下一符号	#+
3	b	操作数	直接输出，读下一符号	#+	b
4	*	操作符	isp('+')＜lcp('*')，进栈，读下一符号	#+*
5	(	操作符	isp('+')＜lcp('(')，进栈，读下一符号	#+*(
6	c	操作数	直接输出，读下一符号	#+'(	c
7	-	操作符	isp('(')＜lcp('-')，进栈，读下一符号	#+*(-
8	d	操作数	直接输出，读下一符号	#+*(-	d
9	)	操作符	isp('-')＞lcp(')')，退栈，输出	#+*(	-
10			isp('(')==lcp(')')，退栈，读下一符号	#+*
11	+	操作符	isp('+')＞lcp('+')，退栈，输出	#+	*
12			isp('+')＞lcp('+')，退栈，输出	#	+
13			isp('#')＜lcp('+')，进栈，读下一符号	#+
14	e	操作数	直接输出，读下一符号	#+	e
15	/	操作符	isp('+')＜lcp('/')，进栈，读下一符号	#+/
16	f	操作数	直接输出，读下一符号	#+/	f
17	#	操作符	isp('/')＞lcp('#')，退栈，输出	#+	/
18			jsp('+')＞lcp('#')，退栈，输出	#	+
19			isp('#')==lcp('#')，退栈，结束

可以利用栈解决数制转换问题。例如，49₁₀=1·2⁵+1·2⁴+1·2⁰=110001₂，其转换规则是：
   
   式中，b_i表示二进制数的第i位上的数字。这样，十进制数N可以用长度为位的二
   进制数表示为。若令，则有
   N=b_j2^j+b_j-12^j-1+…+b₁2¹+b₀2⁰
   =(b_j2^j-1+b_j-12^j-2+…+b₁)×2+b₀
   =(N/2)×2+N%2('/'表示整除运算)
   因此，可以先通过N%2求出b₀，然后令N=N/2，再对新的N做除2求模运算可求出b₁……如此重复直到某个N等于零结束。这个计算过程是从低位到高位逐个进行的，但输出过程是从高位到低位逐个打印的，为此需要利用栈来实现。代码如下：
   int BaseTrans(int N)
   {
   int i,result=0;
   int stack[maxSize],top=-1;
   //定义并初始化栈，其中maxSize是已定义的常量，其大小足够处理本题中数据
   while(N !=0)
   {
   i = N%2;
   N = N/2;
   stack[++top]=i;
   }
   while(top!=-1)
   {
   i=stack[top];
   --top;
   result=result * 10+i;
   }
   return result;
   }

在算法中，扫描程序中的每一个字符，当扫描到每个花括号、方括号、圆左括号时，令其进栈；当扫描到花括号、方括号、圆右括号时，检查栈顶是否为相应的左括号，若是则进行退栈处理；若不是则表明出现了语法错误，应返回0。当扫描到程序文件结尾时，若栈为空则表明没有发现括号配对错误，应返回1；否则表明栈中还有未配对的括号，应返回0。另外，对于一对单引号或双引号内的字符不进行括号配对检查。
   由此可以写出以下代码：
   int BracketsCheck(char f[])
   {
   //对由字符数组f所存字符串中的文本进行括号配对检查
   stack S;char ch;    //定义一个栈
   char *p=f;
   while(*p !='\0')    //顺序扫描串中的每一个字符
   {
   if(*p==39)          //单引号内字符不参与配对比较，过滤掉其中字符
   while(*p !='\0' && *p !=39)      //39为单引号的ASCII值
   ++p;
   else if(*p !='\0' && *p==34)    //双引号内字符不参与配对比较
   while(*p !='\0' && *p !=34) //34为双引号的ASCII值
   ++p;
   if(*p !'\0')
   {
   switch(*p)
   {
   case '{':
   case '[':
   case '(': Push(S,*p);
   //出现左括号：'(','['和'('进栈
   break;
   case ')': getTop(S,ch);
   if(ch=='{')                //栈顶的左花括号出栈
   Pop(S,ch);
   else
   return 0;
   break;
   case ']': getTop(S,ch);
   if(ch=='[')                //栈顶的左方括号出栈
   Pop(S,ch);
   else
   return 0;
   break;
   case ')': getTop(S,ch);
   if(ch=='(')               //栈顶的左圆括号出栈
   Pop(S,ch);
   else
   return 0;
   }
   ++p;
   }
   if(IsEmpty(S))
   return 1;
   else
   return 0;
   }
   }

可用递归方式计算。设当n=0时，计算时间复杂度为常数T(0)=d；当n＞0时，按T(n)=T(n-1)+c(c为常数)，则有
   T(n)=T(n-1)+c
       =T(n-2)+2×c
       =T(n-3)+3×c
       
       =T(1)+(n-1)×c
       =T(0)+n×c
       =n×c+d

描述汉诺塔问题的递归算法代码如下：
   void Hanoi(int x,int y,int z,int n)
   {/*代表将n个盘子分别从x移到z上，y做辅助柱。*/
   if(n==1)
   move(x,z);            //n为1可以直接解决
   else
   {
   Hanoi(x,z,y,n-1);     //分别处理n-1个盘，从x移动到y上，z做辅助
   move(x,z);            //直接移动x上的一个盘到z上
   Hanoi(y,x,z,n-1);     //分别处理n-1个盘，从y移动到z上，x做辅助
   }
   }
   设move()函数执行的移盘次数为常数1，则汉诺塔问题总的运算次数代码如下：
   T(1)=1=2¹-1；
   T(2)=2×T(1)+1=3=2²-1；
   T(3)=2×T(2)+1=2*3+1=7=2³-1；
   
   T(n)=2×T(n-1)+1=2ⁿ-1