/D+E^F# Operate(B * C) 7 #- A G /D+E^F# PUSH(OPTR /) 8 #-/ A G D+E^F# PUSH(OPND D) 9 #-/ A G D +E^F# Operate(G / D) 10 #- A H +E^F# Operate(A - H) 11 # I +E^F# PUSH(OPTR +) 12 #+ I E^F#

PUSH(OPND E) 13 #+

I E ^F#

PUSH(OPTR ^) 14 #+^ I E F#

PUSH(OPND F) 15 #+^ I E F #

Operate(E ^ F) 16 #+ I J #

Operate(I + J) 17 # K #

RETURN

3.8 试推导求解n阶梵塔问题至少要执行的move操作的次数

解：

3.9 试将下列递推过程改写为递归过程

void ditui(int n) {

int i; i = n; while(i>1) cout<

void ditui(int j) {

if(j>1){ cout<

return; }

3.10 试将下列递归过程改写为非递归过程

void test(int &sum) {

int x; cin>>x;

if(x==0) sum=0; else {

test(sum); sum+=x; }

cout<

void test(int &sum) {

Stack s;

InitStack(s); int x; do{

cin>>x; Push(s x);

}while(x>0);

while(!StackEmpty(s)){ Pop(s x);

sum+=x;

cout<

DestoryStack(s); }

3.11 简述队列和堆栈这两种数据类型的相同点和差异处

解：栈是一种运算受限的线性表

其限制是仅允许在表的一端进行插入和删除运算

队列也是一种运算受限的线性表 其限制是仅允许在表的一端进行插入 而在表的另一端进行删除

3.12 写出以下程序段的输出结果（队列中的元素类型QElemType为char）

void main() {

Queue Q;

InitQueue(Q); char x= 'e' y= 'c';

EnQueue(Q 'h');

EnQueue(Q 'r');

EnQueue(Q y);

DeQueue(Q x);

EnQueue(Q x);

DeQueue(Q x);

EnQueue(Q 'a');

While(!QueueEmpty(Q)) {

DeQueue(Q y);

cout<

cout<

解：char

3.13 简述以下算法的功能（栈和队列的元素类型均为int）

void algo3(Queue &Q) {

Stack S; int d;

InitStack(S);

while(!QueueEmpty(Q)) {