14、过程p递归调用自身时，过程p由内部定义的局部变量在p的2次调用期间，不占同一数据区。每次调用都保留其数据区，这是递归定义所决定，用“递归工作栈”来实现。
15. 试推导出当总盘数为n的Hanoi塔的移动次数。 【北京邮电大学 2001 四、3 （5分）】
15、设Hn为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z，可借助钢针Y)
则 Hn =2Hn-1+1 //先将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z
=2（2Hn-2+1）+1
2
=2 Hn-2+2+1
2
=2（2Hn-3+1）+2+1
32
=2 Hn-3+2+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. 对下面过程写出调用P(3)的运行结果。
PROCEDURE p（w：integer）; BEGIN
IF w>0 THEN
BEGIN
p(w-1);
writeln(w);{输出W} p(w-1）
END；
END；
【西北大学 2001 三、7】
16、运行结果为：1 2 1 3 1 2 1（注：运行结果是每行一个数，为节省篇幅，放到一行。）
17. 用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C或PASCAL设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。
【浙江大学 1998 五、2 (7分)】 17、两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。
用C写的入栈操作push（i，x）如下： const MAX=共享栈可能达到的最大容量 typedef struct node {elemtype s[MAX]；
int top[2]； }anode； anode ds;
int push(int i,elemtype x)
//ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。
i的值为0或1，x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回1；否则，返回0。
{if（ds.top[1]-ds.top[0]==1）{printf（“栈满\\n”）；return（0）；} switch（i）
{case 0：ds.s[++ds.top[i]]=x；break； case 1：ds.s[--ds.top[i]]=x； return（1）；}//入栈成功。 }
18. 简述下列程序段的功能。
PROC algo(VAR S : stack; k:integer); VAR T: stack; temp: integer; WHILE NOT empty(S) DO
[temp:=POP(S); IF temp<>k THEN PUSH(T,temp)];
WHILE NOT empty(T) DO [temp:=POP(T);PUSH(S,temp)]; 【山东科技大学 2002 一、1（4分）】
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)转换成后缀表达式，画出栈的变化过程图。
【南京航空航天大学 2001 五 （10分）】
19、中缀表达式8-(3+5)*(5-6/2）的后缀表达式是： 8 3 5 + 5 6 2 / - * - 栈的变化过程图略（请参见22题），表达式生成过程为：
中缀表达式exp1转为后缀表达式exp2的规则如下：
设操作符栈s，初始为空栈后，压入优先级最低的操作符‘#’。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。
（1）w为一般操作符（’+’，’-‘，’*’，’/’等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。
（2）w为左括号（’（’），w入栈。 （3）w为右括号（’）’），操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入exp2），右括号也丢掉，达到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 / - * - 。 可用类似方法将中缀表达式转为前缀表达式。 20. 在表达式中，有的运算符要求从右到左计算，如A**B**C的计算次序应为(A**(B**C))，这在由中缀生成后缀的算法中是怎样实现的?(以**为例说明)【东南大学1993一、2(6分) 1997一、1(8分)】
20、中缀表达式转为后缀表达式的规则基本上与上面19题相同，不同之处是对运算符**优先级的规定。在算术运算中，先乘除后加减，先括号内后括号外，相同级别的运算符按从左到右的规则运算。而对**运算符，其优先级同常规理解，即高于加减乘除而小于左括号。为了适应本题中“从右到左计算”的要求，规定栈顶运算符**的级别小于正从表达式中读出的运算符**，即刚读出的运算符**级别高于栈顶运算符**，因此也入栈。 下面以A**B**C为例说明实现过程。
读入A，不是操作符，直接写入结果表达式。再读入*，这里规定在读入*后，不能立即当乘号处理，要看下一个符号，若下个符号不是*，则前个*是乘号。这里因为下一个待读的符号也是*，故认为**是一个运算符，与运算符栈顶比较（运算符栈顶初始化后，首先压入‘#’作为开始标志），其级别高于‘#’，入栈。再读入B，直接进入结果表达式。接着读入**，与栈顶比较，均为**，我们规定，后读入的**级别高于栈顶的**，因此**入栈。接着读入C，直接到结果表达式。现在的结果（后缀）表达式是ABC。最后读入‘#’，表示输入表达式结束，这时运算符栈中从栈顶到栈底有两个**和一个‘#’。两个运算符**退栈至结果表达式，结果表达式变为ABC****。运算符栈中只剩‘#’，退栈，运算结束。
21. 有递归算法如下：
FUNCTION sum (n:integer):intger; BEGIN
IF n=0 THEN sum:=0
ELSE BEGIN read(x)；sum:=sum(n-1)+x END；
END；
设初值n=4，读入 x=4,9,6,2
问：(1) 若x为局部变量时；该函数递归结束后返回调用程序的sum=? 并画出在递归过程中栈状态的变化过程；
(2) 若x为全程变量递归结束时返回调用程序的sum=?【北京邮电大学 1997 一 （10分）】 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. 画出对算术表达式A-B*C/D-E↑F求值时操作数栈和运算符栈的变化过程。 【东南大学2000一、3（6分）】
22、设操作数栈是opnd，操作符栈是optr，对算术表达式A-B*C/D-E↑F求值，过程如下：
步骤 初始 1 2 3 4 5 6 7 8 opnd栈 A A AB AB ABC AT(T=B*C) ATD AT(T=T/D) T(T=A-T) optr栈 # # # - # - # - * # - * F# # - / F# # - / F# # - # - -E↑F# x=POP(OPND);y=POP(OPND) PUSH(OPND,y/x); D-E↑/D-E↑PUSH(OPND,POP(OPND)*POP(OPND)) PUSH(OPTR,’/’) PUSH(OPND,D) 输入字符 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↑主要操作 PUSH(OPTR,’#’) PUSH(OPND,A) PUSH(OPTR,’-’) PUSH(OPND,B) PUSH(OPTR,’*’) PUSH(OPND,C) x=POP(OPND);y=POP(OPND); PUSH(OPND,y-x) PUSH(OPTR,’-’) 9 10 11 TE TE TEF # - F# # -↑ F# # -↑ # 12 TE TS(S=E↑F) #- R(R=T-S) #
23. 计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次扫描到运算符时，要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈S1中（得到的结果依次用T1、T2等表示）。为方便比较，假设栈S2的初始栈顶为?（?运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式： A-B*C/D+E/F。写出栈S1和S2的变化过程。【山东科技大学 2001 一、4 （7分）】 23、 步骤 初始 1 2 3 4 5 6 7 8 9 10 11 12 栈S1 A A AB AB ABC AT1（注：T1=B*C） AT1D 栈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? /D+E/F? D+E/F? +E/F? E/F? /F? 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) FPUSH(OPND,F) ↑PUSH(OPTR, ‘↑’) E↑PUSH(OPND,E) AT2（注：T2=T1/D） ?- T3 （注：T3=A-T2） ?+ T3E T3E T3EF ?+ ?+/ ?+/ T3T4（注：T4=E/F） ?+ T5（注：T5= T3+ T4） ?
24. 有字符串次序为3*-y-a/y^2,利用栈，给出将次序改为3y-*ay2^/-的操作步骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS）【东北大学 2001 一、