栈和队列练习题.docx
选择题：1、设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（D）。AfedcbaB.bcafedC.dcefbaD.cabdef2、若已知一个栈的入栈序列是1,2,3,口其输出序列为p1,p2,p3,，pN,若pN是n，则pi是（D）。A.iB.n-iC.n-i+1D.不确定3、设计一个判别表达式中左，右括号是否配对出现的算法，采用（D）数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈4、用链接方式存储的队列，在进行删除运算时（D）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改5、递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。A.队列B.多维数组C.栈D.线性表6、假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear,则当前队列中的元素个数为（A）。A（rear-front+m）%mBrear-front+1C（front-rear+m）%mD（rear-front）%m7、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少（B）A.1和5B.2和4C.4和2D.5和18、最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是（A）。A.（rear+1）MODn=frontB.rear=frontCrear+1=frontD.（rear-l）MODn=front9、栈和队列的共同点是（C）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点10、设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1则栈S的容量至少应该是（C）。A6B.4C.3D.2判断题：栈和队列都是限制存取点的线性结构。（）消除递归不一定需要使用栈，此说法（）任何一个递归过程都可以转换成非递归过程。（）两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。()名词解释：栈队列循环队列(1)什么是递归程序(2)递归程序的优、缺点是什么( 3) 递归程序在执行时，应借助于什么来完成( 4) 递归程序的入口语句、出口语句一般用什么语句实现算法题：1、已知数组a，有n个元素，用递归实现以下算法：求和，求最大值，求平均数。判断是否为一个递增数组。大则继续，否则返回false结束：2、试将下列递归过程改写为非递归过程。voidtest(int*sum)intx；scanf(“%d”,&x)；if(x=0)*sum=0elsetest(sum);*sum+=x;printf("%d",*sum)；3、请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,优素x入ST栈；POP(ST,&x)ST栈顶元素出栈，赋给变量x;Sempty(ST)判断ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列；dequeue:删除一个元素出队列；queue_empty:判断队列为空。(请写明算法的思想及必要的注释，不需要代码实现)题目分析栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈si和s2模拟一个队列时，si作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈si退栈并逐个压入栈s2中，si中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且si也为空，才算是队列空。算法讨论算法中假定栈si和栈s2容量相同。出队从栈s2出，当s2为空时，若si不空，则将si倒入s2再出栈。元素从栈si倒入s2,必须在s2空的情况下才能进行，即在要求出队操作时，若s2空,则不论si元素多少(只要不空)，就要全部倒入s2中。入队在si,当si满后，若s2空，则将si倒入s2,之后再入队。因此队列的容量为两栈容量之和。(1) intenqueue(stacksi,elemtpx)/si是容量为n的栈，栈中元素类型是elemtp。本算法将x入栈，若入栈成功返回i,否则返回0oif(topi=n&&!Sempty(s2)/topi是栈si的栈顶指针，是全局变量。printf(“栈满”);return(0);/si满s2非空，这时si不能再入栈。if(topi=n&&Sempty(s2)若s2为空，先将si退栈,元素再压栈到s2。while(!Sempty(si)POP(si,x);PUSH(s2,x);PUSH(si,x)return(i);/x入栈，实现了队列元素的入队。(2) voiddequeue(stacks2,si)/s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。if(!Sempty(s2)栈s2不空，则直接出队。POP(s2,x);printf(“出队元素为",x);else处理s2空栈。if(Sempty(si)printf(“队歹1J空”);exit(0);若输入栈也为空，则判定队空。else/先将栈si倒入s2中，再作出队操作。while(!Sempty(si)POP(si,x);PUSH(s2,x);POP(s2,x);/s2退栈相当队列出队。printf(“出队元素”，x);结束算法dequue。(3) intqueue_empty()本算法判用栈si和s2模拟的队列是否为空。if(Sempty(s1)&&Sempty(s2)return(1);/队列空。elsereturn(0);/队列不空。1、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LIFQ表。2、队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出(FIF。表。3、用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。(1) 一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数f在执行中，又调用函数f自身，这称为直接递归；若函数f在执行中，调用函数g,而g在执行中，又调用函数f,这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。(2)递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。(3)递归程序执行中需借助栈这种数据结构来实现。(4)递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本项和归纳项组成。基本项是递归程序出口，即不再递归即可求出结果的部分；归纳项是将原来问题化成简单的且与原来形式一样的问题，即向着“基本项”发展，最终“到达”基本项。
