第3章栈与队列习题参考答案

堆栈和队列测试题一、选择题1. 对于栈操作数据的原则是（B）。

A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在做进栈运算时,应先判别栈是否( B),在做退栈运算时应先判别栈是否( A)。

当栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为( B )。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( D )分别设在这片内存空间的两端。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D.n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底3. 一个栈的输入序列依次为1，2，3，…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。

A. 不确定B. n-i+1C. iD. n-i4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。

A. i-j-1B. i-jC. j-i+1D. 不确定的5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则pi是( D )。

A. iB. n-iC. n-i+1D. 不确定6.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 67. 设栈的输入序列是1，2，3，4,则（ D ）不可能是其出栈序列。

A. 1，2，4，3，B. 2，1，3，4，C. 1，4，3，2，D. 4，3，1，2，E. 3，2，1，4，8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 29. 设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。

习题三栈和队列一单项选择题1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/22．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。

A 可能是2B 一定是2C 可能是1D 一定是13. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 64.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（）A.2B. 3C. 5D.65. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。

A. |top[2]-top[1]|=0B. top[1]+1=top[2]C. top[1]+top[2]=mD. top[1]=top[2]6. 执行完下列语句段后，i值为：（）int f(int x){ return ((x>0) ? x* f(x-1):2);}int i ;i =f(f(1));A．2 B. 4 C. 8 D. 无限递归7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。

A. 3,2,4,1,1；(*^(+*-B. 3,2,8；(*^-C. 3,2,4,2,2；(*^(-D. 3,2,8；(*^(-8. 用链接方式存储的队列，在进行删除运算时（）。

第三章栈和队列(参考答案)// 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构// 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。

3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 11 2 4 3 2 1 4 3 3 2 4 11 32 4 23 14 3 4 2 11 3 42 234 11 4 32 2 43 1设入栈序列元素数为n，则可能的出栈序列数为C2n n=(1/n+1)*(2n!/(n!)2)3.2 证明：由j<k和p j<p k说明p j在p k之前出栈，即在k未进栈之前p j已出栈，之后k进栈，然后p k出栈；由j<k和p j>p k说明p j在p k之后出栈，即p j被p k压在下面，后进先出。

由以上两条，不可能存在i<j<k使p j<p k<p i。

也就是说，若有1，2，3顺序入栈，不可能有3，1，2的出栈序列。

3.3 void sympthy(linklist *head, stack *s)//判断长为n的字符串是否中心对称{ int i=1; linklist *p=head->next;while (i<=n/2) // 前一半字符进栈{ push(s,p->data); p=p->next; }if (n % 2 !==0) p=p->next;// 奇数个结点时跳过中心结点while (p && p->data==pop(s)) p=p->next;if (p==null) printf(“链表中心对称”)；else printf(“链表不是中心对称”)；} // 算法结束3.4int match()//从键盘读入算术表达式，本算法判断圆括号是否正确配对（init s;//初始化栈sscanf(“%c”,&ch);while (ch!=’#’) //’#’是表达式输入结束符号switch (ch){ case ’(’: push(s,ch); break;case ’)’: if (empty(s)) {printf(“括号不配对”); exit(0);}pop(s);}if (!empty(s)) printf(“括号不配对”);else printf(“括号配对”);} // 算法结束3.5typedef struct // 两栈共享一向量空间{ ElemType v[m]; // 栈可用空间0—m-1int top[2] // 栈顶指针}twostack;int push(twostack *s,int i, ElemType x)// 两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，// 本算法是入栈操作{ if (abs(s->top[0] - s->top[1])==1) return(0);// 栈满else {switch (i){case 0: s->v[++(s->top)]=x; break;case 1: s->v[--(s->top)]=x; break;default: printf(“栈编号输入错误”); return(0);}return(1); // 入栈成功}} // 算法结束ElemType pop(twostack *s,int i)// 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作{ ElemType x;if (i!=0 && i!=1) return(0);// 栈编号错误else {switch (i){case 0: if(s->top[0]==-1) return(0);//栈空else x=s->v[s->top--];break;case 1: if(s->top[1]==m) return(0);//栈空else x=s->v[s->top++]; break;default: printf(“栈编号输入错误”);return(0);}return(x); // 退栈成功}} // 算法结束ElemType top (twostack *s,int i)// 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作{ ElemType x;switch (i){case 0: if(s->top[0]==-1) return(0);//栈空else x=s->v[s->top]; break;case 1: if(s->top[1]==m) return(0);//栈空else x=s->v[s->top]; break;default: printf(“栈编号输入错误”);return(0);}return(x); // 取栈顶元素成功} // 算法结束3．6void Ackerman(int m,int n)// Ackerman 函数的递归算法{ if (m==0) return(n+1);else if (m!=0 && n==0) return(Ackerman(m-1,1);else return(Ackerman(m-1,Ackerman(m,n-1))} // 算法结束3．7(1) linklist *init(linklist *q)// q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空{ q=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出q->next=q;return (q);} // 算法结束(2) linklist *enqueue(linklist *q，ElemType x)// q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队{ s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出s->next=q->next; // 将元素结点s入队列q->next=s;q=s; // 修改队尾指针return (q);} // 算法结束(3) linklist *delqueue(linklist *q)//q是以带头结点的循环链表表示的队列的尾指针，这是出队算法{ if (q==q->next) return (null); // 判断队列是否为空else {linklist *s=q->next->next; // s指向出队元素if (s==q) q=q->next; // 若队列中只一个元素，置空队列else q->next->next=s->next;// 修改队头元素指针free (s); // 释放出队结点}return (q);} // 算法结束。

栈和队列习题及答案第三章栈和队列⼀、选择题1、⼀个栈的输⼊序列为：a，b，c，d，e，则栈的不可能输出的序列是（）。

A. a,b,c,d,eB. d,e,c,b,aC. d,c,e,a,bD. e,d,c,b,a2、判断⼀个循环队列Q（最多n个元素）为满的条件是（）。

A. Q->rear==Q->frontB. Q->rear==Q->front+1C. Q->front==(Q->rear+1)%nD. Q->front==(Q->rear-1)%n3、设计⼀个判别表达式中括号是否配对的算法，采⽤（）数据结构最佳。

A. 顺序表B. 链表C. 队列D. 栈4、带头结点的单链表head为空的判定条件是（）。

A. head==NULLB. head->next==NULLC. head->next!=NULLD. head!=NULL5、⼀个栈的输⼊序列为：1,2,3,4，则栈的不可能输出的序列是（）。

A. 1243B. 2134C. 1432D. 4312E. 32146、若⽤⼀个⼤⼩为6的数组来实现循环队列，且当rear和front的值分别为0，3。

当从队列中删除⼀个元素，再加⼊两个元素后，rear和front 的值分别为（）。

A. 1和5B. 2和4C. 4和2D. 5和17、队列的插⼊操作是在（）。

A. 队尾B. 队头C. 队列任意位置D. 队头元素后8、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（）。

A. front==rearB. front==0C. rear==0D. front=rear+19、⼀个顺序栈S，其栈顶指针为top，则将元素e⼊栈的操作是（）。

A. *S->top=e;S->top++;B. S->top++;*S->top=e;C. *S->top=eD. S->top=e;10、表达式a*(b+c)-d的后缀表达式是（）。

一、选择题一、选择题1、栈中存取数据的原则（）、栈中存取数据的原则（）A 、先进先出B 、先进后出C 、后进后出D 、随意进出、随意进出2、队列中存取数据的原则（）、队列中存取数据的原则（） A 、先进先出 B 、后进先出 C 、先进后出 D 、随意进出、随意进出3、插入和删除只能在一端进行的线性表，称为（）、插入和删除只能在一端进行的线性表，称为（）A 、队列B 、循环队列C 、栈D 、循环栈、循环栈4、在栈中，出栈操作的时间复杂度为（）、在栈中，出栈操作的时间复杂度为（）A 、O （1）B 、O （log 2n ）C 、O （n ）D 、O （n 2）5、设长度为n 的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为（）（） A 、O （1） B 、O （log 2n ） C 、O （n ） D 、O （n 2）6、设长度为n 的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为（）（） A 、O （1） B 、O （log 2n ） C 、O （n ） D 、O （n 2）7、一个线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）是（） A 、110 B 、108 C 、100 D 、1208、一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是（），则栈的不可能的输出序列是（）A 、edcbaB 、decbaC 、dceabD 、abcde9、若已知一个栈的入栈序列是1，2，3，……，n ，其输出序列是p1,p2,p3,……,pn ，若p1=n ，则pi 为（）为（）A 、iB 、n=iC 、n-i+1D 、不确定、不确定10、判断一个栈ST （最多元素m0）为空的条件是（））为空的条件是（）A 、ST->top==0B 、ST->top==-1C 、ST->top!=m0D 、ST->top==m0 11、判断一个栈ST （最多元素m0）为满的条件是（））为满的条件是（）A 、ST->top!=0B 、ST->top==0C 、ST->top!=m0D 、ST->top==m0 12、判断一个循环队列QU （最多元素为m0）为空的条件是（））为空的条件是（） A 、QU.front==QU.rear B 、QU.front!=QU.rearC 、QU.front==(QU.rear+1)%m0D 、QU.front!=(QU.rear+1)%m013、判断一个循环队列QU （最多元素为m0）为满的条件是（））为满的条件是（）A 、QU.front==QU.rearB 、QU.front!=QU.rearC 、QU.front==(QU.rear+1)%m0D 、QU.front!=(QU.rear+1)%m0 14、循环队列用数组存放其元素值A[0，m-1]，已知其头尾指针分别是rear 和front ，则当前队列的元素个数是（）队列的元素个数是（）A 、(rear-front+m)%mB 、rear-front+1C 、rear-front-1D 、rear-front 15、栈和队列的共同特点是（）、栈和队列的共同特点是（）A 、都是先进后出B 、都是先进先出、都是先进先出C 、只允许在端点处插入和删除D 、没有共同点、没有共同点二、填空题二、填空题1、设长度为n 的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（O(N)）和（O(1)）；若又设尾指针，则入队和出队操作的时间复杂度分别为（O(1)）和（O(1)）。

第3章栈和队列习题参考答案第3章栈和队列一、基础知识题3.1有五个数依次进栈：1，2，3，4，5。

在各种出栈的序列中，以3，4先出的序列有哪几个。

（３在４之前出栈）。

【解答】34215 ，34251，345213.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和43.4设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量至少应该是多少？【解答】43.5循环队列的优点是什么，如何判断“空”和“满”。

第3章作业参考答案1.1,4,3,5,2)能,1011100100：(1,4,2,3,5)不能，因为4先于3和2出栈，4出栈时，2和3都在栈中，且2压在3之下，故只能3 先出栈才能2出栈。

*若借助栈由输入序列1,2，…，n得到输出序列为P1/p2，…,p n,则在输出序列中不可能出现这样的情形：存在着ivjvk使PjVpkVpi。

2.借助栈T,删除栈S中元素值为k的元素。

4.〃定义双向栈类template <class ElemType>〃声明一个类模板class DSqStack{public: 〃双向栈类的各成员函数DSqStack(int m = 100);~DSqStack();bool Empty(int i) const;ElemType & Top(int i) const;void Push(const ElemType &e」nt i);void Pop(int i);private: 〃双向栈类的数据成员ElemType *base; 〃基地址指针int top[2]; 〃栈顶指针int size; 〃向量空间大小}；〃构造函数，分配m个结点的顺序空间，构造一个空的双向栈。

template <class ElemType>DSqStack <ElemType>::DSqStack(int m){top[0] =-l;top[l] = m;base = new ElemType[m];size = m;}//DSqStack〃析构函数，将栈结构销毀。

template <class ElemType>DSqStack <ElemType>::~DSqStack()讦(base != NULL) deleted base;}//~SqStack〃判栈是否为空,若为空，则返回true,否则返回false。

template <class ElemType> bool DSqStack <ElemType>::Empty(int i) const{//i的取值为0或1if (i==0)return top[0] == -1;elsereturn top[l] == size;}//Empty〃取栈顶元素的值。

第三章栈和队列课后习题答案1、单项选择题（1） B（2） B（3） D（4） D（5） C（6） C（7） B（8） C（9） B（10）C2、填空题（1）后进先出先进先出（2）front = rear （rear+1）% Max = front（3）top = 0 top =N-1（4）空空只含有一个结点（5）p->next=top; top=p;（6）rear->next=p; rear=p;（7） 4（8）假上溢3、问答题（1）参考答案：栈的操作特点是后进先出，因此输出序列有：A入，A出，B入，B出，C入C出，输出序列为ABC。

A入，A出，B入，C入，C出，B出，输出序列为ACB。

A入，B入，B出，A出，C入，C出，输出序列为BAC。

A入，B入，B出，C入，C出，A出，输出序列为BCA。

A入，B入，C入，C出，B出，A出，输出序列为CBA。

（2）参考答案：8 3 5 + 5 6 2 / - * -（3）参考答案：一个过程（或函数）直接或间接调用自己，这种过程（或函数）叫递归过程（或函数）。

递归算法一般用于解决三类问题：1）数据的定义是按递归定义的。

（Fibonacci函数）2）问题解法按递归算法实现。

（回溯）3）数据的结构形式是按递归定义的。

（树的遍历，图的搜索）设计递归算法的方法：①寻找递归通式，分解问题；②设置递归出口，确定递归终止条件。

（4）参考答案：向一个顺序栈插入一个元素时，首先使栈顶指针后移一个位置，然后把待插入元素写入到这个位置上。

（5）参考答案：向一个链栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给栈顶指针。

（6）参考答案：①一种是在定义结构体时，附设一个存储循环队列中元素个数的变量如n，当n=0时，队空。

当n=MaxSize时为队满。

②另一种方法是少用一个元素控件，约定当尾指针加1等于头指针时，认为是队满，可用于求模运算来实现，即front=rear，称为队空。

第三章栈与队列（答案）一、选择题1．栈的特点是（ B ），队列的特点是（ A ）。

A、先进先出B、后进先出2.一个栈的队列顺序是a,b,c,d,e，则栈的不可能的输出序列是（）。

A 、edcba B、decba C、dceab D 、abcde3. 判断一个队列QU（最多元素为MAXSIZE）为空的条件是（）A 、QU->rear-QU->front== MAXSIZE B、QU->rear-QU->front-1==MAXSIZEC、QU->front==QU->rearD、QU->front==QU->rear+14.若已知一个栈的进栈序列是1，2，3,……..,n，其输出序列为p1,p2,p3,…..,pn,若p1=n,则pi(1<=i<n)为（）A、i B 、n=i C、n-i+1 D、不确定5.循环顺序队列中是否可以插入下一个元素，（）A、与队首指针和队尾指针的值有关B、只与队尾指针的值有关，与队首指针的值无关C、只与数组大小有关，与队首指针和队尾指针的值无关D、与曾经进行过多少次插入操作有关二、填空题1. 设有编号为1，2，3，4的四辆车，顺序进入一个栈式结构的站台（栈的大小为4），试写出这四辆车开出站的所有可能的顺序（每辆车入站后出站的时间未知）：1234，1243，1324，1342，1432，2134，2143，2314，2341，2431，3214，3241，3421，43212.将下列各中缀表达式转换成后缀表达式。

（A*（B+C）+D）*E-F*G ABC+*D+E*FG*- ;A*(B-D)+H/(D+E)-S/N*T ABD-*HDE+/+SN/T*- ;(A-C)*(B+D)+(E-F)/(G+H) AC-BD+*EF-GH+/+3.顺序栈的入栈操作Sqstack *push_seqstack(Sqstack *s,elementtype x){ if(s->top= =MAXLEN-1){ printf(“上溢\n”);return 0;}else{ s->top++;s->element[s->top] =x;return s;}}4.链栈的出栈操作int *pop_linkstack(linkstack *s,elementtype y) {linkstack *p;if(s==NULL ){ printf(“下溢\n”);return 0;}else{ p=s;y=s->data;s= s->next ;(或者s=p->next)free(p);return 1;}}5.循环队列的出队操作elementtype delete_cyqueue(Cqueue *cp,elementtype y) { if( cp->front= =cp->rear ){ printf(“下溢\n”);return NULL;}else{ cp->front= (cp->font+1)%MAXLEN ;y=cp->element[cp->front];return y;} }。

第3章栈和队列一选择题1. 对于栈操作数据的原则是（）。

A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底⑤: A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点.C. 两个栈的栈顶在栈空间的某一位置相遇.D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。

A. 不确定B. n-i+1C. iD. n-i4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。

A. i-j-1B. i-jC. j-i+1D. 不确定的5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。

A. iB. n-iC. n-i+1D. 不确定6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 67. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

A. 1，2，4，3，B. 2，1，3，4，C. 1，4，3，2，D. 4，3，1，2，E. 3，2，1，4，8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。

第三章栈和队列习题答案一、基础知识题3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。

(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。

答：(1)出栈序列为：1324(2)不能得到1423序列。

因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。

这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。

能得到1432的出栈序列。

具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是：1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,43123.2 链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

3.3 循环队列的优点是什么? 如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。

判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。

第三章栈和队列一、选择题二、判断题部份答案解释如下。

1、尾递归的消除就不需用栈2、这个数是前序序列为1,2,3,…,n，所能取得的不相似的二叉树的数量。

三、填空题1、操作受限（或限定仅在表尾进行插入和删除操作）后进先出2、栈3、3 1 24、23 100CH5、0 n+1 top[1]+1=top[2]六、两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）。

7、(1)满(2)空(3)n (4)栈底(5)两栈顶指针相邻（即值之差的绝对值为1）八、链式存储结构九、S×SS×S××10、data[++top]=x；1一、（注：表达式中的点(.)表示将数隔开，如是三个数）1二、假溢出时大量移动数据元素。

13、(M+1) MOD N (M+1)% N；14、队列1五、先进先出1六、先进先出17、s=(LinkedList)malloc(sizeof(LNode))；s->data=x;s->next=r->next；r->next=s；r=s；1八、捐躯一个存储单元设标记1九、（TAIL+1）MOD M=FRONT (数组下标0到M-1，若必然利用1到M，则取模为0者，值改取M20、=+1)%(M+1)；return)；+1)%(M+1)==；2一、栈2二、（rear-front+m）% m；23、（R-P+N）% N；24、（1）a[i]或a[1] （2）a[i] （3）pop（s）或s[1]；2五、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate （a，theta，b））26、（1）T>0（2）i<n（3）T>0（4）top<n（5）top+1（6）true（7）i-1（8）top-1（9）T+w[i]（10）false四、应用题1、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。

第三章栈和队列一、判断题1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。

（×）2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。

（×）二、填空题1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。

2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。

3、有如下递归过程：Void Print(int w){int i;if (w!=0){Print(w−1);for (i=1;i<=w;i++) printf(“%3d”,w);printf(“\n”);}}调用语句print(4)的结果是__________。

12 23 3 34 4 4 44、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S；三、选择题1、设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。

在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。

假设栈或队的初始状态都是空。

现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。

经操作后，最后在栈中或队中的元素还有 E 2个。

供选择的答案：A～D：①a1 ②a2 ③ a3 ④a4E：①1 ②2 ③ 3 ④ 02、栈是一种线性表，它的特点是 A 2。

设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。

第3章栈和队列练习题答案一、填空题1. 线性表、栈和队列都是线性结构,可以在线性表的任何位置插入和删除元素;对于栈只能在栈顶插入和删除元素;对于队列只能在队尾插入和队首删除元素。

2. 栈是一种特殊的线性表,允许插入和删除运算的一端称为栈顶。

不允许插入和删除运算的一端称为栈底。

3. 队列是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。

二、判断正误(√)1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。

(√)2. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。

正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。

(×)3. 栈和队列是一种非线性数据结构。

错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。

(√)4. 栈和队列的存储方式既可是顺序方式,也可是链接方式。

(√)5. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。

(×)6. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。

错,后半句不对。

(×)7. 一个栈的输入序列是12345,则栈的输出序列不可能是12345。

错,有可能。

三、单项选择题(B)1.栈中元素的进出原则是A.先进先出B.后进先出C.栈空则进D.栈满则出(C)2.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为A.iB.n-iC.n-i+1D.不确定解释:当p1=n,即n是最先出栈的,根据栈的原理,n必定是最后入栈的(事实上题目已经表明了),那么输入顺序必定是1,2,3,…,n,则出栈的序列是n,…,3,2,1。

(若不要求顺序出栈,则输出序列不确定)(D)3.数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为(A)r-f; (B)(n+f-r)% n; (C)n+r-f; (D)(n+r-f)% nE:①1 ②2 ③3 ④0四、阅读理解1.【严题集3.3②】写出下列程序段的输出结果(栈的元素类型SElem Type为char)。

一、选择题1. A2. C3. B4. B5. A6. B7. C8. C9. B10. D11. B12. D13. B14. D15. A16. B17. D18. C19. C20. B21. B二、填空题1. 队列2. FILO FIFO3. 栈顶栈底4. 前一个位置；n-15. 尾首6. 队尾队头7. 线性表后进先出表8. s->next=h->next h=s9. q->front->next=NULLq->rear=q->front;10. stack三、判断题1. ×2. √3. √4. ×5. √6. √7. √8. √9. ×10. ×四、简答题1. 顺序队列的结构:typedef struct{datatype data[maxsize]int front rear;}sequeue;sequeue *sq;2. 解答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点3. (1)出栈序列为：1324(2)不能得到1423序列。

因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push(3),Push(4),Pop()。

这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。

能得到1432的出栈序列。

具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

4. 用队列长度计算公式：(N＋r－f)% N① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=325. 答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。

6. 栈是仅允许在一端进行插入和删除的线性表,又称为后进先出表, 队列是允许在一端插入,在另一端删除的线性表,允许插入的一端的称为队尾,允许删除的一端称为队头,又称为先进先出表。

第三章栈和队列一、单项选择题参考答案： 1. A 2. B 3. C 4. A 5. B6. B7. D8. D9. C 10. A11. D 12. A 13. A 14. D 15. C二、填空题参考答案：1. 先进后出2. 先进先出3. 队尾，队头4. 栈顶指针5. 栈顶指针6. MaxSize-17. top==08. 空栈9. 栈顶指针10. p->link=top，top=p11. top=top->link 12. Q.front==Q.rear 13. (Q.rear+1)%MaxSize==Q.front14. 队尾指针15. 空，只含有一个结点16. front == rear && front != NULL或者front == rear && rear != NULL17. 两端18. 3x2+*5- 19. 15 20. 3三、判断题参考答案： 1. 是 2. 是 3. 否 4. 是 5. 是6. 否7. 否8. 是9. 否10. 否11. 否12. 是13. 否14. 是15. 否16. 否四、运算题参考答案：1.根据以上规则，给出计算中缀表达式a + b * c – d / e时两个栈的变化。

步扫描项项类型动作OPND栈OPTR栈0 OPTR栈与OPND栈初始化, ‘#’ 进OPTR栈,#取第一个符号1 a 操作数a进OPND栈, 取下一符号 a #2 + 操作符icp (‘+’ ) > isp (‘#’ ), 进OPTR栈, 取a # +下一符号3 b 操作数b进OPND栈, 取下一符号 a b # +a b # + *4 * 操作符icp (‘*’ ) > isp (‘+’ ), 进OPTR栈, 取下一符号5 c 操作数c进OPND栈, 取下一符号 a b c # + *a s1# +6 - 操作符icp (‘-’ ) < isp (‘*’ ), 退OPND栈‘c’,退OPND栈‘b’, 退OPTR栈‘*’, 计算 b * c→ s1,结果进OPND栈s2#7 同上同上ic p (‘-’ ) < isp (‘+’ ), 退OPND栈‘s’,1退OPND栈‘a’, 退OPTR栈‘+’, 计算 a * s1→s2, 结果进OPND栈8 同上同上icp (‘-’ ) > isp (‘#’ ), 进OPTR栈, 取下一符号s2# -9 d 操作数d进OPND栈, 取下一符号s2 d # -10 / 操作符icp (‘/’ ) > isp (‘-’ ), 进OPTR栈, 取下一符号s2 d # - /11 e 操作数e进OPND栈, 取下一符号s2 d e # - /12 # 操作符icp (‘#’ ) < isp (‘/’ ), 退OPND栈‘e’,退OPND栈‘d’, 退OPTR栈‘/’, 计算 d / e →s5, 结果进OPND栈s2 s3# -13 同上同上icp (‘#’ ) < isp (‘-’ ), 退OPND栈‘s3’,退OPND栈‘s2’, 退OPTR栈‘-’, 计算 s2– s3→s4, 结果进OPND栈s4#14 同上同上 icp (‘#’ ) == isp (‘#’ ), 退OPND栈‘s4’, 结束#2.利用运算符优先数，画出将中缀表达式a + b * c - d / e 改为后缀表达式时运算符栈OPTR的变化。

第三章栈与队列习题答案一、基础知识题3、1 设将整数1,2,3,4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下述问题:(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈得数字序列为何(这里Push(i)表示i进栈,Pop( )表示出栈)?(2)能否得到出栈序列1423与1432?并说明为什么不能得到或者如何得到。

(3)请分析1,2 ,3 ,4 得24种排列中,哪些序列就是可以通过相应得入出栈操作得到得。

答:(1)出栈序列为:1324(2)不能得到1423序列。

因为要得到14得出栈序列,则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。

这样,3在栈顶,2在栈底,所以不能得到23得出栈序列。

能得到1432得出栈序列。

具体操作为:Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1,2 ,3 ,4 得24种排列中,可通过相应入出栈操作得到得序列就是:1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321不能得到得序列就是:1423,2413,3124,3142,3412,4123,4132,4213,4231,43123、2 链栈中为何不设置头结点?答:链栈不需要在头部附加头结点,因为栈都就是在头部进行操作得,如果加了头结点,等于要对头结点之后得结点进行操作,反而使算法更复杂,所以只要有链表得头指针就可以了。

3、3 循环队列得优点就是什么? 如何判别它得空与满?答:循环队列得优点就是:它可以克服顺序队列得"假上溢"现象,能够使存储队列得向量空间得到充分得利用。