第3章栈和队列作业参考答案5页word文档

第三章栈和队列作业1、若按教材P44页图3.1（b）所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？（2）如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到？（写出进栈和出栈的栈操作序列）。

123、132、213、231、321输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。

得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

2、试证明：若借助栈由输入序列1、2……n得到的输出序列为p1、p2……p n(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着，i〈j〈k使p j<p k<p i如果i<j，则对于p i<p j情况，说明p i在p j入栈前先出栈。

而对于p i>p j的情况，则说明要将p j压到p i之上，也就是在p j出栈之后p i才能出栈。

这就说明，对于i<j<k，不可能出现p j<p k<p i的输出序列。

换句话说，对于输入序列1，2，3，不可能出现3，1，2的输出序列。

3、按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节3--2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D-E ↑F4、试编写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列，序列1和序列2中不包含字符‘&’，序列1是序列2的逆序列。

第3章栈和队列答案：一、选择题1-5 BCBCB 6-10BCCDD 11-15 BDBBD16-20CCBDB16题解释:一般只需修改队头指针，不过当队列里面只有一个结点时，需要同时修改队尾指针。

二、判断题1-5 ×√×√√6-10 √√√√×11-16√√√××√三、填空题1.栈顶、栈底2. 入栈、出栈3. 队列、先进先出4.栈5.队列6.先进先出7. (R-P+N) % N8. n-1 牺牲一个存储单元、设标记栈底、两栈顶指针相邻（即值之差的绝对值为1）1.没有、一2. 数据域、指针域3. 前驱4.前驱、后继5.前驱、后继6.头结点7.循环链表8. n-19. 栈后进先出10.SXSSXSXX 11.3，1，2 12.牺牲一个存储单元设标记 13.栈底两栈顶指针相邻（即值之差的绝对值为1）四、简答题（每小题5分，共10分）1.简述队列和栈这两种数据类型的相同点和差异处。

答：队列和栈都是操作受限的线性表，都属于线性表的逻辑结构。

区别在于，队列的插入是在队尾端进行，删除是在队头端进行；而栈的插入和删除都只能在栈顶端进行。

2.简述栈和线性表的差别。

答：栈是操作受限的线性表，栈的插入和删除操作都只能在栈顶端进行，因而相应的称为“入栈”和“出栈”。

3.说明线性表、栈与队列的异同点。

答：相同点：都是线性结构；不同点：队列和栈都是操作受限的线性表，队列的插入是在队尾端进行，删除是在队头端进行；而栈的插入和删除都只能在栈顶端进行，而线性表的插入、删除则不受限制，可以在任何位置进行。

4.链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

5.什么是循环队列？答：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的最高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。

第3 章栈和队列习题1．选择题（1）若让元素1，2，3，4，5 依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1 （2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为（）。

A．i B．n-i C．n-i+1 D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top 指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x 中,则应执行操作（）。

A.x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；（5）设有一个递归算法如下int fact(int n) { //n 大于等于0if(n<=0) return 1;else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为（）。

A．n+1 B．n-1 C．n D．n+2 （6）栈在（）中有所应用。

A．递归调用 B．函数调用 C．表达式求值 D．前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。

主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（）。

A．队列B．栈C．线性表D．有序表（8）设栈S 和队列Q 的初始状态为空，元素e1、e2、e3、e4、e5 和e6 依次进入栈S，一个元素出栈后即进入Q，若6 个元素出队的序列是e2、e4、e3、e6、e5 和e1，则栈S 的容量至少应该是（）。

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

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)）。

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

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

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

13、(M+1) MOD N (M+1)% N； 14、队列 15、先进先出 16、先进先出17、s=(LinkedList)malloc(sizeof(LNode))；s->data=x;s->next=r->next；r->next=s；r=s；18、牺牲一个存储单元设标记19、（TAIL+1）MOD M=FRONT (数组下标0到M-1，若一定使用1到M，则取模为0者，值改取M20、sq.front=(sq.front+1)%(M+1)；return(sq.data(sq.front))；(sq.rear+1)%(M+1)==sq.front；21、栈 22、（rear-front+m）% m； 23、（R-P+N）% N；24、（1）a[i]或a[1] （2）a[i] （3）pop（s）或s[1]；25、（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、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。

第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，称为队空。

第三章栈和队列习题答案一、基础知识题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.在栈中存取数据的原则是（ B ）。

A．先进先出 B. 先进后出C. 后进后出D. 没有限制2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。

A．1234 B. 1324 C. 4321 D. 14233．在链栈中，进行出栈操作时（B ）。

A．需要判断栈是否满 B. 需要判断栈是否为空C. 需要判断栈元素的类型D. 无需对栈作任何差别4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。

A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-15．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。

则顺序栈的判满的条件是（ C ）。

A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-16．在队列中存取数据元素的原则是（ A ）。

A．先进先出 B. 先进后出C. 后进后出D. 没有限制7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front 和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A ）。

A．front==rear B. front!=rearC. front==rear+1D. front==(rear+1)% maxSize8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front 和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ）。

A．front==rear B. front!=rearC. front==rear+1D. front==(rear+1)% maxSize9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C ）。

第三章栈和队列一、判断题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章桟和队列3.1 选择题1．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（）A）不确定 B）n-i+1 C）i D）n-i【答案】B【解析】根据栈的性质（LIFO），若输出的第一个元素是n，则表明所有的元素已经入栈，则出栈顺序为n，n-1，…，3，2，1。

2．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（）A）6 B）4 C）3 D）2【答案】C【解析】根据栈的性质（LIFO）得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e4三个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为3。

3．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（）A）top=top+1; V[top]=x B）V[top]=x; top=top+1C）top=top-1; V[top]=x D）V[top]=x; top=top-1【答案】C【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。

本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减一操作。

通常元素进栈的操作为：先移动栈顶指针后存入元素。

4．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。

请问在top为100时，再进行入栈操作，会产生（）A）正常动作 B）溢出 C）下溢 D）同步【答案】B【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。

5．栈在（）中应用。

A）递归调用 B）子程序调用 C）表达式求值 D）A，Ｂ，Ｃ【答案】D7．用链接方式存储的队列，在进行删除运算时（）A）仅修改头指针 B）仅修改尾指针C）头、尾指针都要修改 D）头、尾指针可能都要修改【答案】D【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。