栈与队列习题与答案(5)

21、（1）sum=21。当x为局部变量时，每次递归调用，都要给局部变量分配存储单元，故x数值4，9，6和2均保留，其递归过程示意图如下： 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-E↑F求值，过程如下：

步骤 opnd栈 optr栈 输入字符 主要操作

初始 #

A-B*C/D-E↑F# PUSH(OPTR,’#’) 1 A #

A-B*C/D-E↑F# PUSH(OPND,A)

2 A # -

-B*C/D-E↑F# PUSH(OPTR,’-’) 3 AB # -

B*C/D-E↑F# PUSH(OPND,B) 4 AB # - *

*C/D-E↑F#

PUSH(OPTR,’*’) 5 ABC # - * C/D-E↑F# PUSH(OPND,C) 6

AT(T=B*C) # - / /D-E↑F#

PUSH(OPND,POP(OPND)*POP(OPND)) PUSH(OPTR,’/’) 7 ATD # - / D-E↑F#

PUSH(OPND,D) 8

AT(T=T/D) T(T=A-T) # - # - -E↑F#

x=POP(OPND);y=POP(OPND)

PUSH(OPND,y/x); x

=POP(OPND);y=POP(OPND); PUSH(OPND,y-x) PUSH(OPTR,’-’) 9 TE # - E↑F#

PUSH(OPND,E) 10 TE # -↑ ↑F#

PUSH(OPTR, ‘↑’) 11 TEF # -↑ F#

PUSH(OPND,F) 12 TE

TS(S=E↑F)

R(R=T-S) #- # #

X=POP(OPND) Y=POP(OPND) POP(OPTR) PUSH(OPND,y↑x) x=POP(OPND) y=POP(OPND) POP(OPTR) PUSH(OPND,y-x)

23、

步骤 栈S1 栈S2

输入的算术表达式（按字符读入）

初始

A-B*C/D+E/F 1 A

A-B*C/D+E/F 2 A -

-B*C/D+E/F 3 AB -

B*C/D+E/F 4 AB -*

*C/D+E/F 5 ABC -*

C/D+E/F 6

AT1（注：T1=B*C）

-/ /D+E/F 7 AT1D -/ D+E/F 8

AT2（注：T2=T1/D） T3 （注：T3=A-T2） - + +E/F 9 T3E + E/F 10 T3E +/ /F 11 T3EF +/ F 12

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的栈顶