《第3章栈和队列.doc》由会员分享，可在线阅读，更多相关《第3章栈和队列.doc（4页珍藏版）》请在三一文库上搜索。
1、第3章 栈和队列重点：栈和队列的区别，fifo,lifo一、填空题（每空1分，共15分）1. 【李春葆】向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。5. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。6. 向栈中压入元素的操作是
2、先 移动栈顶指针 ，后 存入元素 。7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。三、单项选择题（每小题1分，共20分）（ 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。（ B ）3. 李春葆判定一个栈ST（最多元素为m0）为空的条件是 ST-top0 ST-top
3、=0 ST-topm0 ST-top=m0（ B ）4. 李春葆判定一个队列QU（最多元素为m0）为满队列的条件是 QU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ D ）5数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n4.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？答：一般的一维数组队列的尾指针已经
4、到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三： 设置一个布尔变量以区别队满还是队空； 浪费一个元素的空间，用于区别队满还是队空。 使用一个计数器记录队列中元素个数（即队列长度）。我们常采用法，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N5.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有
5、元素多少个？答：用队列长度计算公式： (Nrf)% N L=（401911）% 40=8 L=（401119）% 40=32五、阅读理解（每小题5分，共20分。至少要写出思路）1. 【严题集3.12】写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。void main( )Queue Q; Init Queue (Q);Char x=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(!Q
6、ueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);答：输出为“char”。2. 【严题集3.13】简述以下算法的功能（栈和队列的元素类型均为int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。六、算法设计（每小题5分，共15分。至少要写出思路）【严题
7、集3.31】试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。答：编程如下：int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c); /同时使用栈和队列两种结构while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK;/Palindrome_Test 习题集基础知识题： 3.10算法设计题： 3.293.10 试将下列
8、递归过程改为非递归过程。void test(int &sum)int x;Sanf(x);if(x= =0) sum=0;else test(sum);sum+=x;printf(sum);分析：该递归过程不能改写成一个简单的递推形式的过程，从它的执行过程可见，其输出的顺序恰好和输入相逆，则必须用一个辅助结构保存其输入值，然后逆向取之，显然用栈最为恰当。 要点：1.输入为0时终止循环 2. 没有读懂源程序，仅仅改写为简单的递推过程参考程序： void test(int &sum)Stack S;int x;Sanf(x);InitStack(S);While(x)Push(S,x);Scanf
9、(x);sum=0;printf(sum);while(Pop(S,x)sum+=x;printf(sum);329 如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以 tag的值0或1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志着两种方法的使用范围（如当循环队列容量较小而队列中每个元素占空间较多时，哪一种方法较好）。分析：标志位tag的初值置“0”。一旦元素入队列使rear= =front 时，需置tag为“1”，反之，一旦元素出队列使front= =rear是，需置tag为“0
10、”，以便使下一次进行入队列或出队列操作时（此时front= =rear），可由标志位tag的值来区别队列当时的状态是“满”还是“空”。参考程序：Status EnCyQueue(CyQueue &Q,int x)/带tag域的循环队列入队算法 if(Q.front=Q.rear&Q.tag=1) /tag域的值为0表示空,1表示满 return OVERFLOW; Q.baseQ.rear=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front=Q.rear) Q.tag=1; /队列满 /EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)/带tag域的循环队列出队算法 if(Q.front=Q.rear&Q.tag=0) return INFEASIBLE; Q.front=(Q.front+1)%MAXSIZE; x=Q.baseQ.front; if(Q.front=Q.rear) Q.tag=0 /队列空 很多同学在此处犯错误return OK; /DeCyQueue 注：当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较 多的存储空间,较有价值. 4