《数据结构栈与队列习题.docx》由会员分享，可在线阅读，更多相关《数据结构栈与队列习题.docx（9页珍藏版）》请在三一文库上搜索。
1、v1.0可编辑可修改第3章栈与队列一、单项选择题1 元素A E、C D依次进顺序栈后，栈顶元素是,栈底元素是A. AB. BC. CD. D2. 经过以下栈运算后，x的值是。InitStack(s) ; Push(s,a) ; Push(s,b) ; Pop(s,x) ； GetTop(s,x);A. aB.bC.1D.03. 已知一个栈的进栈序列是 ABC出栈序列为CBA经过的栈操作是。A. push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,pus
2、h,pop,pop4. 设一个栈的输入序列为 A、B、C D,A. A,B,C,DC. A,C,D,B5. 一个栈的进栈序列是a, b, c, d, e,A. edcbaC. dceab6. 已知一个栈的进栈序列是1, 2, 3,则第j个出栈元素是。A. iC. j-i+17. 已知一个栈的进栈序列是1, 2, 3,若p1= n,贝卩pi的值。A. iM 昔助一个栈所得到的序列是。B. D,C,B,AD. D,A,B,C则栈的不可能的输出序列是。B. decbaD. abcde,n，其输出序列的第一个元素是i ,B. n-iD.不确定,n,其输出序列是p1,p2,Pn,B. n-i7C. n-
3、i+1D.不确定8设n个元素进栈序列是1,2,3,，n,其输出序列是pi,p2,pn,若pi=3, 则P2的值。A. 定是2B.定是1C不可能是1D.以上都不对9. 设n个元素进栈序列是Pi,p 2,pn,其输出序列是1, 2, 3, ,n,若p3=1,则3的值。A.可能是2B.定是1C不可能是2D.不可能是310. 设n个兀素进栈序列是p1,p2,p n,其输出序列是1, 2, 3, ,n,若p3=3,贝卩p1的值。A.可能是2B.定是2C不可能是1D. 定是111. 设n个兀素进栈序列是p1,p2,p n,其输出序列是1, 2, 3, ,n,若pn=1,贝U pi(1 <i <
4、n-1)的值。n-iA. n-i+1C. iD.有多种可能12.判定一个顺序栈S为空的条件为A.=B. !=C. != +D. = = +13. 判定一个顺序栈S为栈满的条件是A.=B. =C. D.!=14. 链栈与顺序栈相比有一个明显的优点，即 。A.插入操作方便B通常不会出现栈满的情况C. 不会出现栈空的情况D.删除操作更加方便15. 最不适合用作链栈的链表是 。A.只有表头指针没有表尾指针的循环双链表B. 只有表尾指针没有表头指针的循环双链表C. 只有表尾指针没有表头指针的循环单链表D. 只有表头指针没有表尾指针的循环单链表16. 如果以链表作为栈的存储结构，则退链栈操作时 A.必须判
5、别链栈是否满C.必须判别链栈是否空17.向一个不带头结点的栈顶指针为行。A=s；C. s->next=1st;1st=s;B. 判别链栈元素的类型D. 对链栈不作任何判别1st的链栈中插入一个s所指结点时，则执1st- >n ext=s;B. s->next=1st->next;1st->nextD. s->next=1st;1st->next;18. 从一个不带头结点的栈顶指针为 S的链栈中删除一个结点时，用x保存被删除结点的值，则执行。A. x=S; S = S ->next;B. x= S ->data;C. S = S ->n
6、ext;x= S ->data;D. x= S ->data; S = S ->next;19. 经过以下队列运算后，队头的元素是 。In itQueue(qu);e nQueue(qu,a);e nQueue(qu,b);e nQueue(qu,c);deQueue(qu );B. bA. aC. 1D. 020. 经过以下队列的运算后，QueueEmpty(q)的值是。In itQueue(qu);e nQueue(qu,a);e nQueue(qu,b);deQueue(qu,x);deQueue(qu,y);A. aB. bC. 1D. 021. 元素A,B,C,D顺
7、序连续进入队列qu后，队头元素是，队尾元素B. BA. AC. CD. D22. 一个队列的入队序列为1,2,3,4，贝U队列可能的输出序列是 A. 4,3,2,1B. 1,2,3,4C. 1,4,3,2D. 3,2,4,1二、填空题1 .栈是一种具有 特性的线性表。2. 顺序栈和链栈的区别仅在于 不同。3. 如果栈的最大长度难以估计，则最好使用 。4. 一个栈的输入序列是1,2,3,4,5 ，则栈的输出序列1,2,3,4,5 是5. 若用不带头结点的单链表来表示链栈S,则创建一个空栈所要执行的操作6. 对于链栈S,进栈操作在端进行，出栈操作在 端进行7. 队列是一种具有特性的线性表。8. 顺
8、序队列和链队列的区别仅在于 的不同。9. 如果队列的最大长度难以估计，则最好使用 。三、判断题1. 顺序栈中元素值的大小是有序的。2. 在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。3. 栈顶元素和栈底元素有可能是同一个元素。4. 若用S1m表示顺序栈的存储空间，则对栈的进栈，出栈操作最多只能进行m次。5. 栈是一种对进栈，出栈操作总次数作了限制的线性表。6. 空栈没有栈顶指针。7. 栈和队列都是限制存取端的线性表。v1.0可编辑可修改8队列是一种对进队列，出队列操作的次序作了限制的线性表。9. n个元素进队列的顺序和出队列的顺序总是一致的。10顺序队中有多少元素，可以根据队首指针的
9、值和队尾指针的值来计算。11.若用“队头指针的值和队尾指针的值相等”作为环形顺序队为空的标志，则在设置一个空队列时，只需给队头指针和队尾指针赋同一个值，不管什么值 都可以。12无论是顺序队列，还是链队列，入队和出队操作的时间复杂度都是0(1)。13 .队列的输入序列为1,2,3,n ，输出序列为a1,a2,an,则 ai<ai+1 (1 w i Wn-1)四、简答题1有5个元素，其进栈次序为A,B,C,D,E,在各种可能的出栈次序中，以元素C,D 最先出栈(即C第一个且D第二个出栈)的次序有哪几个2设输入元素为1, 2, 3, P和A,入栈次序为1,2,3,P,A，元素经过栈后到达 输出
10、序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的 变量名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 (设大小为Max
11、Size)作为两个栈的共享空间。请说明共享 方法，栈满和栈空的判断条件，并用C/C+语言设计公用的初始化栈运算5v1.0可编辑可修改InitStackl(st) 、判栈空运算 StackEmpty1(st,i)、入栈运算 Push(st,i,x)和出栈运算Pop(st,i,x)，其中i为1或2,用于表示栈好，x为入栈或出栈2. 设计一个算法，利用栈的 InitStack( )、Push( ) > Pop()和 StackEmpty() 等基本运算返回指定栈中栈底元素。3. 用不带头结点的单链表存储链栈，设计初始化栈、判断栈是否为空、进栈和 出栈相应的算法。4. 在栈顶头结点为1st的链栈中，设计一个算法计算该栈中结点个数。9