数据结构栈和队列知识点总结

《数据结构》实验指导及报告书

2014 / 2015 学年 第 1学期

姓 名： 学 号： 班 级： 指导教师：徐江

计算机科学与工程学院

2014

实验二 栈和队列

一、实验目的

1、掌握栈的结构特性及其入栈，出栈操作；

2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。

二、实验内容和要求

1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。

#include #include #define ERROR 0 #define OK 1

#define STACK_INT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ typedef int ElemType; /*定义元素的类型*/ typedef struct{ ElemType *base; ElemType *top;

int stacksize; /*当前已分配的存储空间*/ }SqStack;

int InitStack(SqStack

《数据结构》实验指导及报告书

2014 / 2015 学年 第 1学期

姓 名： 学 号： 班 级： 指导教师：徐江

计算机科学与工程学院

2014

实验二 栈和队列

一、实验目的

1、掌握栈的结构特性及其入栈，出栈操作；

2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。

二、实验内容和要求

1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。

#include #include #define ERROR 0 #define OK 1

#define STACK_INT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ typedef int ElemType; /*定义元素的类型*/ typedef struct{ ElemType *base; ElemType *top;

int stacksize; /*当前已分配的存储空间*/ }SqStack;

int InitStack(SqStack

数据结构练习（栈和队列）

一、选择题

1．有5个元素a,b,c,d,e依次进栈，允许任何时候出栈，则可能的出栈序列是 C 。

A．baecd B．dceab

C．abedc

D．aebcd

2．下列有关递归的叙述，不正确的是 B 。

A．在计算机系统内，执行递归函数是通过自动使用栈来实现的。

B．在时间和空间效率方面，递归算法比非递归算法好。 C．递归函数的求解过程分为递推（进栈）和回推（出栈）两个阶段。

D．在递归函数中必须有终止递归的条件。 3．栈和队列均属于哪一种逻辑结构 A 。

A．线性结构 B．顺序结构 C．非线性结构 D．链表结构

4．设输入元素为1、2、3、P和A，输入次序为123PA，元素经过栈后得到各种输出序列，则可以作为高级语言变量名的序列有 D 种。

A．4

B．5

C．6

D．7

5．一个队列的入队序列为a，b，c，d，则该队列的输出序列是

B 。

A．dcba B．abcd C．adcb

D．cbda

1．当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行 语句修改top指针。

A、top++ B、top-- C、top=0 D、top

2．若让元素1，2，3依次进栈，则出栈次序不可能出现 种情况。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2

3．假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是 。 A、f+1==r B、r+1==f C、f==0 D、f==r

4．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是 。 A、front==rear B、front!=NULL C、rear!=NULL D、front==NULL

5．执行下面函数调用后得到的输出结果是什么？

void AF(Queue & Q) {

InitQueue(Q);

int a[4] = { 5,8,12,15

数据结构学习总结

壹、研究对象及基本概念

首先从数据结构是什么开始，数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。主要研究：1、数据的逻辑结构，即数据关系之间的逻辑关系；2、数据的存储结构（即物理结构），即数据的逻辑结构在计算机中的表示；3、操作算法，即插入、删除、修改、查询、排序等操作。

一、从数据的逻辑结构划分，即数据之间的逻辑关系从线性分析的角度划

分主要有线性结构和非线性结构。线性结构又可细分为线性表、栈、队列、串、数组。非线性结构又可细分为树型结构和图结构。

线性结构: 线性表、栈、队列、串、数组 树结构

逻辑结构 非线性结构 图结构 二、从存储结构划分 物理结构

顺序结构 链式结构 索引结构 散列结构 各自的定义及特点：

1、顺序存储：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来直接体现。

优点：随机存取表中元素。缺点：插入和删除操作需要移动大量结点。

2、链式存储：它不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。

它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存

1．当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行 语句修改top指针。

A、top++ B、top-- C、top=0 D、top

2．若让元素1，2，3依次进栈，则出栈次序不可能出现 种情况。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2

3．假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是 。 A、f+1==r B、r+1==f C、f==0 D、f==r

4．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是 。 A、front==rear B、front!=NULL C、rear!=NULL D、front==NULL

5．执行下面函数调用后得到的输出结果是什么？

void AF(Queue & Q) {

InitQueue(Q);

int a[4] = { 5,8,12,15

第三章 栈和队列

一、 选择题

1.以下不是栈的基本运算的是( )

A) 删除栈顶元素 B) 删除栈底元素 C) 判断栈是否为空 D) 将栈置为空栈

2.若进栈序列为1,2,3,4,进栈过程中可以出栈,则下列不可能的一个出栈序列是( ) A) 1,4,3,2 B) 2,3,4,1 C) 3,1,4,2 D) 3,4,2,1

3.栈和队列的共同点( )

A) 都是先进先出 B) 都是后进先出

C) 只允许在端点处插入和删除元素 D) 没有共同点

4.若已知一个进栈序列是1,2,3,……,n,其输出序列是p1,p2,vp3,……pn, 若p1=n, 则pi(1

A) I B) n-i

C) n-i+1 D) 不确定

5.判断一个栈ST(最多元素为MaxSize)为空的条件是( ) A) ST->top==1 B) ST->top==-

数据结构练习第三章 栈和队列

一、选择题

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表示链式队列的

队尾指

习题三 栈和队列

一 单项选择题

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,则

第三章 栈和队列

一、 选择题

1.以下不是栈的基本运算的是( )

A) 删除栈顶元素 B) 删除栈底元素 C) 判断栈是否为空 D) 将栈置为空栈

2.若进栈序列为1,2,3,4,进栈过程中可以出栈,则下列不可能的一个出栈序列是( ) A) 1,4,3,2 B) 2,3,4,1 C) 3,1,4,2 D) 3,4,2,1

3.栈和队列的共同点( )

A) 都是先进先出 B) 都是后进先出

C) 只允许在端点处插入和删除元素 D) 没有共同点

4.若已知一个进栈序列是1,2,3,……,n,其输出序列是p1,p2,vp3,……pn, 若p1=n, 则pi(1

A) I B) n-i

C) n-i+1 D) 不确定

5.判断一个栈ST(最多元素为MaxSize)为空的条件是( ) A) ST->top==1 B) ST->top==-