算法与数据结构C语⾔版课后习题答案（机械⼯业出版社）第3,4章习题参考答案
第3章栈和队列
⼀、基础知识题
3.1有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出的
序列有哪⼏个。（３在４之前出栈）。
【解答】34215 ，34251，34521
3.2铁路进⾏列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：
1，2，3，4，5，6，那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。
【解答】输⼊序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，前⾯4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。
得到325641的过程如下：1 2 3顺序⼊栈，32出栈，得到部分输出序列32；然后45⼊栈，5出栈，部分输出序列变为325；接着6⼊栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。
得到135426的过程如下：1⼊栈并出栈，得到部分输出序列1；然后2和3⼊栈，3出栈，部分输出序列变为13；接着4和5⼊栈，5，4和2依次出栈，部分输出序列变为13542；最后6⼊栈并退栈，得最终结果135426。
3.3若⽤⼀个⼤⼩为6的数组来实现循环队列，且当前rear和front的值分别
为0和3，当从队列中删除⼀个元素，再加⼊两个元素后，rear和front的值分别为多少？
【解答】2和4
3.4设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过
栈S，⼀个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量⾄少应该是多少？【解答】4
3.5循环队列的优点是什么，如何判断“空”和“满”。
【解答】循环队列解决了常规⽤0--m-1的数组表⽰队列时出现的“假溢出”（即队列未满但不能⼊队）。在循环队列中我们仍⽤队头指针等于队尾指针表⽰队空，⽽⽤牺牲⼀个单元的办法表⽰队满，即当队尾指针加1（求模）等于队头指针时，表⽰队列满。也有通过设标记以及⽤⼀个队头或队尾指针加上队中元素个数来区分队列的“空”和“满”的。
3.6设长度为n的链队列⽤单循环链表表⽰，若只设头指针，则⼊队和出队的时
间如何？若只设尾指针呢？
【解答】若只设头指针，则⼊队的时间为O(n），出队的时间为O(1)。若只设尾指针，则⼊队和出队的时间均为O(1)。
3.7指出下⾯程序段的功能是什么？
(1)void demo1(SeqStack S)
{int i，arr[64]，n=0;
while(!StackEmpty(S)) arr[n++]=Pop(S);
for(i=0;i
}
【解答】程序段的功能是实现了栈中元素的逆置。
(2)void demo2(SeqStack S，int m)∥设栈中元素类型为int型
{int x;SeqStack T;
StackInit(T);
while(!StackEmpty(S))
if((x=Pop(S)!=m) Push(T，x);
while(!(StackEmpty(T)) {x=Pop(T); Push(S，x);}
}
【解答】程序段的功能是删除了栈中值为m的元素。
(3)void demo3(SeQueue Q，int m)∥设队列中元素类型为int型
{int x;SeqStack S;
StackInit(S);
while(!QueueEmpty(Q)){x=QueueOut(Q); Push(S，x);}
while(!StackEmpty(S)){x=Pop(s); QueueIn(Q，x);}
}
【解答】程序段的功能是实现了队列中元素的逆置。
3.8试将下列递推过程改写为递归过程。
void ditui(int n)
{i=n;
while(i>1) printf(i--);
}
【解答】void digui(int n)
{if(n>1){printf(n);
digui(n-1);
}
}
3.9写出下列中缀表达式的后缀表达式：
(1)A*B*C (2)(A+B)*C-D (3)A*B+C/(D-E) (4)(A+B)*D+E/(F+A*D)+C 【解答】(1)ABC**
(2)AB+C*D-
(3)AB*CDE-/+
(4)AB+D*EFAD*+/+C+
3.10选择题：循环队列存储在数组]中，则⼊队时的操作为( )。
A. rear=rear+1
B. rear=(rear+1) % (m-1)
C. rear=(rear+1) % m
D. rear=(rear+1) % (m+1)
【解答】D
3.11 选择题：4个园盘的Hahoi塔，总的移动次数为( )。
A.7
B. 8
C.15
D.16
【解答】C
3.12选择题：允许对队列进⾏的操作有( )。
A. 对队列中的元素排序
B. 取出最近进队的元素
C. 在队头元素之前插⼊元素
D. 删除队头元素
【解答】D
⼆、算法设计题
3.13 利⽤栈的基本操作，编写求栈中元素个数的算法。
【题⽬分析】将栈值元素出栈，出栈时计数，直⾄栈空。
【算法】int StackLength(Stack S)
{//求栈中元素个数
int n=0;
while(!StackEmpty(S)
{n++; Pop(S);
}
return n;
}
算法讨论：若要求统计完元素个数后，不能破坏原来栈，则在计数时，将原栈导⼊另⼀临时栈，计数完毕，再将临时栈倒⼊原栈中。
int StackLength(Stack S)
{//求栈中元素个数
int n=0;
Stack T;
StackInit(T); //初始化临时栈T
while(!StackEmpty(S)
{n++; Push(T,Pop(S));
}
while(!StackEmpty(T)
{Push(S,Pop(T));
}
return n;
}
3.14 双向栈S是在⼀个数组空间V[m]内实现的两个栈，栈底分别处于数组空间
的两端。试为此双向栈设计栈初始化Init(S)、⼊栈Push(S，i，x)、出栈Pop(S，i)算法，其中i为0或1，
⽤以指⽰栈号。[题⽬分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向、迎⾯增长，栈顶指针指向栈顶元素。
#define ElemType int ∥假设元素类型为整型
typedef struct
{ElemType V[m]; ∥栈空间
int top[2]; ∥top为两个栈顶指针
}stk;
stk S; ∥S是如上定义的结构类型变量，为全局变量
(1)栈初始化
int Init()
{S.top[0]=-1;
return 1; //初始化成功
}
(2)⼊栈操作：
int push(stk S ,int i,int x)
∥i为栈号，i=0表⽰左栈，i=1为右栈，x是⼊栈元素。⼊栈成功返回1，否则返回0
{if(i<0||i>1){printf(“栈号输⼊不对\n”);exit(0);}
p[1]-S.top[0]==1) {printf(“栈已满\n”);return(0);}
switch(i)
{case 0: S.V[++S.top[0]]=x; return(1); break;
case 1: S.V[--S.top[1]]=x; return(1);
}
}∥push
(3)退栈操作
ElemType pop(stk S,int i)
∥退栈。i代表栈号，i=0时为左栈，i=1时为右栈。退栈成功返回退栈
元素
∥否则返回-1
{if(i<0 || i>1){printf(“栈号输⼊错误\n”)；exit(0);}
switch(i)
{case0: p[0]==-1) {printf(“栈空\n”)；return（-1）；}
else return(S.p[0]--]);
case 1: p[1]==m {printf(“栈空\n”); return(-1);}
else return(S.p[1]++]);
}∥switch }∥算法结束
(4)判断栈空
int Empty();
{return (S.top[0]==-1 && S.top[1]==m);
}
[算法讨论]请注意算法中两栈⼊栈和退栈时的栈顶指针的计算。s1(左栈)是通常意义下的栈，⽽s2(右栈)⼊栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。
3.15设以数组Q[m]存放循环队列中的元素，同时设置⼀个标志tag，以tag=0
和tag=1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“不空”。试编写相应的⼊队(QueueIn)和出队(QueueOut)算法。（1）初始化
SeQueue QueueInit(SeQueue Q)
{//初始化队列
Q.ar=0; Q.tag=0;
return Q;
}
（2）⼊队
SeQueue QueueIn(SeQueue Q,int e)
{//⼊队列
if((Q.tag==1) && (Q.rear==Q.front)) printf("队列已满\n");
else {Q.rear=(Q.rear+1) % m;
Q.ar]=e;
if(Q.tag==0) Q.tag=1; //队列已不空
}
return Q;
}
(3)出队
ElemType QueueOut(SeQueue Q)
{//出队列
if(Q.tag==0) printf("队列为空\n");
else
{Q.front=(Q.front+1) % m;
数据结构与算法分析答案e=Q.data[Q.front];