·
= 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。
12． 用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C或PASCAL设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。 两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为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）；∥入栈成功 } }
13．用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。
中缀表达式8-(3+5)*(5-6/2)的后缀表达式是： 8 3 5 + 5 6 2 / - * - 栈的变化过程图略，表达式生成过程为：
中缀表达式exp1转为后缀表达式exp2的规则如下：
设操作符栈s，初始化为空栈，压入优先级最低的操作符‘#’。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。
11
（1）w为一般操作符（’+’，’-‘，’*’，’/’等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。 （2）w为左括号（’（’），w入栈。
（3）w为右括号（’）’），操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入exp2），右括号也丢掉，达到exp2中消除括号的目的。 （4）w为‘#’，表示中缀表达式exp1结束，操作符栈退栈到exp2，直至碰到‘#’，退栈，整个操作结束。 14．有字符串次序为3*-y-a/y^2,利用栈，给出将次序改为3y-*ay2^/-的操作步骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS）
XSXXXSSSXXSXXSXXSSSS
15．计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次扫描到运算符时，要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈S1中（得到的结果依次用T1、T2等表示）。为方便比较，假设栈S2的初始栈顶为?（?运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式： A-B*C/D+E/F。写出栈S1和S2的变化过程。
步骤 栈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） ?- +E/F? T3 （注：T3=A-T2） ?+ 9 T3E ?+ E/F? 10 T3E ?+/ /F? 11 T3EF ?+/ F? 12 T3T4（注：T4=E/F） ?+ ? T5（注：T5= T3+ T4） ?
16．简述顺序存储队列的假溢出的避免方法及队列满和空的条件。
设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front
12
指向队头元素的前一位置，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则为队满。
17．如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。 编写实现队列的三个基本运算：判空、入队、出队（3分） 队列中能容纳元素的最多个数是多少？（1分） typedef struct {ElemType 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，ElemType 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指向队头元素。
18．给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FRONT，队尾指针REAR)
循环队列中元素个数为（REAR-FRONT+N）%N。其中FRONT是队首指针，指向队首元素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。
19．若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：
能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列； 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列； 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序
13
列。
（1）4132 （2）4213 （3）4231 五、应用题
1．已知一个中缀算术表达式为： 3+4*(25-(6/15))-8@ ，写出对应的后缀算术表达式。
后缀算术表达式：3 4 25 6 15 / － * ＋ 8 － @
2．设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（6分） （1） d,e,b入队 （2） d,e出队 （3） i,j入队 （4） b出队 （5）n,o,p入队
六、程序填空题（或算法阅读题） 1．void exam1(SeqStack S, int m) { SeqStack T; int i； IniStack(T);
while(!Stackempty (S))
if ((i=pop(S))!=m) push(T,i); while (!Stackempty(T))
{ i=pop（T）; push(S,i); } } //exam1
程序段1 的功能是将一个非空栈中值等于m的元素全部删除；（根据答题情况酌情给分）
七、算法设计题 1． 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。【哈尔滨工业大学 2001 七 （12分）】 [题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。
#define maxsize 两栈共享顺序存储空间所能达到的最多元素数
14
#define ElemType int ∥假设元素类型为整型 typedef struct
{ElemType stack[maxsize];∥栈空间
int top[2]; ∥top为两个栈顶指针 }stk;
stk s; ∥s是如上定义的结构类型变量，为全局变量 （1）入栈操作：
int push(int I,int x)
∥入栈。I为栈号，i=0表示左栈s1，i=1表示右栈s2，x是入栈元素。入栈成功返回1，否则返回0
{if(i<0||i>1){printf(“栈号输入不对\\n”);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）退栈操作
ElemType 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]++]); }∥switch }∥算法结束
[算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图略，s1栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。
2．设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 【北京科技大学 2001 九.1 （10分）】 [题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 Int EXYX(char E[],int n)
∥E[]是有n字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆括号是否匹配
{char s[30]; ∥s是一维数组，容量足够大，用作存放括号的栈 int top=0; ∥top用作栈顶指针。
S[top]= ‘#’; ∥‘#’先入栈，用于和表达式结束符号‘#’匹配 int i=0; ∥字符数组E的工作指针
15