数据结构第3章栈队列学习习题

1、第3章栈与队列一、单项选择题1元素A、C、D依次序后，元素是，底元素是。AABBCCDD2以下运算后，x的是。InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x);AaBbC1D03已知一个的序列是ABC，出序列CBA，的操作是。Apush,pop,push,pop,push,popBpush,push,push,pop,pop,popCpush,push,pop,pop,push,popDpush,pop,push,push,pop,pop4一个的入序列A、B、C、D，借助一个所获取的序列是。AA,B,C,DBD,C,B,ACA,C,D,

2、BDD,A,B,C5一个的序列是a，b，c，d，e，的不可以能的出序列是。AedcbaBdecbaCdceabDabcde6已知一个的序列是1，2，3，,n，其出序列的第一个元素是i，第j个出元素是。AiBn-iCj-i+1D不确定7已知一个的序列是1，2，3，n，其出序列是p1,p2,Pn，若p1=n，pi的。AiBn-iCn-i+1D不确定8n个元素序列是1，2，3，n，其出序列是p1,p2,pn，若p1=3,p2的。A必然是2B必然是1C不可以能是1D以上都不9n个元素序列是p1,p2,pn，其出序列是1，2，3，n，若p3=1,p1的。A可能是2B必然是1C不可以能是2D不可以能是31

3、0n个元素序列是12n3p,p,p，其出序列是1，2，3，n，若p=3,p1的。A可能是2B必然是2C不可以能是1D必然是111n个元素序列是p1,p2,pn，其出序列是1，2，3，n，若pn=1,pi(1n的。i-1)An-i+1Bn-iCiD有多种可能12判断一个序S空的条件。AS.top=S.baseBS.top!=S.baseCS.top!=S.base+S.stacksizeDS.top=S.base+S.stacksize13判断一个序S的条件是。AS.top-S.base=S.stacksizeBS.top=S.baseCS.top-S.base!=S.stacksizeDS.t

4、op!=S.base14与序对照有一个明的点，即。A插入操作方便B平时不会出的情况C不会出空的情况D除操作更加方便15最不适合用作的表是。A只有表指没有表尾指的循双表B只有表尾指没有表指的循双表C只有表尾指没有表指的循表D只有表指没有表尾指的循表16若是以表作的存构，退操作。A必判可否B判元素的型C必判可否空D不作任何判17向一个不带头结点的栈顶指针为1st的链栈中插入一个s所指结点时，则执行。A1st-next=s;Bs-next=1st-next;1st-next=s;Cs-next=1st;1st=s;Ds-next=1st;1st-next;18从一个不带头结点的栈顶指针为S的链栈中删

5、除一个结点时，用x保存被删除结点的值，则执行。Ax=S;S=S-next;Bx=S-data;CS=S-next;x=S-data;Dx=S-data;S=S-next;19经过以下队列运算后，队头的元素是。InitQueue(qu);enQueue(qu,a);enQueue(qu,b);enQueue(qu,c);deQueue(qu);AaBbC1D020经过以下队列的运算后，QueueEmpty(q)的值是。InitQueue(qu);enQueue(qu,a);enQueue(qu,b);deQueue(qu,x);deQueue(qu,y);AaBbC1D021元素A,B,C,D次

6、序连续进入队列qu后，队头元素是，队尾元素是。AABBCCDD22一个队列的入队序列为1,2,3,4，则队列可能的输出序列是_.A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,1二、填空题1栈是一种拥有特点的线性表。2次序栈和链栈的差异仅在于不同样。3若是栈的最大长度不可以估计，则最好使用。4一个栈的输入序列是1,2,3,4,5，则栈的输出序列1,2,3,4,5是。5若用不带头结点的单链表来表示链栈S，则创办一个空栈所要执行的操作是。6于S，操作在端行，出操作在端行。7列是一种拥有特点的性表。8序列和列的区在于的不同样。9若是列的最大度以估，最好使用_。三、判断题1序中元素的大小

7、是有序的。2在n个元素后，它的出序和序必然正好相反。3元素和底元素有可能是同一个元素。4若用S1m表示序的存空，的，出操作最多只能行次。5是一种，出操作次数作了限制的性表。6空没有指。7和列都是限制存取端的性表。8列是一种列，出列操作的次序作了限制的性表。9n个元素列的序和出列的序是一致的。10序中有多少元素，可以依照首指的和尾指的来算。11若用“指的和尾指的相等”作形序空的志，在置一个空列，只需指和尾指同一个，无论什么都可以。12无是序列，是列，入和出操作的复度都是O(1)。13列的入序列1,2,3,，,n出序列a1,a2,anaiai+1(1i-n1)四、简答题1有5个元素，其次序A,B,

8、C,D,E,在各种可能的出次序中，以元素C,D最先出（即C第一个且D第二个出）的次序有哪几个？2入元素1，2，3，P和A，入次序1,2,3,P,A，元素后到达出序列，当所有元素均到达出序列后，有哪些序列可以作高言的量名？3设有一个数列的输入次序为1,2,3,4,5,6，若采用栈结构，并以A和D分别表示进栈和出栈操作，试问经过进栈和出栈操作的合法序列是什么？（1）可否获取输出次序为3,2,5,6,4,1的序列。（2）可否获取输出次序为1,5,4,6,2,3的序列。4简述线性表、栈和队列的异同。5设栈S和队列Q的初始状态都为空，元素a,b,c,d,e和f依次经过栈S，一个元素出栈后即进入队列Q，若6个元素的出队的序列是b,d,c,f,e,a，则栈S的容量最少应该存多少个元素。五、算法设计题1用一个一维数组S（设大小为MaxSize）作为两个栈的共享空间。请说明共享方法，栈满和栈空的判断条件，并用C/C+语言设计公用的初始化栈运算InitStack1(st)、判栈空运算StackEmpty1(st,i)、入栈运算Push(st,i,x)和出栈运算Pop(st,i,x)，其中i为1或2，用于表示栈好，x为入栈或出栈元素。2设