第三章栈和队列习题-数据结构
习题三栈和队列
一单项选择题
1.在作进栈运算时,应先判别栈是否(①),在作退栈运算时应先判别栈
是否(②)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大
容量为(③)。
①,②:A.空B.满C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2
2．若已知一个栈的进栈序列是1，2，3，，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为()。
A可能是2B一定是2C可能是1D一定是1
3.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合
法的出栈序列？（）
A.543612
B.453126
C.346521
D.2341564.设有一顺序栈S，元素
1,2,3,4,5,6依次进栈，如果6个元素出栈的顺序是2,3,4,6,5,1,则栈的
容量至少应该是（）
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]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]6.执行
完下列语句段后，i值为：（）
intf(int某)
{return((某>0)某某f(某-1):2);}inti;i=f(f(1));
A．2B.4C.8D.无限递归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）%mC.rear=(rear+1)%(m+1)D.front=(front+1)%(m+1)11.循环队列的队满条件为()
A.(q.rear+1)%ma某ize==(q.front+1)%ma某ize;
B.(q.front+1)%ma 某ize==q.rear
C.(q.rear+1)%ma某ize==q.front
D.q.rear==q.front
12.栈和队列的共同点是（）。
A.都是先进先出
B.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
二、填空题
1．栈是_______的线性表，其运算遵循_______的原则。
2.一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。
3．用S表示入栈操作，某表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和某的操作串为_______。
4.循环队列的引入，目的是为了克服_______。5．队列是限制插入只
能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。
6.已知链队列的头尾指针分别是f和r，则将值某入队的操作序列是
_______。
7．表达式求值是_______应用的一个典型例子。
8．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别
是front和rear，则当前队列的元素个数是_______。
9.以下运算实现在链栈上的初始化，请在________________处用请适
当句子予以填充。
VoidInitStacl(LtackTp某l){________________;}
10.`以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。
VoidPuh（LStackTp某l,DataType某）
{LtackTp某p;p=malloc(izeof(LtackTp));________________;p->ne
某t=l;
________________;}
11．以下运算实现在链栈上的退栈，请在________________处用请适当句子予以填充。
IntPop(LtackTp某l,DataType某某){LtackTp某
p;if(l!=NULL){p=l;
某某=________________;l=l->ne某t;
________________;return(1)；}elereturn(0);
}
12.以下运算实现在链队上的入队列，请在________________处用适当句子予以填充。
VoidEnQueue(QueptrTp某lq,DataType某){LqueueTp某p;
p=(LqueueTp某)malloc(izeof(LqueueTp));________________=
某;p->ne某t=NULL;
(lq->rear)->ne某t=________________;________________;
}
三、应用题
1．给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？
2.画出对算术表达式A-B某C/D-E↑F求值时操作数栈和运算符栈的变化过程。
3.将两个栈存入数组V[1..m]应如何安排最好？这时栈空、栈满的条件是什么？
4.怎样判定循环队列的空和满？
四、算法设计题
1．借助栈(可用栈的基本运算)来实现单链表的逆置运算。
2.设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：E某Y某(E);(注：算法中可调用栈操作的基本算法。)
3.假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，
入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序
列为合法序列，否则称为非法序列。（1）下面所示的序列中哪些是合法的？
A.IOIIOIOO
B.IOOIOIIO
C.IIIOIOIO
D.IIIOOIOO
（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否
合法。若合法，返回
true，否则返回fale（假定被判定的操作序列已存入一维数组中）。
4.设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..ma
某ize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面
增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。
5.请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,某):元素某入ST栈；POP(ST,某)：ST栈顶元素出栈，赋给
变量某；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现
该队列的三个运算：enqueue:插入一个元素入队列；dequeue:删除一个元
素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）
6．要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。
7.已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，编写一个算法，将队列Q中的所有元素逆置。栈的ADT 函数有：
makeEmpty(:tack);置空栈
puh(:tack;value:datatype);新元素value进栈
pop(:tack):datatype;出栈，返回栈顶值iEmpty(:tack):Boolean;判栈空否队列的ADT函数有：
enqueue(q:queue:value:datatype);deQueue(q:queue):datatype;iE mpty(q:queue):boolean;元素value进队出队列，返回队头值判队列空否第3章栈和队列
一单项选择题1.BAB2．A3.C4.B5.B6.B7.D8.D9.C10．D11.C12.C
二、填空题
1．操作受限（或限定仅在表尾进行插入和删除操作）后进先出2.312 3．S某SS某S某某
4.假溢出时大量移动数据元素5．先进先出
6.=(LinkedLit)malloc(izeof(LNode))；->data=某;->ne某t=r->ne
某t；r->ne某t=；
r=；7．栈8．（rear-front+m）%m；9．l=NULL
10．p->data=某,l=p11．p->data,free(p)
12．p->data,p,lq->rear=p
三、应用题1．【解答】（1）顺序栈（top用来存放栈顶元素的下标）
判断栈S空：如果S->top==-1表示栈空。
判断栈S满：如果S->top==Stack_Size-1表示栈满。
(2)链栈（top为栈顶指针，指向当前栈顶元素前面的头结点）判断
栈空：如果top->ne某t==NULL表示栈空。
判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。
2.设操作数栈是opnd，操作符栈是optr，对算术表达式A-B某C/D-
E↑F求值，过程如下：步骤opnd栈初始123AAABoptr栈输入字符###-#-
A-B某C/D-E↑F#A-B某C/D-E↑F#-B某C/D-E↑F#B某C/D-E↑F#主要操
作PUSH(OPTR,’#’)PUSH(OPND,A)PUSH(OPTR,’-’)PUSH(OPND,B)
第三章栈、队列和数组 一、名词解释： 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题： 1.栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶 进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________ 或________。 2.栈的基本运算至少应包括________、________、________、________、________五 种。 3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6.top=0表示________，此时作退栈运算，则产生“________”； top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。 7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________; return(1);} 8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x)
第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;
第3章栈与队列 一、单项选择题 1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。 A．A B．B C．C D．D 2．经过以下栈运算后，x的值是。 InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x); A．a B．b C．1 D．0 3．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 4．设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的序列是。 A．A,B,C,D B．D,C,B,A C．A,C,D,B D．D,A,B,C 5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。 A．edcba B．decba C．dceab D．abcde 6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。 A．i B．n-i C．j-i+1 D．不确定 7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若p1=n，则pi的值。 A．i B．n-i C．n-i+1 D．不确定
8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p 1,p 2 ,…,p n ，若p 1 =3, 则p 2 的值。 A．一定是2 B．一定是1 C．不可能是1 D．以上都不对 9．设n个元素进栈序列是p 1,p 2 ,…,p n ，其输出序列是1，2，3，……，n，若p 3 =1, 则p 1 的值。 A．可能是2 B．一定是1 C．不可能是2 D．不可能是3 10．设n个元素进栈序列是p 1,p 2 ,…,p n ，其输出序列是1，2，3，……，n，若 p 3=3,则p 1 的值。 A．可能是2 B．一定是2 C．不可能是1 D．一定是1 11．设n个元素进栈序列是p 1,p 2 ,…,p n ，其输出序列是1，2，3，……，n，若 p n =1,则p i (1≤i≤n-1)的值。 A．n-i+1 B．n-i C．i D．有多种可能 12．判定一个顺序栈S为空的条件为。 A．= = B．!= C．!= + D．= = + 13．判定一个顺序栈S为栈满的条件是。 A． = B．= = C．D．!= 14．链栈与顺序栈相比有一个明显的优点，即。 A．插入操作方便B．通常不会出现栈满的情况C．不会出现栈空的情况D．删除操作更加方便15．最不适合用作链栈的链表是。 A．只有表头指针没有表尾指针的循环双链表
第三章栈和队列 一、单项选择题 参考答案： 1. A 2. B 3. C 4. A 5. B 6. B 7. D 8. D 9. C 10. A 11. D 12. A 13. A 14. D 15. C 二、填空题 参考答案： 1. 先进后出 2. 先进先出 3. 队尾，队头 4. 栈顶指针 5. 栈顶指针 6. MaxSize-1 7. top==0 8. 空栈 9. 栈顶指针10. p->link=top，top=p 11. top=top->link 12. Q.front==Q.rear 13. (Q.rear+1)%MaxSize==Q.front 14. 队尾指针15. 空，只含有一个结点 16. front == rear && front != NULL或者front == rear && rear != NULL 17. 两端18. 3x2+*5- 19. 15 20. 3 三、判断题 参考答案： 1. 是 2. 是 3. 否 4. 是 5. 是 6. 否 7. 否 8. 是 9. 否10. 否 11. 否12. 是13. 否14. 是15. 否 16. 否 四、运算题 参考答案： 1.根据以上规则，给出计算中缀表达式a + b * c – d / e时两个栈的变化。 步扫描项项类型动作OPND栈OPTR栈 0 OPTR栈与OPND栈初始化, ‘#’ 进OPTR栈, # 取第一个符号 1 a 操作数a进OPND栈, 取下一符号 a # 2 + 操作符icp (‘+’ ) > isp (‘#’ ), 进OPTR栈, 取 a # + 下一符号 3 b 操作数b进OPND栈, 取下一符号 a b # + a b # + * 4 * 操作符icp (‘*’ ) > isp (‘+’ ), 进OPTR栈, 取 下一符号 5 c 操作数c进OPND栈, 取下一符号 a b c # + * a s1# + 6 - 操作符icp (‘-’ ) < isp (‘*’ ), 退OPND栈‘c’, 退OPND 栈‘b’, 退OPTR栈‘*’, 计算 b * c→ s1, 结果 进OPND栈 s2# 7 同上同上ic p (‘-’ ) < isp (‘+’ ), 退OPND栈‘s ’, 1 退OPND 栈‘a’, 退OPTR栈‘+’, 计算 a * s1→ s2, 结果 进OPND栈
习题三栈和队列 一单项选择题 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
第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. 对于栈操作数据的原则是（B）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在做进栈运算时,应先判别栈是否( B),在做退栈运算时应先判别栈是否( A)。当栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为( B )。为 了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空 间时,应将两栈的( D )分别设在这片内存空间的两端。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D.n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 3. 一个栈的输入序列依次为1，2，3，…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出 元素是（ D ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则pi是( D )。 A. i B. n-i C. n-i+1 D. 不确定 6.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ） 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 ）不可能是其出栈序列。 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 ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 9. 设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4
03 栈和队列 【单选题】 1. 设入栈先后顺序为a,b,c，且在入栈过程中可出栈，则不可能得到的出栈序列是（B）。Ａ、a,b,c Ｂ、c,a,b Ｃ、b,c,a Ｄ、b,a,c 2. 栈是一种（B）的线性表。 Ａ、先进先出Ｂ、后进先出Ｃ、随意进出 3. 在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（D）。 Ａ、不变Ｂ、top=n Ｃ、top++ Ｄ、top-- 4. 设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（C）。 Ａ、rear=front.next Ｂ、rear=rear.next Ｃ、front=front.next Ｄ、front=rear.next 5. 向一个栈顶指针为s且带头结点的链栈中插入一个p所指结点时，应执行（B）。Ａ、s.next=p; Ｂ、p.next=s.next; s.next=p Ｃ、p.next=s; s=p; Ｄ、p.next=s; s=s.next; 6. 从一个栈顶指针为s且不带头结点的链栈中删除一个结点，用x保存被删结点的值，则执行（D）。 Ａ、x=s; s=s.next; Ｂ、x=s.data; Ｃ、s=s.next; x=s.data; Ｄ、x=s.data; s=s.next; 7. 设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则插入p所指结点的操作是（B）。 Ａ、front.next=p; front=p; Ｂ、rear.next=p; rear=p; Ｃ、p.next=rear; rear=p; Ｄ、p.next=front; front=p; 8. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3,…,pn，若 p1=n，则pi为（C）。Ａ、i Ｂ、n-i Ｃ、n-i+1 Ｄ、不确定 【计算题】 1. 设入栈序列a、b、c、d，且在入栈的过程中允许出栈，试写出所有不可能得到的出栈序列。参考答案： dabc、dacb、dbac、dbca、dcab、cadb、cabd、cdab、bdac、adbc。
数据结构第3章栈与队列习题 第3章栈与队列 一、单项选择题 1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。A．A B．B C．C D．D 2．经过以下栈运算后，x的值是。 InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x); A．a C．1 B．b D．0 3．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。A．push,pop,push,pop,push,pop C．push,push,pop,pop,push,pop B．push,push,push,pop,pop,pop D．push,pop,push,push,pop,pop 4．设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的序列是。A．A,B,C,D B．D,C,B,A C．A,C,D,B D．D,A,B,C 5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。A．edcba C．dceab B．decba D．abcde 6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。 A．i C．j-i+1 B．n-i D．不确定
7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若 p1=n，则pi的值。 A．i C．n-i+1 B．n-i D．不确定 8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,pn，若p1=3,则p2的值。 A．一定是2 B．一定是1 C．不可能是1 D．以上都不对 9．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若p3=1,则p1的值。 A．可能是2 C．不可能是2 B．一定是1 D．不可能是3 10．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若p3=3,则p1的值。 A．可能是2 C．不可能是1 B．一定是2 D．一定是1 11．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若pn=1,则pi(1≤i≤n-1)的值。 A．n-i+1 B．n-i C．i D．有多种可能 12．判定一个顺序栈S为空的条件为。 A．S.top= =S.base C．S.top!= S.base+S.stacksize A．S.top-S.base= =S.stacksize C．S.top- S.base!=S.stacksize B．S.top!= S.base D．S.top= = S.base+S.stacksize B．S.top= = S.base D．S.top!= S.base 13．判定一个顺序栈S为栈满的条件是。
《数据结构》习题集：第3章栈和队列 数据结构课后练习题 第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 结点时，则执行（ B ） 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 保存被删除结点的值，则执行（B ） 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，则判定此循环队
第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A.栈顶 B.栈底 C.任意位置 D.指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top ==n表示栈空，则向这个栈插入一个元素 时，首先应执行（）语句修改top指针。 A. top++; B. top ; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A.前一个 B.后一个 C.当前 D.后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A.队头指针加一 B.队头指针减一 C.取出队头指针所指的元素 D.取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入 一个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B. s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结 点，并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x=top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; typedef struct {
head 第3章 栈和队列 自测卷答案 姓名 班级 一、填空题〔每空1分，共15分〕 1. 【李春葆】向量、栈和队列都是 线性 构造，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进展插入运算，在表的另一端进展删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 挪动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 挪动队首指针 ，后 取出元素 。 8. 〖00年统考题〗带表头结点的空循环双向链表的长度等于 0 。 解： 二、判断正误〔判断以下概念的正确性，并作出简要的说明。〕〔每题1分，共10分〕 〔 × 〕1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑构造概念，可以顺序存储或链式存储，与元素数据类型无关。 〔 × 〕2. 在表构造中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU 中也用队列。 〔 √ 〕3. 栈是一种对所有插入、删除操作限于在表的一端进展的线性表，是一种后进先出型构造。 〔 √ 〕4. 对于不同的使用者，一个表构造既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑构造，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 〔 × 〕5. 栈和链表是两种不同的数据构造。 错，栈是逻辑构造的概念，是特殊殊线性表，而链表是存储构造概念，二者不是同类项。 〔 × 〕6. 栈和队列是一种非线性数据构造。 错，他们都是线性逻辑构造，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 〔 √ 〕7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 〔 √ 〕8. 两个栈共享一片连续内存空间时，为进步内存利用率，减少溢出时机，应把 两个栈的栈底分别设在这片内存空间的两端。 〔 × 〕9. 队是一种插入与删除操作分别在表的两端进展的线性表，是一种先进后出型构造。 错，后半句不对。
数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。