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

《数据结构》习题集：第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 结点时，则执⾏（ B ）

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 保存被删除结点的值，则执⾏（B ）

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，1B、1，2，3，4

C、1，4，3，2

D、3，2，4，1

8.循环队列SQ 采⽤数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队

列为空的条件是（ D ）A、Q.rear-Q.front==n

B、Q.rear-Q.front-1==n

C、Q.front==Q.rear

1/15 第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，则判定此循环队列为空的条件是（ ）

1 / 7 20XX年复习资料

大

学

复

习

资

料

专 业：

班 级：

科目老师：

日 期：

2 / 7 第3章作业参考答案

1.

1,4,3,5,2)能，IOIIIOOIOO；

(1,4,2,3,5)不能，因为4先于3和2出栈，4出栈时，2和3都在栈中，且2压在3之下，故只能3先出栈才能2出栈。

*若借助栈由输入序列1,2, … , n得到输出序列为p1, p2, …, pn，则在输出序列中不可能出现这样的情形：存在着i

2. 借助栈T，删除栈S中元素值为k的元素。

4.

//定义双向栈类

template //声明一个类模板

class DSqStack

{

public: //双向栈类的各成员函数

DSqStack(int m = 20XXXX0);

~DSqStack();

bool Empty(int i) const;

ElemType & Top(int i) const;

void Push(const ElemType &e,int i);

void Pop(int i);

private: //双向栈类的数据成员

ElemType *base; //基地址指针

int top[2]; //栈顶指针

int size; //向量空间大小

};

//构造函数，分配m个结点的顺序空间，构造一个空的双向栈。

template

DSqStack ::DSqStack(int m)

{

top[0] = -1;

top[1] = m;

base = new ElemType[m];

size = m;

}//DSqStack

第一节 栈

一、栈的定义及其运算

1、栈的定义

栈(Stack)：是限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一端称为栈项(top)，另一端称为栈底(bottom)。不含元素的空表称为空栈。

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

真题选解

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

隐藏答案

【答案】DCBA

【解析】根据堆栈"先进后出"的原则，若输出序列的第一个元素为D，则ABCD入栈，输出序列为DCBA

2、栈的基本运算

(1)置空栈InitStack(&S)：构造一个空栈S。