数据结构实验二栈和队列

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

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. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

2. 熟练掌握栈类型的两种实现方法。

3. 熟练掌握循环队列和链队列的基本操作实现算法。 二、实验内容

用队列求解迷宫问题 [问题描述]

以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 [基本要求]

实现一个以顺序存储结构的队列类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，pre）的形式输出，其中：（i，j）指示迷宫中的一个坐标，pre表示本路径中上一个方块在队列中的下标。

[测试数据] 由学生任意指定。

三、源代码

# include #define M 5 #define N 5

//行数 //列数

//队最多元素个数

//一个迷宫,其四周要加上均为1的外框{1,1,

#define MaxSize 100 int mg[M+2][N+2]={ {1,1,1,1,1,1,1}, {1,0,0,0,0,0,1}, {1,0,1,0,0,1,1},

{1,0,1,0,0,1,1}, {1

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．当利用大小为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==-