第3章栈和队列练习题答案

1第3章栈和队列练习题答案一、填空题1.向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。2.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。3.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4.在具有n个单元的循环队列中，队满时共有n-1个元素。二、判断正误（√）1.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（×）3.栈和队列是一种非线性数据结构。错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（√）4.栈和队列的存储方式既可是顺序方式，也可是链接方式。（√）5.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（×）6.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。错，后半句不对。（×）7.一个栈的输入序列是12345，则栈的输出序列不可能是12345。错，有可能。三、单项选择题（B）1.栈中元素的进出原则是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出（C）2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．iＢ．n-iＣ．n-i+1Ｄ．不确定解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。（若不要求顺序出栈，则输出序列不确定）（D）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%nE：①1②2③3④04.从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。在做进栈运算时，应先判别栈是否A；在做退栈运算时，应先判别栈是否B。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为C。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的D分别设在这片内存空间的两端，这样，只有当E时，才产生上溢。供选择的答案：A，B：①空②满③上溢④下溢2C：①n-1②n③n+1④n/2D：①长度②深度③栈顶④栈底E：①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点③两个栈的栈顶在达栈空间的某一位置相遇④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底答案：ABCDE＝2,1,2,4,3四、阅读理解1.【严题集3.7①】按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教材例3-1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B×C/D+E↑F答：2.【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;Charx,y;InitStack(S);X=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};Printf(x);}3答：输出为“stack”。3.【严题集3.12②】写出下列程序段的输出结果（队列中的元素类型QElemType为char）。voidmain(){QueueQ;InitQueue(Q);Charx=’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);printf(y);};Printf(x);}答：输出为“char”。4.【严题集3.13②】简述以下算法的功能（栈和队列的元素类型均为int）。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。5.分析下列递归程序，并将其改写为非递归过程。voidtest(int&sum){intx；cinx；if(x=0)sum=0;else{test(sum);sum+=x;}coutsum；}答：该算法是以读入数据的顺序为相反顺序进行累加的问题，可将读入数据放入栈中，到输入结束，将栈中数据退出进行累加。累加的初值为0。改写后的非递归程序为：inttest(){4intx,e,sum=0;SqStackS;InitStack(S);cinx;while(x0){Push(S,a);cinx;}coutsum‘’;while(!StackEmpty(S)){Pop(S,e);sum+=e;coutsum‘’;}}