栈和队列练习题答案.doc

《栈和队列练习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章栈和队列练习题答案一、填空题1.线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。2.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。3.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。二、判断正误（√）1.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。正确，都是线性逻辑结构，栈和队列其实是特殊的线

2、性表，对运算的定义略有不同而已。（×）3.栈和队列是一种非线性数据结构。错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（√）4.栈和队列的存储方式既可是顺序方式，也可是链接方式。（√）5.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（×）6.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。错，后半句不对。（×）7.一个栈的输入序列是12345，则栈的输出序列不可能是12345。错，有可能。三、单项选择题（B）1.栈中元素的进出原则是Ａ．先进先出Ｂ．后进先

3、出Ｃ．栈空则进Ｄ．栈满则出（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＋

4、r－f;（Ｄ）（n＋r－f）%nE：①1②2③3④0四、阅读理解1.【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;Charx,y;InitStack(S);x=’c’;y=’k’;2Push(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);}答：输出为“stack”。1.【严题集3.

5、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”。2.【严题集3.13②】简述以下算法的功能（栈和队列的元素类型均为i

6、nt）。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);}}答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。2