资源描述：
《栈和队列练习题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、选择题：1、设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（D）。A．fedcbaB.bcafedC.dcefbaD.cabdef2、若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为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.头
2、、尾指针可能都要修改5、递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。A．队列B．多维数组C．栈D.线性表6、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（A）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m7、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？(B)A.1和5B.2和4C.4
3、和2D.5和18、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（A）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front9、栈和队列的共同点是（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．6B.4C.3D.2判断题
4、：栈和队列都是限制存取点的线性结构。（）消除递归不一定需要使用栈，此说法（）任何一个递归过程都可以转换成非递归过程。（）两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）名词解释：栈队列循环队列（1）什么是递归程序？（2）递归程序的优、缺点是什么？（3）递归程序在执行时，应借助于什么来完成？（4）递归程序的入口语句、出口语句一般用什么语句实现？算法题：1、已知数组a[]，有n个元素，用递归实现以下算法：求和，求最大值，求平均数。判断是否为一个递增数组。
大则继续，否则返回false结束：2、试将下列递归过程
5、改写为非递归过程。voidtest(int*sum){intx；scanf(“%d”,&x)；if(x==0)*sum=0else{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:判断队列为空。（请写明算
6、法的思想及必要的注释，不需要代码实现）[题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。[算法讨论]算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多
7、少（只要不空），就要全部倒入s2中。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。(1)intenqueue(stacks1,elemtpx)//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。{
