chapter3栈与队列(key)

第3章栈和队列一、选择题1.对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序【答案】A2.在作入栈运算时,应先判别栈是否(①),在作出栈运算时应先判别栈是否(②)。当栈中元素为n个,作入栈运算时发生上溢,则说明该栈的最大容量为(③)。①,②:A.空B.满C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2【答案】BAB3.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i【答案】B4.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。A.i-j-1B.i-jC.j-i+1D.不确定的【答案】D5.设有三个元素X，Y，Z顺序入栈（入栈过程中允许出栈），下列得不到的出栈排列是()。A．XYZB.YZXC.ZXYD.ZYX【答案】C6.输入序列为ABC，可以变为CBA时，经过的栈操作为（）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop【答案】B7.栈可以在（）中应用。A.递归调用B.子程序调用C.表达式求值D.A，Ｂ，Ｃ【答案】D8.一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分【答案】B9.执行完下列语句段后，i值为：（）intf(intx){return((x0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.无限递归【答案】B10.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，操作数栈和运算符栈分别为（），其中^为乘幂。A.3,2,4,1,1；(*^(+*-B.3,2,8；(*^-C.3,2,4,2,2；(*^(-D.3,2,8；(*^(-【答案】D11.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈【答案】D12.对于链式队列，在进行出队运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改【答案】D13.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改【答案】D14.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m【答案】A15.循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)【答案】D16.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A.1和5B.2和4C.4和2D.5和1【答案】B17.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)%n==frontB.rear==frontC．rear+1==frontD.(rear-l)%n==front【答案】B18.栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点【答案】C19.栈的特点是（①）,队列的特点是（②）,栈和队列都是（③）。若进栈序列为1,2,3,4则（④）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4则（⑤）是一个出队列序列。①,②:A.先进先出B.后进先出C.进优于出D.出优于进③:A.顺序存储的线性结构B.链式存储的线性结构C.限制存取点的线性结构D.限制存取点的非线性结构④,⑤:A.3,2,1,4B.3,2,4,1C.4,2,3,1D.4,3,2,1F.1,2,3,4G.1,3,2,4【答案】BACCF20.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是()。A．6B.4C.3D.2【答案】C21.在一个具有n个单元的顺序栈中，假定以地址低端(即0单元)作为栈底，以top作为栈顶指针,则当做出栈处理时，top变化为（）(A)top不变(B)top=0(C)top--(D)top++【答案】C22.在具有n个单元的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（）(A)rear%n=front(B)(front+1)%n=rear(C)rear%n-1=front(D)(rear+1)%n=front【答案】D23.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行（）(A)hs-next=s;(B)s-next=hs;hs=s;(C)s-next=hs-next;hs-next=s;(D)s-next=hs;hs=hs-next;【答案】C24.在一个链式队列中，假定front和rear分别是队首和队尾指针，则插入*s结点的操作应执行（）(A)front-next=s;front=s(B)s-next=rear;rear=s(C)rear-next=s;rear=s(D)s-next=front;front=s【答案】C25.在一个链式队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（）(A)front=front-next(B)rear=rear-next(C)rear=front-next(D)front=rear-next【答案】A二、填空题1．栈是_______的线性表，其运算遵循_______的原则。2．_______是限定仅在表尾进行插入或删除操作的线性表。3.设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为{1，2，3，4，5}，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。4．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。5.顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。6.循环队列的引入，目的是为了克服_______。7．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=_______8．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。9.已知链队列的头尾指针分别是f和r，则将值x入队的操作语句序列是p=(NODEPTR)malloc(sizeof(NODE))；p-data=x；p-next=r-next；r-next=p；r=p；。10．区分循环队列的满与空，有两种常用方法，它们是______和______。11．设循环队列用数组A[1..M]表示，队首、队尾指针分别是front和rear，判定队满的条件为_front==(rear+1)%M__。12.设循环队列存放在向量sq.data[0:M]中，则队首指针sq.front在循环意义下的出队操作序列可表示为_elemtype*e；*e=sq.elem[sq.front]；sq.front=(sq.front+1)%(M+1)；__，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。13．表达式求值是_______应用的一个典型例子。14．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是_______。15．顺序栈s存储在数组s-elem[MAXSIZE]中，s栈满的条件是。三、判断题（×）1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×）2.在表结构中最常用的是线性表，栈和队列不太常用。（√）3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（×）5.栈和链表是两种不同的数据结构。（×）6.栈和队列是一种非线性数据结构。（√）7.栈和队列的存储方式既可是顺序方式，也可是链接方式。（×）8.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（×）9.一个栈的输入序列是12345，则栈的输出序列不可能是12345。（√）10.任何一个递归过程都可以转换成非递归过程。（√）11.消除递归不一定需要使用栈。（√）12.栈是实现过程和函数等子程序所必需的结构。（×）13.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（√）14.栈与队列是一种特殊操作的线性表。（×）15.只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。四、简答题1.说明线性表、栈与队的异同点。答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。2.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：设置一个布尔变量以区别队满还是队空；浪费一个元素的空间，用于区别队满还是队空。使用一个计数器记录队列中元素个数（即队列长度）。我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是：front==rear队满标志是：front==(rear+1)%N3.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？答：用队列长度计算公式：(N＋r－f)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32