数据结构练习题之栈和队列

《数据结构练习题之栈和队列》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第三章栈和队列习题一、选择题1.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）A.edcbaB.dccbaC.dceabD.abode2.一个队列的入队顺序是1，2,3,4,则队列的输出顺序是（）八.4321B.1234C.1432D.32413.若已知一个栈的入栈序列是1，2，3，...，n，其输出序列力pl，p2，p3，...，pn,若pl=n，则pi为（）A.iB.n=iC.n-i+1D.不确定4.栈是将插入或删除操作限定在（）处进行的线性表。A端点B栈底C栈顶D中间5.若一个

2、顺序栈ST在初始化吋top=-l，则判定这个栈（最多元素为niO个）为栈满的条件是（）A.top!=0;B.top==m0;C.top!=m0;D.top==m0-l6.向一个栈顶指针为ns的链栈中插入一个s所指结点时，则执行（）（不带空的头结点）A.HS.next=s;B.s.next=HS.next;HS.next=s;C.s.next=HS;HS=s;D.s.next=HS;HS=HS.next;7.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行的完整操作为（）（不带空

3、的头结点）A.x=HS;HS=HS.next;B.x=HS.data;C.IIS=IIS.next;x=IIS.data;D.x=HS.data;HS=HS.next;1.最大容量为n的循环队列，队尾指针是rear，队头指针是front，则队空的条件是()A.(rear+l)M0Dn=frontB.rear二frontC.rear+l=frontD.(rear-1)MOD2.设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5、e6依次通过栈S,—个元素出栈后即进入队列Q，若6个元素出队的顺

4、序是e2、e4、e3、e6、e5、el,则栈S的容量至少应该是()A.6B.4C.3D.2n=front3.表达式3*274+2*2-6*3)-5求值过程中，当扫描到6时，操作数栈和算符栈为()。A3,2,4,1,1;，(+*_B3,2,4,4;((+-C3,2,4,2,2;*7~D3,2,8;<(-二、填空题1.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234,为了得到1342出栈顺序，相应的S和X的操作串为。2.循环队列的引入，目的是为了克服。3.队列与一般的线性表的区别在于。4.表达

5、式求值是应用的一个典型例子。5.循环队列用数组A[0..m-l]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是。6.解决顺序队列假溢出的一个打效的方法是将溢出条件rear=maxsize改为7.同一个栈内各元素的类型。8.在作入栈运算时，应先判别栈是否，在作出栈时应先判別栈是否。9.设长度为n的链队列用申循环链表，若只设头指针，则入队和出队操作_的_吋间复杂度分别为和;若只设尾指针，则入队和出队操作的时间复杂度分别为和O10.在有n个元素的栈中，进栈和退栈操作的时间复杂

6、度为和。三、判断()1.栈是一种对所有插入、删除操作限于在表的•一端进行的线性表，是一•种盾进先出型结构。队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。()2.栈和队列是一种非线性数据结构。()3.栈和队列的存储方式既可是顺序方式，也可是链接方式。（）4.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把W个栈的栈底分别设在这片内存空问的W端。（）5.由于队列遵循先进先出原则，所以队列出队操作只需要修改头指针。四、实验题1，请编写并实现算法，将任意一个非负的十

7、进制整数，采用辗转相除法，转换为其他进制的数。（耍求阃流程阁。）2,—班有m个女生、n个男生，举办一场舞会.男女生分别编号坐在舞池两边的椅子上，每曲开始时，依次从男生和女生中各出~人配对跳舞，本曲没成功配对者坐着等待卜*一曲找舞伴，设计一个程序模拟舞伴配对过程（男生多于女生，女生多于男生，男生女生人数相等）。要求舞伴的排队遵循先进先岀原则。3,（选做）、n个水手来到一个岛上，采了一堆椰子后，因为疲劳都睡着了。一段吋间后，第一个水手醒来，悄悄地将椰子等分成n份，多出m个椰子，便给了旁边的猴子，然石U己藏

8、起一份再将剩卜*的椰子重新合在一起，继续睡觉。不久,第二名水手醒来，同样将椰子等分成n份，恰好也多出m个，也给了猴子。然后自己也藏起一份，再将剩下的椰子重新合在一起以后每个水手都如此分了一次并都藏起一份，也恰好都把多出的m个给了猴子。第二天n个水手醒来，发现椰子少了许多，心照不宣，便把剩下的椰子分成n份，恰好又多出m个给了猴子。对于给定的整数n、m（约定0〈m〈n〈9从键盘输入），试求原来这堆椰子至少宥多少个？请编写算法实现并阃流程阁。