(2) sum=8,当x为全局变量时，在程序的整个执行期间，x只占一个存储单元，先后读入的4个数(4,9,6,2),仅最后一个起作用。当递归调用结束，逐层返回时sum:=sum(n-1)+x表达式中，x就是2，所以结果为sum=8。
22、设操作数栈是opnd，操作符栈是optr，对算术表达式A-B*C/D-E↑F求值，过程如下：
步骤 初始 1 2 3 4 5 6 7 8 A A AB AB ABC AT(T=B*C) ATD AT(T=T/D) T(T=A-T) opnd栈 optr栈 # # # - # - # - * # - * # - / # - / # - # - A-B*C/D-E↑F# A-B*C/D-E↑F# -B*C/D-E↑F# B*C/D-E↑F# *C/D-E↑F# C/D-E↑F# /D-E↑F# D-E↑F# -E↑F# PUSH(OPTR,’#’) PUSH(OPND,A) PUSH(OPTR,’-’) PUSH(OPND,B) PUSH(OPTR,’*’) PUSH(OPND,C) PUSH(OPND,POP(OPND)*POP(OPND)) PUSH(OPTR,’/’) PUSH(OPND,D) x=POP(OPND);y=POP(OPND) PUSH(OPND,y/x); x=POP(OPND);y=POP(OPND); PUSH(OPND,y-x) PUSH(OPTR,’-’) 9 10 11 12 23、 步骤 初始 1 2 3 4 5 栈S1 A A AB AB ABC 栈S2 ? ? ?- ?- ?-* ?-* 输入的算术表达式（按字符读入） A-B*C/D+E/F? A-B*C/D+E/F? -B*C/D+E/F? B*C/D+E/F? *C/D+E/F? C/D+E/F? TE TE TEF TE TS(S=E↑F) R(R=T-S) # - # -↑ # -↑ #- # E↑F# ↑F# F# # PUSH(OPND,E) PUSH(OPTR, ‘↑’) PUSH(OPND,F) X=POP(OPND) Y=POP(OPND) POP(OPTR) PUSH(OPND,y↑x) x=POP(OPND) y=POP(OPND) POP(OPTR) PUSH(OPND,y-x) 输入字符 主要操作 6 7 8 9 10 11 12 AT1（注：T1=B*C） AT1D T3 （注：T3=A-T2） T3E T3E T3EF ?-/ ?-/ ?+ ?+ ?+/ ?+/ /D+E/F? D+E/F? +E/F? E/F? /F? F? ? AT2（注：T2=T1/D） ?- T3T4（注：T4=E/F） ?+ T5（注：T5= T3+ T4） ? 24、XSXXXSSSXXSXXSXXSSSS
25、S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。
26、设栈S1和栈S2共享向量V[1..m]，初始时，栈S1的栈顶指针top[0]=0，栈S2的栈顶指针top[1]=m+1，当top[0]=0为左栈空，top[1]=m+1为右栈空；当top[0]=0并且top[1]=m+1时为全栈空。当top[1]-top[0]=1时为栈满。 27、（1）每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。
（2）多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个栈满时要向左、右栈查询有无空闲单元。如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。
（3）多个链栈一般不考虑栈的溢出（仅受用户内存空间限制），缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。 28、设top1和top2分别为栈1和2的栈顶指针 （1）入栈主要语句
if(top2-top1==1) {printf(“栈满\\n”); exit(0);}
case1:top1++；SPACE[top1]=x; //设x为入栈元素。 case2:top2--；SPACE[top2]=x; 出栈主要语句
case1：if（top1==-1） {printf（“栈空\\n”）；exit（0）；} top1--；return（SPACE[top1+1]）； //返回出栈元素。 case2：if（top2==N）{printf（“栈空\\n”）；exit（0）；}
top2++；return（SPACE[top2-1]）； //返回出栈元素。 （2）栈满条件：top2-top1=1
栈空条件：top1=-1并且top2=N //top1=-1为左栈空，top2=N为右栈空
29、设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，
m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。 30、见上题29的解答。 31、参见上面29题。 32、typedef struct node
{elemtype elemcq[m]; //m为队列最大可能的容量。 int front ,rear; //front和rear分别为队头和队尾指针。 }cqnode; cqnode cq; (1) 初始状态 cq.front=cq.rear=0; (2) 队列空 cq.front==cq.rear; (3) 队列满
(cq.rear+1)%m==cq.front;
33、栈的特点是后进先出，队列的特点是先进先出。初始时设栈s1和栈s2均为空。
（1）用栈s1和s2模拟一个队列的输入：设s1和s2容量相等。分以下三种情况讨论：若s1未满，则元素入s1栈；若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；若s1满，s2不空（已有出队列元素），则不能入队。 （2）用栈s1和s2模拟队列出队（删除）：若栈s2不空，退栈，即是队列的出队；若s2为空且s1不空，则将s1栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。若栈s1为空并且s2也为空，队列空，不能出队。
（3）判队空若栈s1为空并且s2也为空，才是队列空。
讨论：s1和s2容量之和是队列的最大容量。其操作是，s1栈满后，全部退栈并压栈入s2（设s1和s2容量相等）。再入栈s1直至s1满。这相当队列元素“入队”完毕。出队时，s2退栈完毕后，s1栈中元素依次退栈到s2，s2退栈完毕，相当于队列中全部元素出队。 在栈s2不空情况下，若要求入队操作，只要s1不满，就可压入s1中。若s1满和s2不空状态下要求队列的入队时，按出错处理。
34、（1）队空s.front=s.rear； //设s是sequeuetp类型变量 （2）队满：（s.rear+1）MOD MAXSIZE=s.front //数组下标为0.. MAXSIZE-1 具体参见本章应用题第29题 35、typedef struct {elemtp q[m];
int front,count; //front是队首指针，count是队列中元素个数。 }cqnode; //定义类型标识符。
(1)判空：int Empty(cqnode cq) //cq是cqnode类型的变量 {if(cq.count==0) return(1)；else return(0); //空队列} 入队: int EnQueue(cqnode cq，elemtp x) {if(count==m){printf(“队满\\n”)；exit(0); } cq.q[(cq.front+count)%m]=x; //x入队
count++; return(1); //队列中元素个数增加1,入队成功。 }
出队: int DelQueue(cqnode cq)
{if (count==0){printf(“队空\\n”)；return(0);} printf(“出队元素”，cq.q[cq.front]);
x=cq.q[cq.front];
cq.front=(cq.front+1)%m; //计算新的队头指针。 return(x) }
(2) 队列中能容纳的元素的个数为m。队头指针front指向队头元素。
36、循环队列中元素个数为（REAR-FRONT+N）%N。其中FRONT是队首指针，指向队首元素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。
37、循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队列的满与空问题。例如：在队列长10的循环队列中，若假定队头指针front指向队头元素的前一位置，而队尾指针指向队尾元素，则front=3，rear=7的情况下，连续出队4个元素，则front==rear为队空；如果连续入队6个元素，则front==rear为队满。如何判断这种情况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。即假设front==rear为队空，而（rear+1）%表长==front为队满，或通过设标记tag。若tag=0，front==rear则为队空；若tag=1，因入队而使得front==rear，则为队满。
本题中队列尾指针rear，指向队尾元素的下一位置,listarray[rear]表示下一个入队的元素。在这种情况下，我们可规定，队头指针front指向队首元素。当front==rear时为队空，当（rear+1）%n=front时为队满。出队操作（在队列不空情况下）队头指针是front=（front+1）%n， 38、既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。
39、（1）4132 （2）4213 （3）4231 40、（1）队空的初始条件：f=r=0；
（2）执行操作A后，r=3；// A表示三次入队操作 执行操作D1后，f=1；//D1表示一次出队操作 执行操作A5后，r=0； 执行操作D2后，f=3； 执行操作A1后，r=1； 执行操作D2后，f=5；
执行操作A4后，按溢出处理。因为执行A3后，r=4，这时队满，若再执行A操作，则出错。
41．一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。
五、算法设计题
1、[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。
#define maxsize 两栈共享顺序存储空间所能达到的最多元素数 #define elemtp int //假设元素类型为整型 typedef struct
{elemtp stack[maxsize]; //栈空间
int top[2]; //top为两个栈顶指针
}stk;
stk s; //s是如上定义的结构类型变量，为全局变量。 (1)入栈操作：
3
3
int push(int i,int x)
//入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。入栈成功返回1，否则返回0。
{if(i<0||i>1){printf(“栈号输入不对”);exit(0);}
if(s.top[1]-s.top[0]==1) {printf(“栈已满\\n”);return(0);} switch(i)
{case 0: s.stack[++s.top[0]]=x; return(1); break; case 1: s.stack[--s.top[1]]=x; return(1); } }//push （2）退栈操作 elemtp pop(int i)
//退栈算法。i代表栈号，i=0时为s1栈，i=1时为s2栈。退栈成功返回退栈元素，否则返回-1。
{if(i<0 || i>1){printf(“栈号输入错误\\n”)；exit(0);} switch(i)
{case 0: if(s.top[0]==-1) {printf(“栈空\\n”)；return（-1）；} else return(s.stack[s.top[0]--]);
case 1: if(s.top[1]==maxsize {printf(“栈空\\n”); return(-1);} else return(s.stack[s.top[1]++]); }
}//算法结束
[算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图略，s1栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。 2、#define maxsize 栈空间容量 void InOutS(int s[maxsize])
//s是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1时入栈。
if(top==maxsize-1){printf(“栈满\\n”);exit(0);}else s[++top]=x; //x入栈。 else //读入的整数等于-1时退栈。
{if(top==0){printf(“栈空\\n”);exit(0);} else printf(“出栈元素是%d\\n”,s[top--])；}} }//算法结束。
3、[题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。
int EXYX(char E[],int n)
//E[]是有n字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆括号是否匹配。
{char s[30]; //s是一维数组，容量足够大，用作存放括号的栈。 int top=0; //top用作栈顶指针。