第3章 栈和队列

《第3章 栈和队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章栈和队列一选择题1.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i2.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.2341563.设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（）。A．fedcbaB.bcafedC.dcefbaD.cabdef4.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈

2、(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.

3、top[2]-top[1]

4、=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]5.执行完下列语句段后，i值为：（）intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.无限递归6.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈7.用不带头结点的单链表存储

5、队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改8.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是()。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front9.依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下

6、哪些序列？A．{d，e，c，f，b，g，a}B.{f，e，g，d，a，c，b}C.{e，f，d，g，b，c，a}D.{c，d，b，e，f，a，g}二判断题1.栈与队列是一种特殊操作的线性表。（）2.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）3.通常使用队列来处理函数或过程的调用。（）4.循环队列通常用指针来实现队列的头尾相接。（）5.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）三填空题1．栈是_______的线性表，其运算遵循_______的原则。2．_______是限定仅在表尾进行插入或删除操

7、作的线性表。3．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。4．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。5.循环队列的引入，目的是为了克服_______。6．区分循环队列的满与空，只有两种方法，它们是__

8、____和______。四应用题1.用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。2.如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。（1）编写实现队列的三个基本运算：判空、入队、出队（2）队列中能容纳元素的最多个数是多少？五．上机题Devillanguage问题有一个魔王总是使用自己的一种非常精练而抽象的语言

9、讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α→β1β2...βm（2）(θδ1δ2...δn)→θδnθδn-1...θδ1θ在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。基本要求：用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇；小写母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。(1)B→tAdA(2)A→sae测试数据：B(ehnxgz)B解

10、释成tsaedsaeezegexenehetsaedsae实现提示：将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，