栈和队列练习题

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