数据结构第3章 栈与队列习题.doc

第3章 栈与队列一、单项选择题1元素A、C、D依次进顺序栈后，栈顶元素是 ，栈底元素是 。AA BBCCDD2经过以下栈运算后，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,B DD,A,B,C5一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 。Aedcba Bdecba CdceabDabcde6已知一个栈的进栈序列是1，2，3，,n，其输出序列的第一个元素是i，则第j个出栈元素是 。Ai Bn-iCj-i+1D不确定7已知一个栈的进栈序列是1，2，3，n，其输出序列是p1,p2,Pn，若p1=n，则pi的值 。AiBn-iCn-i+1D不确定8设n个元素进栈序列是1，2，3，n，其输出序列是p1,p2,pn，若p1=3,则p2的值 。A一定是2B一定是1C不可能是1D以上都不对9设n个元素进栈序列是p1,p2,pn，其输出序列是1，2，3，n，若p3=1,则p1的值 。A可能是2B一定是1C不可能是2D不可能是310设n个元素进栈序列是p1,p2,pn，其输出序列是1，2，3，n，若p3=3,则p1的值 。A可能是2B一定是2C不可能是1D一定是111设n个元素进栈序列是p1,p2,pn，其输出序列是1，2，3，n，若pn=1,则pi(1in-1)的值 。An-i+1 Bn-iCiD有多种可能12判定一个顺序栈S为空的条件为 。AS.top= =S.baseBS.top!= S.baseCS.top!= S.base+S.stacksizeDS.top= = S.base+S.stacksize 13判定一个顺序栈S为栈满的条件是 。AS.top-S.base= =S.stacksizeBS.top= = S.baseCS.top-S.base!=S.stacksizeDS.top!= 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的链栈中删除一个结点时，用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);Aa BbC1 D020经过以下队列的运算后，QueueEmpty(q) 的值是 。InitQueue(qu);enQueue(qu,a);enQueue(qu,b);deQueue(qu,x);deQueue(qu,y);Aa BbC1 D021元素A,B,C,D顺序连续进入队列qu后，队头元素是 ，队尾元素是 。AA BBCC DD22一个队列的入队序列为1,2,3,4，则队列可能的输出序列是_.A4,3,2,1B1,2,3,4C1,4,3,2 D3,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顺序栈中元素值的大小是有序的。2在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。3栈顶元素和栈底元素有可能是同一个元素。4若用S1m表示顺序栈的存储空间，则对栈的进栈，出栈操作最多只能进行m次。5栈是一种对进栈，出栈操作总次数作了限制的线性表。6空栈没有栈顶指针。7栈和队列都是限制存取端的线性表。8队列是一种对进队列，出队列操作的次序作了限制的线性表。9n个元素进队列的顺序和出队列的顺序总是一致的。10顺序队中有多少元素，可以根据队首指针的值和队尾指针的值来计算。11若用“队头指针的值和队尾指针的值相等”作为环形顺序队为空的标志，则在设置一个空队列时，只需给队头指针和队尾指针赋同一个值，不管什么值都可以。12无论是顺序队列，还是链队列，入队和出队操作的时间复杂度都是O(1)。13队列的输入序列为1,2,3,n，输出序列为a1,a2,an, 则aiai+1(1in-1) 四、简答题1有5个元素，其进栈次序为A,B,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，用于表示栈