当前位置：文档库 › 数据结构第3章栈和队列

数据结构第3章栈和队列

第3章栈和队列

一选择题

1. 对于栈操作数据的原则是（）。

A. 先进先出

B. 后进先出

C. 后进后出

D. 不分顺序

2. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元

素是（）。

A. 不确定

B. n-i+1

C. i

D. n-i

3. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是

（）。

A. i-j-1

B. i-j

C. j-i+1

D. 不确定的

4. 有六个元素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

5．设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。

A. 5 1 2 3 4

B. 4 5 1 3 2

C. 4 3 1 2 5

D. 3 2 1 5 4

6．输入序列为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

7．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是

( )。

A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1

C. top:=top-1; V [top]:=x

D. V [top]:=x; top:=top-1

8．若栈采用顺序存储方式存储，现两栈共享空间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

top[1]=top[2]

9．栈在（）中应用。

A. 递归调用

B. 子程序调用

C. 表达式求值

D. A，Ｂ，Ｃ

10. 一个递归算法必须包括（）。

A. 递归部分

B. 终止条件和递归部分

C. 迭代部分

D.终止条件和迭代部分

11.. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。

A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈

12. 用链接方式存储的队列，在进行删除运算时（）。

A. 仅修改头指针

B. 仅修改尾指针

C. 头、尾指针都要修改

D. 头、尾指针

可能都要修改

13. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中

的元素个数为（）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m

D．(rear-front)%m

14. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。

A. (rear+1) MOD n=front

B. rear=front

C．rear+1=front D. (rear-l) MOD n=front

15. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个

元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少

应该是( )。

A． 6 B. 4 C. 3 D. 2

16．某个车站呈狭长型，宽度只能容下一辆车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入纪录为：“进，出，进，进，进，出，出，进，进，进，出，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（）。

A．1，2，3，4，5B．1，4，3，7，6C．1，2，4，5，7D．1，4，3，7，2 二判断题

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

2. 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（）

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

4. 栈和队列都是限制存取点的线性结构。（）

5. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（）

6. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）

7. 循环队列也存在空间溢出问题。（）

三填空题

1．栈是_______的线性表，其运算遵循_______的原则。

2．_______是限定仅在表尾进行插入或删除操作的线性表。

3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。

4. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。

5．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。

6．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。

7. 表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。

8. 循环队列的引入，目的是为了克服_______。

9. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。

10．设循环队列用数组A[1..M]表示，队首、队尾指针分别是front和rear，判定队满的条件为_______。

11. 设循环队列存放在向量sq.data[0..M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。

12．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。

15．设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为_______。

四应用题

1. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D

最先出栈（即C第一个且D第二个出栈）的次序有哪几个？

2. 设一数列的输入顺序为123456，若采用栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。

（1）能否得到输出顺序为325641的序列。

（2）能否得到输出顺序为154623的序列。

3. 用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C语言写出入栈的操作。

五算法设计题

1. 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。

2. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（1）下面所示的序列中哪些是合法的？

A. IOIIOIOO

B. IOOIOIIO

C. IIIOIOIO

D. IIIOOIOO

（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

3. 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）

4. 试将下列递归过程改写为非递归过程。

void test(int &sum)

{ int x；

scanf(x)；

if(x=0) sum=0 else {test(sum); sum+=x;}

printf(sum)；

}

完整版数据结构习题集第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 结点时，则执行（ 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;

数据结构基础练习(栈和队列)

数据结构基础练习（栈和队列）学号姓名蓝礼巍班级 . 一、选择题 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 6．在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是b 。 A. f->next=s; f=s; B. r->next=s; r=s; C. s->next=s; r=s; D. s->next=f; f=s; 7．如果5个元素出栈的顺序是1、2、3、4、5，则进栈的顺序可能是 c 。 A．3、5、4、1、2 B．1、4、5、3、2 C．5、4、1、3、2 D．2、4、3、1、5 8．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。 A．i B．n-i C．n-i+1 D．不确定二、填空题 1．栈和队列是一种特殊的线性表，其特殊性体现在是运算受限线性表。设现有元素e1,e2,e3,e4,e5和e6依次进栈，若出栈的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少是 3 。 2．顺序循环队列中，设队头指针为front，队尾指针为rear，队中最多可有MAX个元素，采用少用一个存储单元的方法区分队满与队空问题，则元素入队列时队尾指针的变化为 Rear=(rear+1)%MAX ；元素出队列时队头指针的变化为fort=(fotr+1)%MAX ；队列中的元素个数为 (rear-fort+MAX)%MAX 。若则可用表示队满的判别条件，队空的判别条件仍然为 rear==fort 。三、解答题

实验三栈和队列的应用

实验三栈和队列的应用 1、实验目的（1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。（2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；（3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法；（4）掌握栈和队列的应用； 2、实验内容 1）栈和队列基本操作实现（1）栈的基本操作：采用顺序存储或链式存储结构（数据类型自定义），实现初始化栈、判栈是否为空、入栈、出栈、读取栈顶元素等基本操作，栈的存储结构自定义。（2）队列的基本操作：实现循环队列或链队列的初始化、入队列、出队列、求队列中元素个数、判队列空等操作，队列的存储结构自定义。 2）栈和队列的应用（1）利用栈的基本操作将一个十进制的正整数转换成二进制数据，并将其转换结果输出。提示：利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：十进制整数X和R作为形参初始化栈只要Ｘ不为0重复做下列动作将x%R入栈 X=X/R 只要栈不为空重复做下列动作栈顶出栈输出栈顶元素 (2) 利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Right”，否则输出“Wrong”。

(3) 假设循环队列中只设rear（队尾）和quelen（元素个数据）来分别表示队尾元素的位置和队中元素的个数，写出相应的入队和出队程序。（4）选作题：编写程序实现对一个输入表达式的括号配对。 3、实验步骤（1）理解栈的基本工作原理；（2）仔细分析实验内容，给出其算法和流程图；（3）用C语言实现该算法；（4）给出测试数据，并分析其结果；（5）在实验报告册上写出实验过程。 4、实验帮助算法为： 1) 定义栈的顺序存取结构 2) 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3) 定义一个函数用来实现上面问题：十进制整数X和R作为形参初始化栈只要X不为0重复做下列动作将X % R入栈 X=X/R 只要栈不为空重复做下列动作栈顶出栈输出栈顶元素 5、算法描述（1））初始化栈S (创建一个空栈S) void initstack(sqstack *S) { S->base=(ElemType *) malloc(INITSIZE*sizeof(ElemType)); if(!S->base) exit (-1); S->top=0; /*空栈标志*/ S->stacksize = INITSIZE; } (2) 获取栈顶元素 int gettop(sqstack S,ElemType *e) //顺序钱 { if ( S.top==0 ) /* 栈空 */

数据结构_实验三_栈和队列及其应用

实验编号：3四川师大《数据结构》实验报告2016年10月29日实验三栈和队列及其应用_ 一．实验目的及要求（1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们；（2）本实验训练的要点是“栈”的观点及其典型用法；（3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。二．实验内容（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；（2）应用栈的基本操作，实现数制转换（任意进制）；（3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）；（4）利用栈实现任一个表达式中的语法检查（括号的匹配）。（5）利用栈实现表达式的求值。注：（1）～（3）必做，（4）～（5）选做。三．主要仪器设备及软件（1）PC机（2）Dev C++ ,Visual C++, VS2010等四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存：代码部分：栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl;

cout << "你的选择是：" ; } 链式储存：代码部分：栈"<>select; switch (select){ case 0:break; case 1: cout<<"push data:"; cin>>e; if(push(L,e)){

数据结构堆栈与队列实验报告

实验二堆栈和队列实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。实验原理：堆栈顺序存储结构下的基本算法；堆栈链式存储结构下的基本算法；队列顺序存储结构下的基本算法；队列链式存储结构下的基本算法；实验内容：第一题链式堆栈设计。要求（1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素；（3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求：（1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空；（2）编写主函数进行测试。程序代码：第一题：（1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/

实验二_栈、队列地实现与应用

实验二栈、队列的实现及应用实验课程名：数据结构与算法专业班级：学号：：

/*构造空顺序栈*/ int InitStack(SqStack *S) //InitStack() sub-function { S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base) { printf("分配空间失败!\n"); return (ERROR); } S->top = S->base; S->stacksize = STACK_INIT_SIZE; printf("栈初始化成功！\n"); return (OK); } //InitStack() end /*取顺序栈顶元素*/ int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function { if (S->top == S->base) { printf("栈为空!\n"); //if empty SqStack return (ERROR); } *e = *(S->top - 1); return (OK); } //GetTop() end /*将元素压入顺序栈*/ int Push(SqStack *S) //Push() sub-function { SElemType e; if (S->top - S->base>S->stacksize) { S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT*sizeof(SElemType))); if (!S->base) { printf("存储空间分配失败!\n"); return (ERROR); } S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量x

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

第三章栈和队列试题一、单项选择题 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;

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

数据结构练习第三章栈和队列一、选择题 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．队列的插入操作是在（）进行。

数据结构习题3 栈和队列

习题3 栈和队列 3.1 单项选择题 1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。 A. i B. n-i C. n-i+1 D. 不确定 3. 栈结构通常采用的两种存储结构是____。 A. 顺序存储结构和链式存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构 4. 判定一个顺序栈ST（最多元素为m）为空的条件是____。 A. top !=0 B. top= =0 C. top !=m D. top= =m-1 5. 判定一个顺序栈ST（最多元素为m）为栈满的条件是____。 A. top！=0 B. top= =0 C. top！=m D. top= =m-1 6. 栈的特点是____，队列的特点是____。 A. 先进先出 B. 先进后出 7. 向一个栈顶指针为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; 8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__ __。(不带头结点) 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，则队列的出队时输出序列是____ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1 10. 判定一个循环队列QU（最多元素为m）为空的条件是____。 A. rear - front= =m B. rear-front-1= =m C. front= = rear D. front= = rear+1 11. 判定一个循环队列QU（最多元素为m, m= =Maxsize-1）为满队列的条件是____。 A. ((rear- front)+ Maxsize)% Maxsize = =m B. rear-front-1= =m C. front= =rear D. front= = rear+1 12. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。 A. (rear-front+m)%m B. rear-front+1

数据结构栈和队列实验报告.doc

南京信息工程大学实验（实习）报告实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌系计算机系专业软件工程年级2016 班次(1) 姓名学号一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作二、实验内容 1、用栈解决以下问题：（1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序：（1）求n！。（2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。

3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换：代码如下： #include #include using namespace std; int main() { stack s; //栈s; int n,radix; printf("请输入要转换的十进制非负整数： "); scanf("%d",&n); printf("请输入目标进制： "); scanf("%d",&radix);

printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值代码如下： #include #include #include #include #define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status;

数据结构第3章栈和队列自测卷答案(供参考)

head 1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的前一个位置。 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先移动栈顶指针，后存入元素。 7. 从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。 8.带表头结点的空循环双向链表的长度等于 0 。解：二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）（ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。（ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。错，不一定吧？调用子程序或函数常用，CPU 中也用队列。（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（ × ）5. 栈和链表是两种不同的数据结构。错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。（ × ）6. 栈和队列是一种非线性数据结构。错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。错，后半句不对。（ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。错，有可能。三、单项选择题（每小题1分，共20分）（ 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。（若不要求顺序出栈，则输出序列不确定）（ B ）3.判定一个栈ST （最多元素为m0）为空的条件是

实验二栈队列的实现及应用

百度文库-让每个人平等地提升自我实验二栈、队列的实现及应用实验课程名：数据结构与算法专业班级：_ 学号：__________ 姓名： _ 实验时间： ____ 实验地点：指导教师：冯珊__________ 一、实验目的 1掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ typedef struct

1 2 3 4 5远兀 1 一 7U- 元谴段囑 :> o 1 2 3 R * 元元栈書 t 出一 ^ 零遐次 :± 谨虚 1 2 3 ^ 5 I B

D 认戯握结IVl 匚on&ol eAp pli cation!\[>ebu g\Con 5 o-leApp li cation 1 .exe :1 刖人操作谊睪代码(05):2 : h E s 选的操一兀一 b 一丁一丁栈 ? 遐次嘆區 1 2 3 4 5 5 ^ 元元栈 S 退、灵岀祓 S I ■ i 9 I I I i 主至 ..T' 一兀元栈￡ 1 2 3 4 5 \Z

百度文库 -让每个人平等地提升自我 P入操隹选择代码（0-5>:4 派元素的是 ; 栈化出取示艮 i元一一选的操元 -> 入中 >c 1- 苴翻（05）: 5 栈化亍 1 2 元元 Is 务一（2）:完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China , Japan, France，India ，Australia ），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。要求生成链栈时，从键盘上读取数据元素。（1）源代码：#i nclude<> #in clude<> #in clude<> # define OK 1 # define ERROR 0 typedef char DataType; /*链式栈的存储类型*/ typedef struct SNode

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

习题三栈和队列一单项选择题 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

数据结构栈和队列

实验二栈和队列一、实验目的 1. 掌握栈的顺序表示和实现 2. 掌握队列的链式表示和实现二、实验内容 1. 编写一个程序实现顺序栈的各种基本运算。 2. 实现队列的链式表示和实现。三、实验步骤 1. 初始化顺序栈 2. 插入元素 3. 删除栈顶元素 4. 取栈顶元素 5. 遍历顺序栈 6. 置空顺序栈 7. 初始化并建立链队列 8. 入链队列 9. 出链队列 10. 遍历链队列四、实现提示 1. /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x)

{if(p->toptop=p->top+1; /*栈顶+1*/ p->stack[p->top]=x; } /*数据入栈*/ } /*出栈函数*/ ElemType Pop(SqStack *p) {x=p->stack[p->top]; /*将栈顶元素赋给x*/ p->top=p->top-1; } /*栈顶-1*/ /*获取栈顶元素函数*/ ElemType GetTop(SqStack *p) { x=p->stack[p->top];} /*遍历顺序栈函数*/ void OutStack(SqStack *p) { for(i=p->top;i>=0;i--) printf("第%d个数据元素是：%6d\n",i,p->stack[i]);} /*置空顺序栈函数*/ void setEmpty(SqStack *p) { p->top= -1;} 2. /*定义链队列*/ typedef struct Qnode { ElemType data; struct Qnode *next; }Qnodetype; typedef struct { Qnodetype *front; Qnodetype *rear; }Lqueue; /*初始化并建立链队列函数*/ void creat(Lqueue *q)

数据结构栈和队列实验报告

《数据结构》课程实验报告实验名称栈和队列实验序号实验日期姓名院系班级学号专业指导教师成绩教师评语一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。二、实验项目摘要编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s；（2）判断栈s是否非空；（3）依次进栈元素a,b,c,d,e；（4）判断栈s是否非空；（5）输出栈长度；（6）输出从栈顶到栈底元素；（7）输出出栈序列；（8）判断栈s是否非空；（9）释放栈。编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化队列q；（2）判断队列q是否非空；（3）依次进队列a,b,c；（4）出队一个元素，输出该元素；（5）输出队列q的元素个数；（6）依次进队列元素d,e,f；（7）输出队列q的元素个数；（8）输出出队序列；（9）释放队列。

三、实验预习内容栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素）队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列）三、实验结果与分析 3-1 #define maxsize 100 #include #include using namespace std; typedef char ElemType; typedef struct { ElemType data[maxsize]; int top; } SqStack; void InitStack(SqStack * &s) { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; } int StackEmpty(SqStack *s) { return(s->top==-1); } int Push(SqStack *&s,ElemType e) { if(s->top==maxsize-1) return 0; s->top++; s->data[s->top]=e; return 1; } int Pop(SqStack *&s,ElemType &e) { if(s->top==-1) return 0; e=s->data[s->top];

栈和队列综合实验报告

栈和队列综合实验报告一、实验目的（1）能够利用栈和队列的基本运算进行相关操作。（2）进一步熟悉文件的应用（3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C＋＋的计算机。本次实验共计4学时。三、实验内容以下两个实验任选一个。 1、迷宫求解设计一个迷宫求解程序，要求如下：以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。能任意设定的迷宫（选作）如果有通路，列出所有通路提示：以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：11

01 01 01 01 01 01 01 11 入口位置：1 1 出口位置：8 8 四、重要数据结构 typedef struct{ int j[100]; int top;栈顶指针，一直指向栈顶 }stack;//存放路径的栈 int s[4][2]={{0,0},{0,0},{0,0},{0,0}}; //用于存放最近的四步路径坐标的数组，是即使改变的，即走一步，便将之前的坐标向前移一步，将最早的一步坐标覆盖掉，新的一步放入数组末尾其实功能和队列一样。其作用是用来判断是否产生了由于本程序算法产生的“田”字方格内的死循环而准备的，用于帮助跳出循环。五、实现思路分析 if(a[m][n+1]==0&&k!=3){ n++; k=1; o=0; }else if(a[m+1][n]==0&&k!=4){ m++;

k=2; o=0; }else if(a[m][n-1]==0&&k!=1){ n--; k=3; o=0; }else if(a[m-1][n]==0&&k!=2){ m--; k=4; o=0; }else{ o++;} if(o>=2){ k=0; }//向所在方格的四个方向探路，探路顺序为→↓←↑（顺时针），其中if判断条件内的&&k!=n和每个语句块中的对k赋值是为防止其走回头路进入死循环，而最后一个else{}内语句是为了防止进入死路时，不能走回头路而造成的死循环。 push(q,m,n);//没进行一次循环都会讲前进的路径入栈。 if (pushf(&s[0][0],m,n)==0){ k=3;}//用来判断是否产生了由于本程序探路算法产生的“田”字方格内的死循环而准备的，用于帮助跳出田字循环。同时会将路径存入用于下次判断六、程序调试问题分析最开始写完时是没有死路回头机制的，然后添加了两步内寻路不回头机制。第二个是“田”字循环问题，解决方法是加入了一个记录最近四步用的数组和一个判断田字循环的函数pushf。