数据结构考研试题精选及答案第三章栈和队列答案

《数据结构考研试题精选及答案第三章栈和队列答案》由会员分享，可在线阅读，更多相关《数据结构考研试题精选及答案第三章栈和队列答案（20页珍藏版）》请在装配图网上搜索。

1、第三章 栈和队列答案一、选择题 1.B2.1B2.2A2.3B2.4D3.B4.D5.D6.C7.D8.B9.D10.D11.D12.C13.B14.C15.B16.D17.B18.B19.B20.D21.D22.D23.D24.C25.A26.A27.D28.B29.BD30.C31.B32.C33.1B33.2A33.3C33.4C33.5F34.C35.C36.A37.AD二、判断题1.2.3. 4. 5.6.7.8. 9. 10.11. 12.13. 14.15. 16.17.18.19.20. 部分答案解释如下。1、 尾递归的消除就不需用栈2、 这个数是前序序列为1,2,3,n，所能

2、得到的不相似的二叉树的数目。三、填空题 1、操作受限（或限定仅在表尾进行插入和删除操作） 后进先出 2、栈 3、3 1 2 4、23 100CH 5、0 n+1 top1+1=top2 6、两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）。7、(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1）8、链式存储结构 9、SSSS 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；

3、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）

4、ai或a1 （2）ai （3）pop（s）或s1； 25、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b） 26、（1）T0（2）i0（4）topn（5）top+1（6）true（7）i-1（8）top-1（9）T+wi（10）false四、应用题 1、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。2、队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称

5、先进先出（FIFO）表。3、用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。4、（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。 （2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序

6、列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的SSS操作序列；对于合法序列BAC，我们使用SSS操作序列。5、三个：CDEBA，CDBEA，CDBAE6、输入序列为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、能得到出

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、如果ij，则对于pipj的情况，则说明要将pj压到pi之上，也就是在pj

8、出栈之后pi才能出栈。这就说明，对于ijk，不可能出现pjpkpi的输出序列。换句话说，对于输入序列1，2，3，不可能出现3，1，2的输出序列。11、（1）能得到325641。在123依次进栈后，3和2出栈，得部分输出序列32；然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。得输出序列325641。其操作序列为AAADDAADADDD。 （2）不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。12、（1）一个函数

9、在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数f在执行中，又调用函数f自身，这称为直接递归；若函数f在执行中，调用函数g，而g在执行中，又调用函数f，这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。 （2）递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。 （3）递归程序执行中需借助栈这种数据结构来实现。 （4）递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本项和归纳项组成。基本项是递归程序出口，即不再递归即可求出结果的部分；归纳项是将原来问题化成简单的且与原来形式一样的问题，即向着“基本项”发展，最终“

10、到达”基本项。13、函数调用结束时vol=14。执行过程图示如下： vol（4） vol(4)=vol(3)+5 14 =vol(2)+3+5 =vol(1)+4+3+5vol（3）+5 =vol(0)+2+4+3+5 9 =0+2+4+3+5 =14vol（2）+3 6vol（1）+4 2vol（0）+2 014、过程p递归调用自身时，过程p由内部定义的局部变量在p的2次调用期间，不占同一数据区。每次调用都保留其数据区，这是递归定义所决定，用“递归工作栈”来实现。15、设Hn为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z，可借助钢针Y) 则 Hn =2Hn-1+1 /先

11、将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z =2（2Hn-2+1）+1 =22 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 =2n-1 H1+2n-2+2n-3+21+20 因为H1=1，所以原式Hn=2n-1+2n-2+21+20=2n-1故总盘数为n的Hanoi塔的移动次数是2n-1。16、运行结果为：1 2 1 3 1 2 1（注：运行结果是每行一个数，为节省篇幅，放到一行。）17、两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为SM

12、AX，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。 用C写的入栈操作push（i，x）如下： const MAX=共享栈可能达到的最大容量 typedef struct node elemtype sMAX； int top2； anode； anode ds; int push(int i,elemtype x)/ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。i的值为0或1，x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回1；否则，返回0。 if（ds.top1-ds.top0=1）printf（“栈满n”）；return（

13、0）； switch（i） case 0：ds.s+ds.topi=x；break； case 1：ds.s-ds.topi=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

14、2 / - * - 栈的变化过程图略（请参见22题），表达式生成过程为：中缀表达式exp1转为后缀表达式exp2的规则如下：设操作符栈s，初始为空栈后，压入优先级最低的操作符#。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。（1）w为一般操作符（+，-，*，/等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。（2）w为左括号（），w入栈。（3）w为右括号（），操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入e

15、xp2），右括号也丢掉，达到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 / -

16、* - 。可用类似方法将中缀表达式转为前缀表达式。20、中缀表达式转为后缀表达式的规则基本上与上面19题相同，不同之处是对运算符*优先级的规定。在算术运算中，先乘除后加减，先括号内后括号外，相同级别的运算符按从左到右的规则运算。而对*运算符，其优先级同常规理解，即高于加减乘除而小于左括号。为了适应本题中“从右到左计算”的要求，规定栈顶运算符*的级别小于正从表达式中读出的运算符*，即刚读出的运算符*级别高于栈顶运算符*，因此也入栈。 下面以A*B*C为例说明实现过程。 读入A，不是操作符，直接写入结果表达式。再读入*，这里规定在读入*后，不能立即当乘号处理，要看下一个符号，若下个符号不是*，则前

17、个*是乘号。这里因为下一个待读的符号也是*，故认为*是一个运算符，与运算符栈顶比较（运算符栈顶初始化后，首先压入#作为开始标志），其级别高于#，入栈。再读入B，直接进入结果表达式。接着读入*，与栈顶比较，均为*，我们规定，后读入的*级别高于栈顶的*，因此*入栈。接着读入C，直接到结果表达式。现在的结果（后缀）表达式是ABC。最后读入#，表示输入表达式结束，这时运算符栈中从栈顶到栈底有两个*和一个#。两个运算符*退栈至结果表达式，结果表达式变为ABC*。运算符栈中只剩#，退栈，运算结束。21、（1）sum=21。当x为局部变量时，每次递归调用，都要给局部变量分配存储单元，故x数值4，9，6和2均

18、保留，其递归过程示意图如下： 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(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-EF求值，过程如下：步骤opnd栈optr栈输入字符主要操作初始#A-B*C/D-EF#PUSH(OPTR,#)

19、1A#A-B*C/D-EF#PUSH(OPND,A)2A# -B*C/D-EF#PUSH(OPTR,-)3AB# -B*C/D-EF#PUSH(OPND,B)4AB# - *C/D-EF#PUSH(OPTR,*)5ABC# - *C/D-EF#PUSH(OPND,C)6AT(T=B*C)# - /D-EF#PUSH(OPND,POP(OPND)*POP(OPND)PUSH(OPTR,/)7ATD# - /D-EF#PUSH(OPND,D)8AT(T=T/D)T(T=A-T)# - # - -EF#x=POP(OPND);y=POP(OPND)PUSH(OPND,y/x);x=POP(OPND)

20、;y=POP(OPND);PUSH(OPND,y-x)PUSH(OPTR,-)9TE# -EF#PUSH(OPND,E)10TE# -F#PUSH(OPTR, )11TEF# -F#PUSH(OPND,F)12 TETS(S=EF) R(R=T-S) #- # # X=POP(OPND) Y=POP(OPND)POP(OPTR) PUSH(OPND,yx)x=POP(OPND) y=POP(OPND)POP(OPTR) PUSH(OPND,y-x) 23、 步骤栈S1栈S2输入的算术表达式（按字符读入）初始A-B*C/D+E/F1AA-B*C/D+E/F2A-B*C/D+E/F3AB-B*C/

21、D+E/F4AB-*C/D+E/F5ABC-*C/D+E/F6AT1（注：T1=B*C）-/D+E/F7AT1D-/D+E/F8AT2（注：T2=T1/D）T3 （注：T3=A-T2）-+E/F9T3E+E/F10T3E+/F11T3EF+/F12T3T4（注：T4=E/F）T5（注：T5= T3+ T4）+24、XSXXXSSSXXSXXSXXSSSS25、S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。26、设

22、栈S1和栈S2共享向量V1.m，初始时，栈S1的栈顶指针top0=0，栈S2的栈顶指针top1=m+1，当top0=0为左栈空，top1=m+1为右栈空；当top0=0并且top1=m+1时为全栈空。当top1-top0=1时为栈满。27、（1）每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。 （2）多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个栈满时要向左、右栈查询有无空闲单元。如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修

23、改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。 （3）多个链栈一般不考虑栈的溢出（仅受用户内存空间限制），缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。28、设top1和top2分别为栈1和2的栈顶指针（1）入栈主要语句if(top2-top1=1) printf(“栈满n”); exit(0);case1:top1+；SPACEtop1=x; /设x为入栈元素。case2:top2-；SPACEtop2=x;出栈主要语句case1：if（top1=-1） printf（“栈空n”）；exit（0）； top1-；return（SPACEtop1+1）； /返回出栈元素。case

24、2：if（top2=N）printf（“栈空n”）；exit（0）； top2+；return（SPACEtop2-1）； /返回出栈元素。 （2）栈满条件：top2-top1=1栈空条件：top1=-1并且top2=N /top1=-1为左栈空，top2=N为右栈空29、设顺序存储队列用一维数组qm表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rea

25、r等于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则为

26、队满。30、见上题29的解答。 31、参见上面29题。32、typedef struct nodeelemtype elemcqm; /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容量相等。分以下三种情况讨论：若s

27、1未满，则元素入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满。这相当队列元素“入队”完毕。出队时，

28、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 structelemtp qm; int front,count; /front是队首指针，count是队列中元素个数。cqnode; /定义类型标识符。

29、(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(“出队元素

30、”，cq.qcq.front); x=cq.qcq.front;cq.front=(cq.front+1)%m; /计算新的队头指针。return(x)(2) 队列中能容纳的元素的个数为m。队头指针front指向队头元素。36、循环队列中元素个数为（REAR-FRONT+N）%N。其中FRONT是队首指针，指向队首元素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。37、循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队列的满与空问题。例如：在队列长10的循环队列中，若假定队头指针front指向队头元素的前一位置，而队尾指针指向队尾元素，则front=

31、3，rear=7的情况下，连续出队4个元素，则front=rear为队空；如果连续入队6个元素，则front=rear为队满。如何判断这种情况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。即假设front=rear为队空，而（rear+1）%表长=front为队满，或通过设标记tag。若tag=0，front=rear则为队空；若tag=1，因入队而使得front=rear，则为队满。本题中队列尾指针rear，指向队尾元素的下一位置,listarrayrear表示下一个入队的元素。在这种情况下，我们可规定，队头指针front指向队首元素。当front=rear时为队空，当（rear+1

32、）%n=front时为队满。出队操作（在队列不空情况下）队头指针是front=（front+1）%n，38、既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。39、（1）4132 （2）4213 （3）423140、（1）队空的初始条件：f=r=0； （2）执行操作A3后，r=3；/ A3表示三次入队操作 执行操作D1后，f=1；/D1表示一次出队操作 执行操作A5后，r=0； 执行操作D2后，f=3； 执行操作A1后，r=1； 执行操作D2后，f=5； 执行操作A4后，按溢出处理。因为执行A3后，r=4，这时队满，若再执行A操作，则出错。41一般说，高级语言

33、的变量名是以字母开头的字母数字序列。故本题答案是:AP321,PA321,P3A21,P32A1,P321A。五、算法设计题1、题目分析两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。#define maxsize 两栈共享顺序存储空间所能达到的最多元素数#define elemtp int /假设元素类型为整型typedef structelemtp stackmaxsize; /栈空间 int top2; /top为两个栈顶指针stk;stk s; /s是如上定义的结构类型变

34、量，为全局变量。(1)入栈操作：int push(int i,int x)/入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。入栈成功返回1，否则返回0。if(i1)printf(“栈号输入不对”);exit(0);if(s.top1-s.top0=1) printf(“栈已满n”);return(0);switch(i) case 0: s.stack+s.top0=x; return(1); break; case 1: s.stack-s.top1=x; return(1); /push（2） 退栈操作 elemtp pop(int i) /退栈算法。i代

35、表栈号，i=0时为s1栈，i=1时为s2栈。退栈成功返回退栈元素，否则返回-1。 if(i1)printf(“栈号输入错误n”)；exit(0); switch(i) case 0: if(s.top0=-1) printf(“栈空n”)；return（-1）； else return(s.stacks.top0-); case 1: if(s.top1=maxsize printf(“栈空n”); return(-1); else return(s.stacks.top1+); /算法结束 算法讨论 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图略，s1栈是通常意义下的栈，

36、而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。2、#define maxsize 栈空间容量 void InOutS(int smaxsize) /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 /读入的整

37、数等于-1时退栈。 if(top=0)printf(“栈空n”);exit(0); else printf(“出栈元素是%dn”,stop-)； /算法结束。3、题目分析判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 int EXYX(char E,int n) /E是有n字符的字符数组，存放字符串表达式，以#结束。本算法判断表达式中圆括号是否匹配。char s30; /s是一维数组，容量足够大，用作存放括号的栈。 int top=0; /top

38、用作栈顶指针。 stop= #; /#先入栈，用于和表达式结束符号#匹配。 int i=0; /字符数组E的工作指针。 while(Ei!= #) /逐字符处理字符表达式的数组。 switch(Ei) case(: s+top=(; i+ ; break ;case): if(stop=(top-; i+; break;elseprintf(“括号不配对”);exit(0);case#: if(stop=#)printf(“括号配对n”);return (1);else printf(“ 括号不配对n”);return (0); /括号不配对 default : i+; /读入其它字符，不作处

39、理。 /算法结束。算法讨论本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况是检查花括号（，）、方括号（，）和圆括号（，）的配对问题。编写算法中如遇左括号（，或（）就压入栈中，如遇右括号（，或），则与栈顶元素比较，如是与其配对的括号（左花括号，左方括号或左圆括号），则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符#时，栈中若应只剩#，表示括号全部配对成功；否则表示括号不匹配。 另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。4、题目分析逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈

40、OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。 float expr( )/从键盘输入逆波兰表达式，以$表示输入结束，本算法求逆波兰式表达式的值。float OPND30; / OPND是操作数栈。init(OPND); /两栈初始化。 float num=0.0; /数字初始化。 scanf (“%c”,&x);/x是字符型变量。 while(x!=$) switch case0=x=0&x=0&xj)prin

41、tf(“序列非法n”)；exit(0); i+; /不论Ai是I或O，指针i均后移。 if(j!=k) printf(“序列非法n”)；return(false); else printf(“序列合法n”)；return(true); /算法结束。 算法讨论在入栈出栈序列（即由I和O组成的字符串）的任一位置，入栈次数（I的个数）都必须大于等于出栈次数（即O的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记0），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。6、题目分析表达式中的括号有以下三对：（、）、，使用栈，当为左括

42、号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对，否则，结论表达式括号不配对。int Match(LinkedList la)/算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对char s; /s为字符栈，容量足够大p=la-link; /p为工作指针，指向待处理结点StackInit(s); /初始化栈s while (p!=la) /循环到头结点为止 switch (p-ch) case (:push(s,p-ch); break; case ):if(StackEmpty(s

43、)|StackGetTop(s)!=()printf(“括号不配对n”); return(0); else pop(s);break;case :push(s,p-ch); break; case : if(StackEmpty(s)|StackGetTop(s)!=)printf(“括号不配对n”); return(0); else pop(s);break;case :push(s,p-ch); break; case : if(StackEmpty(s)|StackGetTop(s)!=)printf(“括号不配对n”); return(0); else pop(s);break; p=

44、p-link; 后移指针/whileif (StackEmpty(s) printf(“括号配对n”); return(1); elseprintf(“括号不配对n”); return(0); /算法match结束 算法讨论算法中对非括号的字符未加讨论。遇到右括号时，若栈空或栈顶元素不是其对应的左圆（方、花）括号，则结论括号不配对，退出运行。最后，若栈不空，仍结论括号不配对。7、题目分析栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中

45、处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。(1) int enqueue(stack s1,elemtp x)/s1是容量为n的栈，栈中元素类型是elemtp。本算法将x入栈，若入栈成功返回1，否则返回0。if(top1=n & !Sempty(s2) /top1是栈s1的栈顶指针，是全局变量。printf(“栈满”);return(0); /s1满s2非空,这时s1不能再入栈。if(top1=n & Sempty(s2) /若s2为空，先将s1退栈,元素再压栈到s2。 while(!Sempty(s1) POP(s1,x);PUSH

46、(s2,x); PUSH(s1,x); return(1); /x入栈，实现了队列元素的入队。(2) void dequeue(stack s2,s1)/s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。if(!Sempty(s2) /栈s2不空，则直接出队。 POP(s2,x); printf(“出队元素为”,x); else /处理s2空栈。 if(Sempty(s1) printf(“队列空”);exit(0);/若输入栈也为空，则判定队空。 else /先将栈s1倒入s2中，再作出队操作。 while(!Sempty(s1) POP(s1,x);PUSH(s2,x); POP

47、(s2,x); /s2退栈相当队列出队。 printf(“出队元素”，x); /结束算法dequue。(3) int queue_empty()/本算法判用栈s1和s2模拟的队列是否为空。if(Sempty(s1)&Sempty(s2) return(1);/队列空。 else return(0); /队列不空。 算法讨论算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，

48、则不论s1元素多少（只要不空），就要全部倒入s2中。 类似本题叙述的其它题的解答：（1） 该题同上面题本质相同，只有叙述不同，请参考上题答案。8、题目分析本题要求用链接结构实现一个队列，我们可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”，且要求入队和出队操作的时间复杂性是O（1），因此我们用只设尾指针的循环链表来实现队列。（1） PROC addq(VAR p:linkedlist,x:elemtp);/p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法是入队操作。new(s); /申请新结点。假设有

49、内存空间，否则系统给出出错信息。s.data:=x; s.link:=p.link;/将s结点入队。p.link:=s; p:=s; /尾指针p移至新的队尾。ENDP;（2） PROC deleq(VAR p:linkedlist,VAR x:elemtp);/ p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法实现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息。IF （p.link=p）THENwriteln(“空队列”);return(0);/带头结点的循环队列。ELSEs:=p.link.link; /找到队头元素。 p.link.link:=s.link; /删队头元素。 x:=s.data; /返回出队元素。 IF (p=s) THEN p:=p.link; /队列中只有一个结点，出队后成为空队列。 dispose(s); /回收出队元素所占存储空间。 ENDP;算法讨论上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队列。否则，可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。9、本题与上题本质上相同，现用类C语言编写入队和出队算法。（1）void EnQueue (LinkedList rear, ElemTyp