第三章栈和队列习题_数据结构电子教案

数据结构第三章栈和队列练习及答案⼀、选择题1、栈中存取数据的原则（）A、先进先出B、先进后出C、后进后出D、随意进出2、队列中存取数据的原则（）A、先进先出B、后进先出C、先进后出D、随意进出3、插⼊和删除只能在⼀端进⾏的线性表，称为（）A、队列B、循环队列C、栈D、循环栈4、在栈中，出栈操作的时间复杂度为（）A、O（1）B、O（log2n）C、O（n）D、O（n2）5、设长度为n的链队列⽤单循环链表表⽰，若只设头指针，则⼊队操作的时间复杂度为（）A、O（1）B、O（log2n）C、O（n）D、O（n2）6、设长度为n的链队列⽤单循环链表表⽰，若只设头指针，则出队操作的时间复杂度为（）A、O（1）B、O（log2n）C、O（n）D、O（n2）7、⼀个线性表的第⼀个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）A、110B、108C、100D、1208、⼀个栈的⼊栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）A、edcbaB、decbaC、dceabD、abcde9、若已知⼀个栈的⼊栈序列是1，2，3，……，n，其输出序列是p1,p2,p3,……,pn，若p1=n，则pi为（）A、iB、n=iC、n-i+1D、不确定10、判断⼀个栈ST（最多元素m0）为空的条件是（）A、ST->top==0B、ST->top==-1C、ST->top!=m0D、ST->top==m011、判断⼀个栈ST（最多元素m0）为满的条件是（）A、ST->top!=0B、ST->top==0C、ST->top!=m0D、ST->top==m012、判断⼀个循环队列QU（最多元素为m0）为空的条件是（）A、QU.front==QU.rearB、QU.front!=QU.rearC、QU.front==(QU.rear+1)%m0D、QU.front!=(QU.rear+1)%m013、判断⼀个循环队列QU（最多元素为m0）为满的条件是（）A、QU.front==QU.rearB、QU.front!=QU.rearC、QU.front==(QU.rear+1)%m0D、QU.front!=(QU.rear+1)%m014、循环队列⽤数组存放其元素值A[0，m-1]，已知其头尾指针分别是rear和front，则当前队列的元素个数是（）A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front15、栈和队列的共同特点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插⼊和删除D、没有共同点⼆、填空题1、设长度为n的链队列⽤单循环链表表⽰，若只设头指针，则⼊队和出队操作的时间复杂度分别为（O(N)）和（O(1)）；若⼜设尾指针，则⼊队和出队操作的时间复杂度分别为（O(1)）和（O(1)）。

《数据结构》第三章堆栈和队列习题基本概念题：3-1 什么叫堆栈？什么叫队列？3-2 线性表、堆栈和队列这三种抽象数据类型有什么相同之处和不同之处？3-3 在顺序队列中，什么叫真溢出？什么叫假溢出？为什么顺序队列通常都采用顺序循环队列结构？3-4 什么叫优先级队列？优先级队列和队列有什么相同之处和不同之处？3-5 举例说明堆栈、队列和优先级队列的用途。

复杂概念题：3-6 设数据元素序列{a, b, c, d, e, f, g}的进堆栈操作和出堆栈操作可任意进行（排除堆栈为空时的出堆栈操作情况），下列哪些数据元素序列可由出堆栈序列得到：（1）{d, e, c, f, b, g, a}; （2）{f, e, g, d, a, c, b};（3）{e, f, d, g, b, c, a}; （4）{c, d, b, e, f, a, g}3-7 画出借助堆栈把下列中缀表达式转换成后缀表达式的过程：A * (B - D) + E / F3-8 对于一个堆栈，（1）如果输入序列由A,B,C,D组成，试给出全部可能的输出序列和不可能的输出序列。

（2）设有n个数据元素的序列顺序进栈，试给出可能的输出序列个数。

（3）设有n个数据元素的序列顺序进栈，试给出不可能的输出序列个数。

（4）以n=4为例，用（2）和（3）中得出的公式验证（1）的结论。

算法设计题：3-9 编写一个判断算术表达式中开括号和闭括号是否配对的算法。

3-10 给出采用设置标志位的方法解决“假溢出”问题的顺序循环队列的初始化操作、入队列操作和出队列操作的算法思想。

3-11 设计采用设置标志位方法解决“假溢出”问题的顺序循环队列的初始化操作、入队列操作和出队列操作的函数。

3-12 仿照例3-3，编程序判断一个字符序列是否是回文，要求采用链式队列和链式堆栈。

3-13 编程序判断一个字符序列是否是回文，要求只使用堆栈，不使用队列。

3-14 编写一个顺序优先级队列的出队列操作算法，要求不考虑相同优先级时的先进先出原则。

xxxx学院教案首页xxxx学院教案附页第一学时（栈的定义、常用操作与顺序存储的实现）一、情景导入（1）引出栈的概念由线性表引出栈：栈是线性表的一种，只是在操作上，与线性表有所差别。

如果没有道具，借用课本，粉笔盒或学生自主进行展示。

（2）进入主题，讲解栈的特点与线性表进行类比，栈与基础线性表的差别，在于它的操作受限、取数的方式不如线性表自由。

可以结合图3-1中的图示，引导学生回想存取碗时的具体操作，帮助学生领悟栈的特点。

图3-1 一摞碗二、知识讲解（1）栈的特点结合图3-2中栈的结构图，对栈的操作原则——后进先出，进行讲解。

图3-2 栈的结构图（2）栈的常用操作栈的常用操作如下：•创建栈（初始化栈）•判断栈是否为空•进栈•出栈•获取栈顶元素•获取栈的长度•销毁栈在对栈的原则进行讲解之后，对栈中常用操作进行总结。

（3）栈的顺序存储实现栈是线性表的一种，顺序存储的栈是一种顺序表。

在知识点（2）提到的操作中，进栈和出栈是可以展示出栈特点的特色操作，可以结合图示，对这两种操作的实现进行详细说明；此外，简单叙述栈中其余功能的实现方法。

在讲解完顺序栈中的各种操作之后，结合书中例3-1给出的代码，带领学生掌握栈的实现方法。

第二学时（栈的链式存储实现）一、知识回顾（1）对上节课留的作业进行答疑。

（2）回顾总结上节课的内容，引出本节课主题。

上个学时讲解了栈的定义、栈的特点与栈的顺序实现，本学时来探讨栈的链式存储实现。

二、知识讲解（1）链栈的数据结构定义链栈是一种链表，与顺序栈相同，链栈在操作时也受到限制，遵循“后进先出”的原则。

结合链表的数据结构定义，引导学生完成链栈的数据结构定义。

（2）链栈的实现链栈的存储方式与链表相同，操作原则与顺序栈相同。

从这两点出发进行分析，引导学生找到链栈实现的思路，然后给学生留出一定时间，由学生自主分析巩固链栈操作的实现方法，之后结合学生自主实现链栈时遇到的问题，对链栈进行讲解。

（用栈实现四则运算）三、情境引入通过计算机的算术运算功能，引出本学时的主题：计算机的基本功能大多都是基于对数据的操作，给出一个运算式，计算机能迅速计算出结果，若运算时有误，如运算式“1+3*（2+5”，右边少了一个“）”，编绎器会立刻检查出错误并报告，那么计算机是如何做到的呢？藉由以上问题，引出逆波兰表达式。

数据结构教案第三章栈和队列目录3.1栈的基本概念 (2)3.1.1 栈的抽象数据类型定义 (2)3.1.2 顺序栈 (2)3.1.3 链栈 (4)3.2栈的应用 (4)3.2.1 数制转换：将十进制数N转换成其他d进制数 (4)3.2.2 括号匹配的检验 (4)3.2.3 行输入处理程序 (4)3.2.4 迷宫求解 (5)3.2.5 表达式求值 (5)3.3栈与递归的实现 (6)3.4队列的基本概念 (6)3.4.1 队列的抽象数据类型定义 (6)3.4.2 链队列 (7)3.4.3 循环队列 (8)3.5队列与栈的应用 (8)3.5.1 离散事件模拟 (8)第3章栈和队列3.1 栈的基本概念3.1.1 栈的抽象数据类型定义1、栈的逻辑特征1）限定在表尾进行插入或删除操作的线性表；2）栈顶——表尾端；栈底——表头端3）后进先出的线性表2、抽象数据类型的定义ADT Stack{数据对象：D={a i |a i∈ElemSet, i=1,2,…,n, n≥0}数据关系：R={R1},R1={<a i-1,a i>|a i-1,a i∈D, i=2,3,…,n }基本操作：InitStack( &S )操作结果：构造一个空的栈SDestroyStack( &S )初始条件：栈S已存在操作结果：销毁栈SClearStack( &S )初始条件：栈S已存在操作结果：将栈S重置为空栈StackEmpty( S )初始条件：栈S已存在操作结果：若S为空栈，则返回TRUE，否则返回FALSEStackLength( S )初始条件：栈S已存在操作结果：返回栈S中数据元素的个数GetTop( S, &e )初始条件：栈S已存在且非空操作结果：用e返回S中栈顶元素Push( &S, e )初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop( &S, &e )初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值StackTraverse( S, visit( ) )初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit( )。

22
= m0*m2 = 2 ✓ 出栈序列中1在第2位。1前有2后有3，
出栈序列为 {2, 1, 3}。= m1*m1 = 1 ✓ 出栈序列中1在第3位。前面2个元素有
m2 = 2个出栈序列：{2, 3, 1}, {3, 2, 1}。 = m2*m0 = 2
✓ n = 4，m4 = 14: = m0*m3+m1*m2+m2*m1+m3*m0
//出栈
virtual bool getTop(E& x) = 0; //取栈顶
virtual bool IsEmpty() = 0;
//判栈空
virtual bool IsFull() = 0;
//判栈满
}；
4
栈的数组存储表示 — 顺序栈
01 2 3 4 5 6 7 8 9 elements
maxSize-1
E *newArray = new E[2*maxSize];
//创建更大的存储数组
for (int i = 0; i <= top; i++)
newArray[i] = elements[i];
maxSize += maxSize;
delete [ ]elements;
elements = newArray;
双栈共享一个栈空间
0
maxSize-1
V
b[0]
t[0] t[1]
b[1]
两个栈共享一个数组空间V[maxSize]
设立栈顶指针数组 t[2] 和栈底指针数组 b[2]
t[i]和b[i]分别指示第 i 个栈的栈顶与栈底
初始 t[0] = b[0] = -1, t[1] = b[1] = maxSize

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

栈和队列教案(总13页) --本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--教案课程名称：数据结构（C语言版）授课班级：技校二年级学生授课学时：1学时授课章节：第三章栈和队列课型：理论课任课教师：***图2 栈的示意图从图2中可以看出第一个进栈的a1为栈底元素，最后一个进栈的an为栈顶元素，进栈和出栈也是同一个方向。

这也是最基本的栈的示意图。

需要同学们熟知。

其实，要解决这个出站问题就离不开我们今天将要学习的进栈、出栈技术，这节课我们将从如下三个方面来掌握它：栈的定义、栈的表示和实现、栈的应用与练习。

其中栈的表示与实现是本节的重点。

一、抽象数据类型栈的定义（6分钟）点。

二、介绍栈的定义类型（8分钟）ADT Stack{数据对象：D＝{ a i | a i ∈ElemSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ <a i-1, a i >| a i-1, a i∈D, i=2,...,n }约定a n端为栈顶，a1 端为栈底。

基本操作：InitStack(&S)操作结果：构造一个空栈 S。

DestroyStack(&S)初始条件：栈 S 已存在。

操作结果：栈 S 被销毁。

StackEmpty(S)初始条件：栈 S 已存在。

操作结果：若栈 S 为空栈，则返回TRUE，否则 FALE。

GetTop(S, &e)初始条件：栈 S 已存在且非空。

操作结果：用 e 返回 S 的栈顶元素。

StackLength(S)初始条件：栈 S 已存在。

分钟）操作结果：返回 S 的元素个数，即栈的长度。

ClearStack(&S)初始条件：栈 S 已存在。

操作结果：将 S 清为空栈。

Push(&S, e)初始条件：栈 S 已存在。

操作结果：插入元素 e 为新的栈顶元素。

Pop(&S, &e)初始条件：栈 S 已存在且非空。

算法举例 栈模拟队列－－入队
int top1; ∥top1是栈s1的栈顶指针，是全局变量
int enqueue(stack s1,ElemType x)
∥ 用入栈模拟入队
{if(top1==n && !Sempty(s2))
{printf(“栈满”);return(0);} ∥s1满s2非空,这时s1不能再入栈
B、当同时进行插入、删除操作时，总是插入操作优先
C、每当有删除操作时，总要先做一次插入操作
D、每次从队中删除的总是最早插入的元素
【武汉理工大学2004一.4(3分)】
A
自测题
用不带头结点的单链表存储队列，其队头指针指向队 头结点，队尾指针指向队尾结点，则在进行出队操作 时( )
A．仅修改队头指针 B. 仅修改队尾指针 C. 队头，队尾指针都可能要修改 D. 队头，队尾指针都要修改 【江苏大学2004一.4(2分)】 C
arrStack<T> *s1,*s2;
// 存放类型为T的队列元素的栈,s1为入队端，s2为出队端
public:
// 队列的运算集
arrQueue(int size) {
// 创建队列的实例
mSize = size/2; // 浪费一个存储空间，以区别队列空和队列满
s1 = new arrStack<T>(mSize);
int A[],B[],n; ∥设整数已存于数组A[1..n]中
void comb(int i, int j,int k)
∥从A[1..n]中选取k（k<=n）个元素的所有组合
{if(k==0)
{for(int i=1;i<=kk;i++) ∥这里kk为所选数（题中为3）

第3章栈和队列本章教学提要教学重点：栈的定义及其基本运算栈的顺序存储结构队列的定义及基本运算队列的顺序存储结构教学难点：栈的链式存储结构队列的链式存储结构——链队列本章教学内容本章将介绍两种特殊的线性表——栈和队列。

从逻辑结构上看，栈和队列仍是线性表，其特殊性主要是其基本运算有着严格的规定。

由于栈和队列在程序设计中应用广泛，因此对它们单独进行讨论。

3．1 栈栈是规定仅在表尾进行插入和删除运算的线性表，采用的是后进先出的访问方法。

表头叫做栈底，表尾叫做栈顶。

栈的基本运算：1．inistack(s)：初始化操作，设定一个空栈s。

2．push(s,x)：在栈s的顶部插入元素x，简称为入栈。

3．pop(s,*x)：删除并返回栈s的栈顶数据元素，简称为出栈，其中x是返回的栈顶数据元素。

相当于线性表中删除一个数据元素，该运算与push (s,x)为互逆运算。

4．top(s,*x)：取出栈s的栈顶元素x，但不删除栈顶元素。

5．setnull(s)：置s为一个空栈。

6．empty(s)：判定s是否为空栈，若是则返回值为真，否则返回值为假。

3．2 队列队列是一种访问次序是先进先出的线性表队列的基本运算如下：1．addqueue(q,x)：在队列q的队尾插入元素x，称为入队列。

2．delqueue(q,*x)：删除并返回队列q的队头元素，x为返回的队头元素，称为出队列。

3．frontque(q,*x)：取得队列q的队头元素，x为返回的队头元素。

4．setnull(q)：置q为一个空队列。

5．empty(q)：判断q是否为空队列，当q为空时，返回“true”，否则“false”。

队列也是一种操作受限的线性表，它具有线性表的两种存储结构——顺序存储结构和链式存储结构。

教学过程设计
1.结合栈在迷宫求解、表达式实现和递归实现实例解释数据结构的基本概念，增强学生对栈数据结构的兴趣；
2.栈和队列对比学习，对比他们的相同点和不同点加深对基本概念和应用的理解。
作业布置
设Q[0,6]是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。（1）a, b, c, d入队；（2）a, b, c出队；（3）i , j , k , l , m入队；（4）d, i出队；（5）n, o, p, q, r入队。
掌握：栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用
主要知识点、重点、难点
知识点：栈和队列的定义、表示和实现；栈在数值转换、括号匹配、行编辑程序、迷宫求解、表达式求解和递归实现方面的应用；队列的定义、表示和实现；队列的链式表示和顺序表示及实现。
重点难点：栈、队列的设计和实现以及基本操作及相关算法及栈和队列的典型应用。
作业布置设q06是一个静态顺序队列初始状态为frontrear0请画出做完下列操作后队列的头尾指针的状态变化情况若不能入对请指出其元素并说明理由
Байду номын сангаас课程名称
数据结构B
章节名称
栈和队列
授课学时
总课时：2课堂讲授：2
教学目标与要求：
了解：栈与队列的定义、特点和性质；
掌握：栈、队列的设计和实现以及基本操作及相关算法

第三章栈和队列一、选择题1. 以下不是栈的基本运算的是( )A) 删除栈顶元素B) 删除栈底元素C) 判断栈是否为空D) 将栈置为空栈2. 若进栈序列为1,2,3,4, 进栈过程中可以出栈,则下列不可能的一个出栈序列是( )A) 1,4,3,2 B) 2,3,4,1C) 3,1,4,2 D) 3,4,2,13. 栈和队列的共同点( )A) 都是先进先出B) 都是后进先出C) 只允许在端点处插入和删除元素D) 没有共同点4•若已知一个进栈序列是1,2,3, ••…,n,其输出序列是p1,p2,vp3,…・卩n,若p仁n,贝U pi(1<i<n)为( )。

A) I B) n-iC) n-i+1 D) 不确定5•判断一个栈ST(最多元素为MaxSize)为空的条件是()A) ST->top==1 B) ST->top==-1C) ST->top!=MaxSize-1 D) ST->top==MaxSize-16•向一个栈指针为HS的链式栈中插入一个s所指的结点时，则执行()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;7•在一个链式队列中•假设f和r分别为队头和队尾指针，则插入s所指的结点运算是()A) f->next=s;f=s; B) r->next=s;r=s;C) s->next=s;r=s; D) s->next=f;f=s;8•在一个链式队列中，假设f和r分别为队头和队尾指针，则删除结点的运算是()A) r=f->next; B) r=r->next;C) f=f->next; D) f=r->next;9•下列关于线性表，栈和队列叙述,错误的是()A) 线性表是给定的n(n 必须大于零)个元素组成的序列B) 线性表允许在表的任何位置进行插入和删除操作C) 栈只允许在一端进行插入和删除操作D) 队列只允许在一端进行插入一端进行删除10•—个队列的入队序列是1,2,3,4,则队列的输出序列是()A) 4,3,2,1 B) 1,2,3,4C) 1,4,3,2 D) 3,2,4,111. 设初始输入序列为1,2,3,4,5,利用一个栈产生输出序列，下列()序列是不可能通过栈产生的•A) 1,2,3,4,5 B) 5,3,4,1,2C) 43,2,1,5 D) 3,4,5,2,112. 设栈s的初始状态为空,6个元素的入栈顺序为e1,e2,e3,e4,e5和e6.若出栈的顺序是e2,e4,e3,e6,e5,e1,则栈s的容量至少应该是()A.插入排序 C 快速排序23. 栈的插入和删除操作在（A 栈顶 ）进行。

3.4简述以下算法的功能
（2） status algo2(Stack S , int e){ Stack T ; int d ; InitStack(T); while (! StackEmpty(S)){ Pop(S,d); if (d!=e) Push(T,d); } while(!Stackempty(T)){ Pop(T,d); Push(S,d); } }
习题课
第3章 栈和队列
3.1
（1）如果进站的车厢序列为123，则可能得到 的出站车厢序列是什么? （2）如果进站的车厢序列为123456，则能否 得到435612和135426出站序列，并请说 明为什么不能得到或如何得到。
(1) 123 , 132 , 213 , 231 , 321 (2) 435612不能得到（6出站时，12必须在站中，只能出站成21，无法 得到12） 135426可以 1S1X2S3S3X4S5S5X4X2X6S6X
3.28 带头指针的循环链表表示队列，并且 只设一个指针指向队尾结点，编写队列初始 化、入队列和出队列算法
typedef struct QNode{ QElemTypቤተ መጻሕፍቲ ባይዱ data; Struct Qnode *next; }QNode,*QueuePtr; typedef struct { QueuePtr rear; }LinkQueue;
3.4简述以下算法的功能
（1）status algol(Stack S){ int I,n,A[255]; n = 0; while (!Stackempty(S)) {n++;Pop(S,A[n]);} for (i=1 ; i<=n ; i++) Push(S,A[i]); }

第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)的值。

第3章栈和队列一选择题1. 对于栈操作数据的原则是（）。

A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。

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

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时,才产生上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底⑤: A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点.C. 两个栈的栈顶在栈空间的某一位置相遇.D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.3. 一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i（1<=i<=n）个元素是（）。

A. 不确定B. n-i+1C. iD. n-i4. 若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是（）。

A. i-j-1B. i-jC. j-i+1D. 不确定的5. 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,p N,若p N是n,则p i是( )。

A. iB. n-iC. n-i+1D. 不确定6. 有六个元素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 67. 设栈的输入序列是1,2,3,4,则（）不可能是其出栈序列。

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,则下列序列中不可能是栈的输出序列的是（）。

《数据结构》习题汇编03第三章栈和队列试题第三章栈和队列试题一、单项选择题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是指向栈顶的指针。