栈和队列练习1
第三章栈和队列
一、选择题部分
1. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（C）。
（A） edcba（B）decba（C）dceab （D）abcde
2.栈结构通常采用的两种存储结构是（A）。
（A）线性存储结构和链表存储结构（B）散列方式和索引方式
（C）链表存储结构和数组（D）线性存储结构和非线性存储结构
3.判定一个顺序栈ST(最多元素为m0)为空的条件是（ B）。
（A） ST-〉top!=0 （B）ST-〉top==0
（C）ST-〉top!=m0 （D）ST-〉top=m0
4.判定一个栈ST(最多元素为m0)为栈满的条件是（ C）。
（A）ST-〉top!=0 （B）ST-〉top==0
（C）ST-〉top==m0（D）ST-〉top==m0-1
5.一个队列的入列序列是1,2,3,4,则队列的输出序列是（ B）。
（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1
6.循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear 则当前队列中的元素个数是（B ）
（A）(rear-front+m)%m （B） rear-front+1 （C）rear-front-1（D）rear-front
7.栈和队列的共同点是（C ）
（A）都是先进后出（B）都是先进先出
（C）只允许在端点处插入和删除元素（D）没有共同点
8.表达式a*(b+c)-d的后缀表达式是（B）。
（A）abcd*+-（B）abc+*d- （C）abc*+d-（D）-+*abcd
9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（C）
(A)a4，a3，a2，a1 (B)a3，a2，a4，a1
(C)a3，a1，a4，a2 (D)a3，a4，a2，a1
10.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际
位置是（ D ）
(A)rear－qulen (B)rear－qulen＋m
(C)m－qulen (D)（1＋rear＋m－qulen）% m
二、填空题部分
1.栈的特点是（先进后出）,队列的特点是（先进先出）。
2.线性表、栈和队列都是（线性）结构,可以在线性表的（任何）位置插入和删除元素，对于栈只能在（栈顶）插入和删除元素，对于队列只能在（队尾）插入元素和（队头）删除元素。
3.一个栈的输入序列是12345,则栈的输出序列12345是（可能的）。
4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳( 4 )个元素。
三. 选择题
1. 栈和队列的共同点是_C__
都是先进后出
都是先进先出
只允许在端点处插入和删除元素
没有共同点
2. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是
__C_
edcba
decba
dceab
abcde
3. 一个栈的入栈序列是1,2,3,4,则栈的可能的输出序列是__B_
1,4,2,3
2,1,4,3
4,2,1,3
4,2,3,1
4. 一个队列的入对序列是1,2,3,4,则队列的输出序列是_B___
4,3,2,1
1,2,3,4
1,4,3,2
3,2,4,1
5. 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为
p1,p2,p3,…,pn,若p1=n,则pi为___C_
I
n=I
n-I+1
不确定
6. 表达式a*(b+c)-d的后缀表达式是__B_
abcdd+-
abc+*d-
abc*+d-
-+*abcd
7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行_C___
HS->next=s;
s->next=HS->next;HS->next=s;
s->next=HS;HS=s;
s->next=HS;HS=HS->next;
8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行___D_
x=HS;HS=HS->next;
x=HS->data;
HS=HS->next;x=HS->data;
x=HS->data;HS=HS->next;
四、填空题
1、在一个具有n个单元的顺序栈中，假设以地址低端（即下标为1的单元）作为栈底，以top作为栈顶指针，则当做堆栈处理时，top变化为 top++ 。
2、在一个具有n个单元的顺序栈中，假设以地址高端（即下标为n 的单元）作为栈底，以top作为栈顶指针，则当作退栈处理时，top变化为 top++ 。
3、在一个循环队列中，队首指针指向队首元素的实际地
址。
4、从循环队列中删除一个元素时，其操作是
Q.front=(Q.front+1) % MAXSIZE
。
5、在具有n个单元的循环队列中，队满时共有 n-1 个元素。
6、一个栈的输入序列是1,2,3,4,5,则栈的输出序列4,3,5,1,2是
不可能的。
7、一个栈的输入序列是1,2,3,4,5,则栈的输出序列1,2,3,4,5是
可能的。
数据结构习题集：第3章栈和队列
第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队 列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队 列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素， 再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; C 、s->next=Q.rear；Q.rear=s; D 、s->next=Q.front；Q.front=s; 14.在一个链队列Q 中，删除一个结点需要执行的指令是（） A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next;
栈和队列练习1
第三章栈和队列 一、选择题部分 1. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（C）。 （A） edcba（B）decba（C）dceab （D）abcde 2.栈结构通常采用的两种存储结构是（A）。 （A）线性存储结构和链表存储结构（B）散列方式和索引方式 （C）链表存储结构和数组（D）线性存储结构和非线性存储结构 3.判定一个顺序栈ST(最多元素为m0)为空的条件是（ B）。 （A） ST-〉top!=0 （B）ST-〉top==0 （C）ST-〉top!=m0 （D）ST-〉top=m0 4.判定一个栈ST(最多元素为m0)为栈满的条件是（ C）。 （A）ST-〉top!=0 （B）ST-〉top==0 （C）ST-〉top==m0（D）ST-〉top==m0-1 5.一个队列的入列序列是1,2,3,4,则队列的输出序列是（ B）。 （A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1 6.循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear 则当前队列中的元素个数是（B ） （A）(rear-front+m)%m （B） rear-front+1 （C）rear-front-1（D）rear-front 7.栈和队列的共同点是（C ） （A）都是先进后出（B）都是先进先出 （C）只允许在端点处插入和删除元素（D）没有共同点 8.表达式a*(b+c)-d的后缀表达式是（B）。 （A）abcd*+-（B）abc+*d- （C）abc*+d-（D）-+*abcd 9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（C） (A)a4，a3，a2，a1 (B)a3，a2，a4，a1 (C)a3，a1，a4，a2 (D)a3，a4，a2，a1 10.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际
数据结构练习题及答案
数据结构练习题（一） 一、单选题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( )。 A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中( )是非线性结构。 A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)， 每个元素占一个空间，问A[3][3](10)存放在（）位置。脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( )。 A．2k-1 +1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( )。 A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个。 A．1 B．2 C．3 D．4 9.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
二、填空题 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为 __________个，树的深度为___________，树的度为_________。 4.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 5.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 6.AOV网是一种___________________的图。 7.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 9.在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、计算题 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 605078903440 next3572041 2.
数据结构复习模拟题1
第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（ B. 后进先出）。 2. 在作进栈运算时,应先判别栈是否(①B. 满),在作退栈运算时应先判别栈是否(②A. 空)。当栈中元素为n个,作进栈运算时发 生上溢,则说明该栈的最大容量为(③B. n)。为了增加内存空间的利用率和减少溢 出的可能性,由两个栈共享一片连续的内 存空间时,应将两栈的 (④D. 栈底)分别 设在这片内存空间的两端,这样,当(⑤C. 两个栈的栈顶在栈空间的某一位置相遇)时，才产生上溢。 3. 一个栈的输入序列为123…n，若输出 序列的第一个元素是n，输出第i （1<=i<=n）个元素是（B. n-i+1）。 4. 若一个栈的输入序列为1,2,3,…,n， 输出序列的第一个元素是i，则第j个输 出元素是（D. 不确定的）。 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是(D. 不确定)。 6. 有六个元素6，5，4，3，2，1 的顺序 进栈，问下列哪一个不是合法的出栈序列？（C. 3 4 6 5 2 1） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（D. 4，3，1，2，）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下 列序列中不可能是栈的输出序列的是（B. 5 4 1 3 2）。 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的 是（D. 3 2 1 5 4）。 10. 某堆栈的输入序列为a, b，c ，d,下 面的四个序列中，不可能是它的输出序列 的是（D. d, c，a，b）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 11. 设abcdef以所给的次序进栈，若在进 栈操作时，允许退栈操作,则下面得不到的 序列为（D. cabdef）。 A．fedcba B. bcafed C. dcefba D. cabdef 12. 设有三个元素X，Y，Z顺序进栈（进 的过程中允许出栈），下列得不到的出栈排 列是(C. ZXY)。 A．XYZ B. YZX C. ZXY D. ZYX 13.输入序列为ABC，可以变为CBA时，经 过的栈操作为 （B. push,push,push,pop,pop,pop） 14. 若一个栈以向量V[1..n]存储，初始 栈顶指针top为n+1，则下面x进栈的正 确操作是(C. top:=top-1; V [top]:=x)。 15. 若栈采用顺序存储方式存储，现两栈 共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底 在V[m]，则栈满的条件是（B. top[1]+1=top[2]）。 16. 栈在（A. 递归调用B. 子程序调用C. 表达式求值）中应用。 17. 一个递归算法必须包括（B. 终止条件 和递归部分）。 18. 执行完下列语句段后，i值为：（B. 4）int f(int x) { return ((x>0) ? x* f(x-1):2);} int i; i =f(f(1)); 19. 表达式a*(b+c)-d的后缀表达式是(D. -+*abcd)。20. 表达式3* 2^(4+2*2-6*3)-5求值过程 中当扫描到6时，对象栈和算符栈为 （ D. 3,2,8；(*^( ），其中^为乘幂。 21. 设计一个判别表达式中左，右括号是 否配对出现的算法，采用（D. 栈）数据结 构最佳。 22. 用链接方式存储的队列，在进行删除 运算时（D. 头、尾指针可能都要修改）。 23. 用不带头结点的单链表存储队列时, 其队头指针指向队头结点,其队尾指针指 向队尾结点，则在进行删除操作时 (D. 队头,队尾指针都可能要修改)。 24. 递归过程或函数调用时，处理参数及 返回地址，要用一种称为（C．栈）的数据 结构。 25. 假设以数组A[m]存放循环队列的元素, 其头尾指针分别为front和rear，则当前 队列中的元素个数为 （A．(rear-front+m)%m）。 26. 循环队列A[0..m-1]存放其元素值， 用front和rear分别表示队头和队尾，则 当前队列中的元素数是 (A. (rear-front+m)%m)。 27. 循环队列存储在数组A[0..m]中，则 入队时的操作为（ D. rear=(rear+1)mod(m+1) ）。 28. 若用一个大小为6的数组来实现循环 队列，且当前rear和front的值分别为0 和3，当从队列中删除一个元素，再加入 两个元素后，rear和front的值分别为多 少？(B. 2和4 ) 29. 已知输入序列为abcd 经过输出受限 的双向队列后能得到的输出序列有（B. cadb D. bdac）。 30. 若以1234作为双端队列的输入序列， 则既不能由输入受限的双端队列得到，也 不能由输出受限的双端队列得到的输出序 列是(C. 4231 )。 31. 最大容量为n的循环队列，队尾指针 是rear，队头是front，则队空的条件是 （B. rear=front）。 32. 栈和队列的共同点是（C. 只允许在端 点处插入和删除元素）。 33. 栈的特点是（①B. 后进先出）,队列 的特点是（②A. 先进先出）,栈和队列都 是（③C.限制存取点的线性结构）。若进栈 序列为1,2,3,4 则（④C. 4,2,3,1）不可 能是一个出栈序列（不一定全部进栈后再 出栈）；若进队列的序列为1,2,3,4 则（⑤ F. 1,2,3,4）是一个出队列序列。 34. 栈和队都是（C. 限制存取点的线性结 构） 35. 设栈S和队列Q的初始状态为空，元 素e1，e2，e3，e4,e5和e6依次通过栈S， 一个元素出栈后即进队列Q，若6个元素 出队的序列是e2，e4，e3,e6,e5,e1则栈 S的容量至少应该是(C. 3)。 36. 用单链表表示的链式队列的队头在链 表的（A．链头）位置。 37. 依次读入数据元素序列{a，b，c，d， e，f，g}进栈,每进一个元素，机器可要求 下一个元素进栈或弹栈，如此进行，则栈 空时弹出的元素构成的序列是以下哪些序 列（ A．{d ，e，c，f，b，g，a} D. {c， d，b，e，f，a，g} ） 二判断题 1. 消除递归不一定需要使用栈，此说法 （√） 2. 栈是实现过程和函数等子程序所必需 的结构。（√） 3. 两个栈共用静态存储空间，对头使用也 存在空间溢出问题。（√） 4．两个栈共享一片连续内存空间时，为提 高内存利用率，减少溢出机会，应把两个 栈的栈底分别设在这片内存空间的两端。 （√） 5. 即使对不含相同元素的同一输入序列 进行两组不同的合法的入栈和出栈组合操 作，所得的输出序列也一定相同。（×） 6. 有n个数顺序（依次）进栈，出栈序列 有Cn种，Cn=[1/（n+1）]* （2n）!/[(n!)*(n!)]。（√） 7. 栈与队列是一种特殊操作的线性表。 （√） 8. 若输入序列为1,2,3,4,5,6,则通过一 个栈可以输出序列3,2,5,6,4,1. （√） 9. 栈和队列都是限制存取点的线性结构。 （√） 10．若输入序列为1，2，3，4，5，6，则 通过一个栈可以输出序列1，5，4，6，2， 3。（×） 11. 任何一个递归过程都可以转换成非递 归过程。（√） 12. 只有那种使用了局部变量的递归过程 在转换成非递归过程时才必须使用栈。 （×） 13. 队列是一种插入与删除操作分别在表 的两端进行的线性表，是一种先进后出型 结构。（×） 14. 通常使用队列来处理函数或过程的调 用。（×） 15. 队列逻辑上是一个下端和上端既能增 加又能减少的线性表。（√） 16. 循环队列通常用指针来实现队列的头 尾相接。（×） 17. 循环队列也存在空间溢出问题。（√） 18. 队列和栈都是运算受限的线性表，只 允许在表的两端进行运算。（×） 19. 栈和队列都是线性表，只是在插入和 删除时受到了一些限制。（√） 20. 栈和队列的存储方式，既可以是顺序 方式，又可以是链式方式。（√） 三填空题 1．栈是操作受限（或限定仅在表尾进行 插入和删除操作）的线性表，其运算遵循 后进先出的原则。 2．_栈_是限定仅在表尾进行插入或删除操 作的线性表。 3. 一个栈的输入序列是：1，2，3则 不可能的栈输出序列是__3 1 2__。 4. 设有一个空栈，栈顶指针为1000H(十 六进制)，现有输入序列为1，2，3，4，5， 经过 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之 后，输出序列是__2 3_，而栈顶指针值是 _100CH_。设栈为顺序栈，每个元素占4个 字节。 5. 当两个栈共享一存储区时，栈利用一维 数组stack(1,n)表示，两栈顶指针为 top[1]与top[2]，则当栈1空时，top[1] 为_0_，栈2空时，top[2]为_n+1_，栈满 时为_ top[1]+1=top[2]_。 6．两个栈共享空间时栈满的条件__两栈顶 指针值相减的绝对值为1（或两栈顶指针 相邻）_。 7．在作进栈运算时应先判别栈是否_(1)_; 在作退栈运算时应先判别栈是否_(2)_；当 栈中元素为n个，作进栈运算时发生上溢， 则说明该栈的最大容量为_(3)_。为了增加 内存空间的利用率和减少溢出的可能性， 由两个栈共享一片连续的空间时，应将两 栈的_(4)_分别设在内存空间的两端，这样 只有当_(5)_时才产生溢出。 (1)满 (2) 空 (3)n (4)栈底 (5)两栈顶指针相邻 （即值之差的绝对值为1） 8. 多个栈共存时，最好用_链式存储结构_ 作为存储结构。 9．用S表示入栈操作，X表示出栈操作， 若元素入栈的顺序为1234，为了得到1342 出栈顺序，相应的S和X的操作串为 _ S×SS×S××_。 10. 顺序栈用data[1..n]存储数据，栈顶 指针是top,则值为x的元素入栈的操作是 _ data[++top]=x；_。 11．表达式 23+((12*3-2)/4+34*5/7)+108/9的后缀 表达式是 _23.12.3*2-4/34.5*7/++108.9/+（注：表 达式中的点(.)表示将数隔开，如23.12.3 是三个数）_。 12. 循环队列的引入，目的是为了克服_ 假溢出时大量移动数据元素_。 13．用下标0开始的N元数组实现循环队 列时，为实现下标变量M加1后在数组有 效下标范围内循环，可采用的表达式是：M： =__(M+1) MODN（填PASCAL语言，C语言 的考生不填）； M= (M+1)% N （填C语言， PASCAL语言的考生不填）。 14．_队列_又称作先进先出表。 15. 队列的特点是_先进先出_。 16．队列是限制插入只能在表的一端，而 删除在表的另一端进行的线性表，其特点 是_先进先出_。 17. 已知链队列的头尾指针分别是f和r， 则将值x入队的操作序列是_ s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s； r=s；_。 18．区分循环队列的满与空，只有两种方 法，它们是_牺牲一个存储单元和_设标记 _。 19．设循环队列用数组A[1..M]表示，队 首、队尾指针分别是FRONT和TAIL，判定 队满的条件为_（TAIL+1）MOD M=FRONT (数 组下标0到M-1，若一定使用1到M，则取 模为0者，值改取M) 。 20. 设循环队列存放在向量sq.data[0:M] 中，则队头指针sq.front在循环意义下的 出队操作可表示为_ sq.front=(sq.front+1)%(M+1)； return(sq.data(sq.front)) ；，若用牺牲 一个单元的办法来区分队满和队空（设队 尾指针sq.rear）,则队满的条件为 _(sq.rear+1)%(M+1)==sq.front ；_。 21．表达式求值是_栈_应用的一个典型例 子。 22．循环队列用数组A[0..m-1]存放其元 素值，已知其头尾指针分别是front和 rear ，则当前队列的元素个数是 （rear-front+m）% m；。 23．设Q[0..N-1]为循环队列，其头、尾 指针分别为P和R，则队Q中当前所含元 素个数为_（R-P+N）% N _。
栈和队列
第三章栈和队列练习题 一、单项选择题 1．一个顺序栈一旦被声明，其占用空间的大小（）。 A．已固定B．可以改变C．不能固定D．动态变化 2．链栈和顺序栈相比，有一个比较明显的缺点，即（）。 A．插入操作更加方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 3．用单链表表示的链式队列的队头在链表的（）位置。 A．链头B．链尾C．链中D．任意位置 4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。 A．堆栈B．队列C．数组D．先性表 5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…p n，若p1=30，则p10为（）。 A．11 B．20 C．19 D．21 6．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（）。 A．（rear+1)%m=front B．rear =front+1 C．rear=front D．（rear+1)%m-1=front 7．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。 A．top->next=p; B．p->next=top->next; top->next=p; C．p->next=top; top=p; D．p->next=top->next; top=top->next; 8．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。 A．x=top;top=top->next; B．x=top->data;
计算机学科专业基础综合数据结构-栈、队列和数组(一)
计算机学科专业基础综合数据结构-栈、队列和数组(一) (总分：92.00，做题时间：90分钟) 一、单项选择题(总题数：26，分数：52.00) 1.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i(1＜=i＜=n)个元素是 ____ 。（分数： 2.00） A.不确定 B.n-i+1 √ C..i D.n-i 解析：按照堆栈“后进先出”的特点，n是最后一个入栈的，即n为栈顶元素。若输出的第一个元素为n，则其余所有元素必定仍在堆栈中。第一个输出元素为n，则第二个输出元素为n-1，第i个输出元素为n-i+1，最后一个(第n个)输出元素为1。 2.有六个元素6，5，4，3，2，1的顺序进栈，下列 ____ 不是合法的出栈序列。 （分数：2.00） A.5 4 3 6 1 2 B.4 5 3 1 2 6 C.3 4 6 5 2 1 √ D.2 3 4 1 5 6 解析：考查堆栈“后进先出”的特点。对选项A来说，第一个出栈元素是5，因为6先于5进栈，所以必定在5之后出栈，其余的元素出栈顺序任意；对选项B来说，第一个出栈元素是4，所以5和6两个元素必定在4之后依次出栈；对选项C来说，第一个出栈元素是3，则必有4、5、6三个元素依次在3后面出栈，但是选项C中的顺序是3、4、6、5，这是不符合要求的；对选项D来说，第一个出栈元素是2，则必有3、4、5、6依次在2后面出栈，D也是符合要求的，因此答案选C。 总结：这种问题如何解决呢?我们看第一个出栈元素，然后确定先于第一个元素进栈的所有其他元素，这些元素一定在第一个出栈元素之后顺序出栈。如果第一个元素仍然无法判断出来，可继续看后面的元素，依次类推。举例如下： 假设第一个出栈的元素是1，则出栈顺序一定是6、5、4、3、2、1，没有其他情况。 假设第一个出栈的元素是2，则出栈顺序可能有： 213456；231456；234156；234516‘； 234561 (可首先把23456写出，然后可将1插到2之后的任意位置) 假设第一个出栈的元素是3，则出栈顺序可能有： 3 12 456；3 4 12 56； 34 5 12 6； 345 6 12 但是314526是不能的。因为3出栈之后，当前栈中仍有4、5、6三个元素，如果下一个是1出栈，则肯定先让2进栈，再让1进栈，然后1出栈，此时栈顶就变成2了，则下一个出栈的只能是2，而不能是4。3.若一个栈的输入序列为1，2，3，…，n，输出序列的第一个元素是i，则第j个输出元素是 ____ 。（分数：2.00） A.i-j-1 B.i-j C.j-i+1 D.不确定的√ 解析：不知道i，j的大小关系，所以无法确定。 4.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时 ____ 。 （分数：2.00） A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都要修改
数据结构栈和队列习题及答案
习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式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；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front
栈与队列复习题
栈与队列复习题 栈与队列复习 1．设有一顺序栈S，元素s1,s2,s3,s4,s5,s6 依次进栈，如果6个元素出栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是（）。 A．2 B．3 C．4 D．5 2．若借助堆栈将中缀表达式a+b*c+(d*e+f)*g 转换为后缀表达式，当读入‘f’时，堆栈里的内容是什么(按堆栈自底向上顺序)? A． +（+ B． +（*+ C． abcde a b c * + d e * f + g* + D． +*+(*+ 3．一个栈的入栈序列是1，2，3，4，5，则栈的不可能输出序列是（ D ）。 A．3，5，4，2，1 B．3，2，4，5，1 C．1，2，3，4，5 D．5，4，3，1，2 4．表达式a*(b+c)-d的后缀表达式是（） A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd 5．一个队列的入队序列是1，3，5，7，9，则出队的输出序列只能是（ B ） A．9，7，5，3，1 B．1，3，5，7，9 C．1，5，9，3，7 D．9，5，1，7，3 6．、设循环队列中数组的下标范围是1～n，其头尾指针分别为f 和r，则其元素个数为（D） A．r-f B. r-f+1 C. (r-f)% n+1 D. (r-f+n)% n 7．设数组data[m]
作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行入队操作后其尾指针rear值为（D ） A. rear=rear+1 B. rear=(rear-1)%m C. rear=(rear+1)%(m-1) D. rear=(rear+1)%m 8．两个栈共享一片连续的内存空间时，为提高内存利用率，减少溢出机会，应把2个栈的栈底分别设在这片内存空间的两端。（对/错） 9、递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组C．栈 D. 线性表 10、若用大小为6的数组来实现循环队列，且当前front和rear 的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？ A．2和6 B．2和0 C．2和6 D．2和2 11．设有编号1，2，3，4的4辆车，顺序进一个栈式结构的站台，试写出这4辆车开出车站的所有可能的顺序。（略） 12．栈的逻辑特点是（LIFO ），队列的特点是（FIFO），举例说明。 13．循环队列的优点是（解决“假溢出”的一种方法，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题），用（front == rear ）判断队列空，用（front == (rear+1) % MAXSIZE）判断队列满。14．栈与队列都是（线性）结构，栈只能在（栈顶）插入和删除元素；队列只能在（队尾）插入元素，在（队头）删除元素。 15．设以顺序循环队列存放元素，设变量rear、front分别做队首、队尾指针，写出入队、出队的算法。（略）
数据结构(Java)复习题及答案 3栈和队列
第4章栈和队列 一、填空题 1.向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的前一个位置。 5. 在具有n个单元的循环队列中，队满时共有n-1个元素。 6. 向栈中压入元素的操作是先移动栈顶指针，后存入元素。 7. 从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。 二、判断正误（判断下列概念的正确性，并作出简要的说明。） （×）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。（×）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU中也用队列。 （√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （×）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 （×）6. 栈和队列是一种非线性数据结构。
错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）8*. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （B）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （B）2. 判定一个栈ST（最多元素为m0）为空的条件是 Ａ．ST→top<>0 Ｂ．ST→top=-1 Ｃ．ST→top<>m0 Ｄ．ST→top=m0 四、简答题 1. 说明线性表、栈与队的异同点。 答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。 不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。 2*.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。
栈和队列练习题
栈和队列练习题
选择题： 1、设abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ D ）。 A．fedcba B. bcafed C. dcefba D. cabdef 2、若已知一个栈的入栈序列是 1,2,3,…,n，其输出序列为 p1,p2,p3，…，pN,若pN 是 n，则 pi 是( D )。 A. i B. n-i C. n-i+1 D. 不确定 3、设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 4、用链接方式存储的队列，在进行删除运算时（ D ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 5、递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 6、假设以数组 A[m]存放循环队列的元素,其头尾指针分别为 front 和rear，则当前队列中的元素个数为（ A ）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 7、若用一个大小为 6的数组来实现循环队列，且当前 rear和 front 的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？( B ) A. 1 和 5 B. 2 和4 C. 4 和2 D. 5 和1 8、最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是（ A ）。 A. (rear+1) MOD n=front B. rear=front C．rear+1=front D. (rear-l) MOD n=front 9、栈和队列的共同点是（ C ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 10、设栈S和队列 Q 的初始状态为空，元素 e1，e2，e3，e4,e5 和e6 依次通过栈 S，一个元素出栈后即进队列 Q，若 6 个元素出队的序列是 e2，e4，e3,e6,e5,e1 则栈 S 的容量至少应该是( C )。 A． 6 B. 4 C. 3 D. 2 判断题： 栈和队列都是限制存取点的线性结构。（） 消除递归不一定需要使用栈，此说法（） 任何一个递归过程都可以转换成非递归过程。（） 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两
线性表、栈和队列习题
第2章线性表 一选择题 1．下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 3. 链表不具有的特点是（ B ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ B ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ D ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ B ）A．O（i） B．O（1） C．O（n） D．O（i-1） 7．在双向链表指针p的结点前插入一个指针q的结点操作是（ C ）。 A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink; C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; 8．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ B ）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 9．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、填空 1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用___顺序____存储结构。 2．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data 为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:__py->next=px->next_____； px->next=py______; 3．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_____n-i+1___个元素。 4．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_____O(1)___,在给定值为x的结点后插入一个新结点的时间复杂度为____O(1)____。 5.顺序存储结构是通过____下标____表示元素之间的关系的;链式存储结构是通过__指针______表示元素之间的关系的。 6. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ____4__个，单链表为
栈和队列习题
栈和队列习题 第三章栈和队列 1.栈的特点是(),队列的特点是(). A.先进先出 B.先进后出 2.栈和队列的共同点是(). A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 3.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是(). A.edcba B.decba C.dceab D.abcde 4.若已知一个栈的进栈序列是1,2,3,……,n,其输出序列为p1,p2,p3,……,p n。若p1=n,则p i(1≤i
A.可能是2 B.不可能是2 C.可能是1 D.一定是1 7. 若已知一个栈的进栈序列是p1,p2,p3,……,p n,其输出序列为1,2,3,……,n。若p3=1,则p1为(). A.可能是2 B.一定是2 C.不可能是2 D.不可能是3 8.若已知一个栈的进栈序列是p1,p2,p3,……,p n,其输出序列为1,2,3,……,n。若p n=1,则p i(1≤i