数据结构栈和队列习题及答案

第三章栈和队列试题一、单项选择题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, 1B. 2, 1, 3C. 3, 1, 2D. 1, 3, 24.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。

A. 前一个B. 后一个C. 当前D. 后面5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。

A. n-2B. n-1C. nD. n+16.从一个顺序存储的循环队列中删除一个元素时，需要（）。

A. 队头指针加一B. 队头指针减一C. 取出队头指针所指的元素D. 取出队尾指针所指的元素7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。

A. front+1 == rearB. rear+1 == frontC. front == 0D. front == rear8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。

A. front == rearB. front != NULLC. rear != NULLD. front == NULL9.设链式栈中结点的结构为（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是指向栈顶的指针。

第3章栈和队列一、填空题1、栈是限定仅在表尾进行插入或删除操作的线性表。

2、栈的修改是按照后进先出的原则进行的。

3、队是一种先进先出的线性表。

4、把队列头尾相接的顺序存储结构称为循环队列。

5、队列也是一种操作受限的线性表，允许插入的一端叫做__队尾___，允许删除的一端叫做__队头__。

二、判断题1、栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。

（√）2、任何一个递归过程都可以转换成非递归过程。

（√）3、若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1。

（√）4、通常使用队列来处理函数的调用。

（╳）5、循环队列通常用指针来实现队列的头尾相接。

（╳）三、单项选择题1、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（C）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（C）。

A．i B．n-i C．n-i+1 D．不确定解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

3、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（D）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

第三章栈、队列和数组一、名词解释：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.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。

习题三栈和队列一单项选择题1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/22．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。

A 可能是2B 一定是2C 可能是1D 一定是13. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 64.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（）A.2B. 3C. 5D.65. 若栈采用顺序存储方式存储，现两栈共享空间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值为：（）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. 用链接方式存储的队列，在进行删除运算时（）。

数据结构相关题库及答案第三章栈和队列一、判断题：1、栈和队列都是限制存取点的线性结构(易)2、栈和队列是两种重要的线性结构。

(易)3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易)4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。

(易)答案：1-4 √√××二、选择题：1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。

A、 edcba B、 decbaC、 dceabD、 abcde2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为_C___。

A、 iB、 n=iC、 n-i+1D、不确定3、栈结构通常采用的两种存储结构是_A___。

A、顺序存储结构和链式存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存储结构和非线性存储结构4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。

A、top !=0B、top= =0C、top !=m0D、top= =m0-15、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。

A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-16、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。

(不带空的头结点) (易)A、HS—＞next=s;9B、s—＞next= HS—＞next; HS—＞next=s;C、s—＞next= HS; HS=s;D、s—＞next= HS; HS= HS—＞next8、从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__ _B_。

(不带空的头结点) (中)A、x=HS; HS= HS—＞next;B、x=HS—＞data;C、HS= HS—＞next; x=HS—＞data;D、x=HS—＞data; HS= HS—＞next;9、一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是___C_ 。

第3章栈和队列一、选择题1.栈结构通常采用的两种存储结构是（A ）。

A、顺序存储结构和链表存储结构B、散列和索引方式C、链表存储结构和数组D、线性链表结构和非线性存储结构2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ）A、ST.top-ST.base<>0B、ST.top-ST.base==0C、ST.top-ST.base<>nD、ST.top-ST.base==n3.向一个栈顶指针为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、-+*abcd6.中缀表达式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，1B、1，2，3，4C、1，4，3，2D、3，2，4，18.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（）A、Q.rear-Q.front==nB、Q.rear-Q.front-1==nC、Q.front==Q.rearD、Q.front==Q.rear+19.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（）A、1，5B、2, 4C、4，2D、5，111.用单链表表示的链式队列的队头在链表的（）位置A、链头B、链尾C、链中12.判定一个链队列Q（最多元素为n 个）为空的条件是（）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n13.在链队列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;C、Q.front->next=Q.front->next->next;D、Q.front=Q.rear->next;15.用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）A、仅修改队头指针B、仅修改队尾指针C、队头尾指针都要修改D、队头尾指针都可能要修改。

一、单选题1、经过以下栈运算后，x的值是（）。

InitStack(s); Push(s,a); Push(s,b); Pop(s,x); GetTop(s,x);A.bB.0C.1D.a正确答案：D2、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A.2，3，5，4，1B.5，4，3，2，1C.2，1，5，4，3D.4，3，1，2，5正确答案：D3、若链栈采用无头结点的单链表存储，top指向栈顶。

若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A.x=top->data;top=top->next；B.top=top->link;x=top-> next；C.x=top-> next；D.x=top;top=top-> next；正确答案：A4、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A.n+r-fB.n+r-f)%nC.r-fD.(n+f-r)%n正确答案：B5、设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0)return 1;elsereturn n*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。

A.n+2B.nC.n-1D.n+1正确答案：D6、栈在（）中有所应用。

A.表达式求值B.递归调用C.其他三个选项D.函数调用正确答案：C7、为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。

主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（）。

A.线性表B.有序表C.栈D.队列正确答案：D8、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

数据结构练习题（一）一、单选题1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( )。

A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.?4.以下数据结构中( )是非线性结构。

A. 队列B. 栈C. 线性表D. 二叉树5.设有一个二维数组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．6966.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据7.二叉树的第k层的结点数最多为( )。

A．2k-1 +1 D. 2k-18.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。

<A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，39.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。

A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。

《数据结构》期末复习题及参考答案- 第3章栈和队列一、选择题1、对于栈，操作数据的原则是（）。

A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2、要求数据遵循FIFO（先进先出）原则的数据结构是（）。

A. 线性表B. 链表C. 队列D. 栈3、若进栈的序列为1,2,3,4，则以下哪一个不可能是一个出栈序列。

A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 65、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

(A) f->next=c；f=s (B) r->next=s；r=s(C) s->next=r；r=s (D) s->next=f；f=s7、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 28、数字1、2依次入栈，则出栈的顺序可能有（）种情况；数字1、2依次进入队列，则出队列的顺序可能有（）种情况。

A. 1 , 2B. 2 , 1C. 2 , 2D. 1 , 19、设一个栈的输入序列是1，2，3，4，5，则下列序列中，是栈的合法输出序列的是（）。

A. a，c，b，dB. b, c，d，aC. c, d，b, aD. d, c，a，b11、顺序存储的栈和队列中已经各有N个结点，要删除一个结点分别需要移动数据（）次和（）次。

A. N/2 , NB. N , N/2C. 0 , ND. N , 012、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。

A. 递归部分B. 终止条件和递归部分C. 迭代部分D.终止条件和迭代部分14、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中MAXQSIZE表示队列的容量）（）：A．if (Q.rear == Q.front) …B．if (Q.rear == (Q.front + MAXQSIZE))C．if (Q.rear == (Q.front + 1) % MAXQSIZE)的元素个数为（）。

第一节栈
一、栈的定义及其运算
1、栈的定义
栈(Stack)：是限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一端称为栈项(top)，另一端称为栈底(bottom)。

不含元素的空表称为空栈。

栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(Last In First Out)的线性表，简称为LIFO表。

真题选解
（例题·填空题）1、如图所示，设输入元素的顺序是（A，B，C，D），通过栈的变换，在输出端可得到各种排列。

若输出序列的第一个元素为D，则输出序列为。

隐藏答案
【答案】DCBA
【解析】根据堆栈"先进后出"的原则，若输出序列的第一个元素为D，则ABCD入栈，输出序列为DCBA
2、栈的基本运算
(1)置空栈InitStack(&S)：构造一个空栈S。

第3章栈和队列3.1栈一、填空题1. 线性表、栈和队列都是________ 结构，可以在线性表的__________ 位置插入和删除元素；对于栈只能___________插入和删除元素；对于队列只在 ____________ 插入元素，并且只在____________ 删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为____________ 。

不允许插入和删除运算的一端称为_________ 。

3. 向栈中压入元素的操作是先____________ ，后 _______ 。

4. 从栈中弹出元素的操作是先____________ ，后 ________ 。

二、选择题：1. （）栈中元素的进出原则是（）。

A.先进先出 B .后进先出C .栈空则进D .栈满则出2. （）若已知一个栈的入栈序列是1 , 2, 3,…，n,其输出序列为pl, p2, p3,…，pn,若p仁n,贝U pi为（）。

A. i B . n=i C . n-i+1 D .不确定3. （）判定一个栈ST （最多元素个数为m0）为空的条件是（）。

A. ST->top<>0 B . ST->top=0 C . ST->top<>mO D . ST->top=mO4. （）有六个元素1,2,3,4,5,6 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 1,2,3,4,5,6B. 5,4,3,2,1,6C. 4,3,2,1,5,6D. 6,5,4,3,1,25. （）将递归算法转换成非递归算法时，通常要借助的数据结构是（）。

A.线性表B. 栈C. 队列D. 树6. （）若栈采用顺序存储方式存储，现两栈共享空间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]7. （）一个递归算法必须包括（）。

1、栈的“先进后出”特性是指（）。

A.最后进栈的元素总是最先出栈B.同时进行进栈和出栈操作时，总是进栈优先C.每当有出栈操作时，总要先进行一次进栈操作D.每次出栈的元素总是最先进栈的元素正确答案：A2、给定一个足够大的空栈，有4个元素的进栈次序为A、B、C、D, 则以C、D开头的出栈序列的个数为（）。

A.1B.2C.3D.4正确答案：A解析：若出栈序列为CD…，则A、B、C进栈，C出栈，D进栈，D出栈，此后只有B出栈和A出栈一种情况，所以这样的出栈序列只有CDBA 一个。

3、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是（）OA. dcebfaB.cbdaefC.bcaefdD. afedcb正确答案：D 解析：选项A操作：a进，b进，c进，d进，d出，c出，e进，e 出，b出，f进，f出，a出。

选项B操作：a进，b进，c进，c出，b出，d进，d出，a出，e 进，e出，f进，f出。

选项C操作：a进，b进，b出，c进，c出，a出，d进，e进，e 出，f进，f出，d出。

选项D操作：a进，a出，b进，c进，d进，e进，f进，f出，e 出，d出，c出，b出。

从中看到，选项D中最后连续出栈5次，不符合要求。

4、一个栈的进栈序列是a、b、c、d> e,则栈的不可能的输出序列是（）。

A.edcbaB.decbaC.dceabD.abcde正确答案：C解析：对于选项A, a、b、c^ d、e进栈，e、d^ c、b、a出栈；对于选项B, a, b, c, d进栈，d出栈，e进栈，e出栈，c、b、a 依次出栈；对于选项C, a、b、c^ d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈底到栈顶为a、b,不可能a先出栈，所以C是不可能的输出序列；对于选项D, a进栈，a出栈，b进栈，b出栈，c进栈，c出栈，d 进栈，d出栈，e进栈，e出栈。

一、单选题1、元素A、B、C、D依次进栈后，栈顶元素是 _______。

A.BB.DC.CD.A正确答案：B2、经过以下运算后， x的值是 _______。

InitStack (s); Push(s, a); Push(s, b); Pop(s, x); GetTop(s,x)A.0B.bC.aD.1正确答案：C3、经过以下栈运算后，StackEmpty(s)的值是 _______。

InitStack (s); Push(s, a); Push(s, b); Pop(s, x); Pop(s,y)A.0B.bC.aD.1正确答案：D4、已知一个栈的进栈序列是ABC，出栈序列为CBA，经过栈的操作是 _______。

A.push, push, push, pop, pop, popB.push,pop,push, push,pop, popC.push, push,pop, pop,push,popD.push,pop,push,pop,push,pop正确答案：A5、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是 _______。

A. bcaefdB.afedcbC.cbdaefD.dcebfa正确答案：B6、设一个栈的输入序列为A、B、C、D，则借助一个栈所得的输出序列不可能是_______。

A.DCBAB.DABCC.ACDBD.ABCD正确答案：B7、一个栈的进栈序列是abcde，则栈的不可能的输出序列是 _______。

A.decbaB.abcdeC.dceabD.edcba正确答案：C8、已知一个栈的进栈序列是1，2，3，…n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是_______。

A.n-iB.j-i+1C.iD.不确定正确答案：D9、已知一个栈的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=n,则pi的值是_______。

栈和队列习题及答案【篇一：栈和队列练习题答案】xt>一、填空题1. 线性表、栈和队列都是结构，可以在线性表的在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。

不允许插入和删除运算的一端称为栈底。

3. 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

二、判断正误（√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

错，有可能。

三、单项选择题（b）1.栈中元素的进出原则是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出（c）2.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为Ａ．i Ｂ．n-iＣ．n-i+1 Ｄ．不确定解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，?，n，则出栈的序列是n，?，3，2，1。

（若不要求顺序出栈，则输出序列不确定）（d）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f;（Ｄ）（n＋r －f）% n e：①1 ②2 ③ 3 ④ 0四、阅读理解1. 【严题集3.3②】写出下列程序段的输出结果（栈的元素类型selem type为char）。

第 3 章特殊线性表——栈、队列和串2005-07-14第 3 章特殊线性表——栈、队列和串课后习题讲解1. 填空⑴设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push后，输出序列是（），栈顶指针为（）。

【解答】23，1003H⑵栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。

【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间⑶（）可作为实现递归函数调用的一种数据结构。

【解答】栈【分析】递归函数的调用和返回正好符合后进先出性。

⑷表达式a*(b+c)-d的后缀表达式是（）。

【解答】abc+*d-【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。

⑸栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。

【解答】后进先出，先进先出，对插入和删除操作限定的位置不同⑹循环队列的引入是为了克服（）。

【解答】假溢出⑺数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。

【解答】（rear-front+n）% n【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。

⑻用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。

【解答】Ｏ(1)，Ｏ(n)【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。

⑼串是一种特殊的线性表，其特殊性体现在（）。

第3章栈与队列一、单项选择题1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。

A．A B．BC．C D．D2．经过以下栈运算后，x的值是。

InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x);A．a B．bC．1 D．03．已知一个栈的进栈序列是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,AC．A,C,D,B D．D,A,B,C5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。

A．edcba B．decbaC．dceab D．abcde6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。

A．i B．n-iC．j-i+1 D．不确定7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若p1=n，则pi的值。

A．i B．n-iC．n-i+1 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 B．一定是1 C．不可能是2 D．不可能是310．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若p 3=3,则p1的值。

A．可能是2 B．一定是2 C．不可能是1 D．一定是111．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若p n =1,则pi(1≤i≤n-1)的值。

计算机学科专业基础综合数据结构-栈、队列和数组(一)(总分：92.00，做题时间：90分钟)一、单项选择题(总题数：26，分数：52.00)1.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i(1＜=i＜=n)个元素是 ____ 。

（分数：2.00）A.不确定B.n-i+1 √C..iD.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 2B.4 5 3 1 2 6C.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；34 12 56； 345 12 6； 3456 12但是314526是不能的。

第三章 栈和队列 试题2. 当利用大小为 n 的数组顺序存储一个栈时，假定用首先应执行（ ）语句修改 top 指针。

A. top++ ;B. top -- ;top ==n 表示栈空，则向这个栈插入一个元素时， C. top = 0A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（ ）位置。

A. 前一个B. 后一个C. 当前D. 后面5. 当利用大小为 n 的数组顺序存储一个队列时，该队列的最大长度为（ ）。

A. n-2B. n-1C. nD. n+16. 从一个顺序存储的循环队列中删除一个元素时，需要（ ）。

A. 队头指针加一B. 队头指针减一C. 取出队头指针所指的元素D. 取出队尾指针所指的元素一、单项选择题 1. 栈的插入和删除操作在（ A. 栈顶）进行。

B. 栈底C. 任意位置D. 指定位置3. 若让元素 1,2,3依次进栈，则出栈次序不可能出现（ ）种情况。

D. topD. 1, 3, 27. 假定一个顺序存储的循环队列的队头和队尾指针分别为front 和 rear ，则判断队空的条件为 ）。

A. front+1 == rearB. rear+1 == frontC. front == 0D. front == rear8. 假定一个链式队列的队头和队尾指针分别为A. front == rear C. rear != NULLfront 和 rear ，则判断队空的条件为（ ）。

B. front != NULLD. front == NULL9. 设链式栈中结点的结构为（ data, link 个由指针 s 所指的结点，则应执行操作（ A.top->link = s;C. s->link = top ; top = s），且 top 是指向栈顶的指针。

若想在链式栈的栈顶插入一 ）。

B. s->link = top->link ; top->link = s D. s->link = top; top = top->link;10. 设 链式栈中结点的结构为（ 并将被摘除结点的值保存到 data, link ），且 top x中，则应执行操作（是指向栈顶的指针。