以下关于栈和队列的叙述中，错误的是（12）。

免费智能真题库 > 历年试卷 > 网络管理员 > 2014年上半年网络管理员上午试卷综合知识

第12题

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

关键词：队列章/节：软件基础知识

A. 栈和队列都是线性的数据结构

B. 栈和队列都不允许在非端口位置插入和删除元素

C. 一个序列经过一个初始为空的栈后，元素的排列次序一定不变

D. 一个序列经过一个初始为空的队列后，元素的排列次序不变

相关试题：数据结构基础

更多>

第9题 2017年上半年

50%

( )图像通过使用色彩查找表来获得图像颜色。

第51题 2015年上半年

43%

在进行域名解析过程中，若主域名服务器出现故障，则在（51）上进行查找；若主域名服务器工作正常但未能查找到记录，由（52）负责..

第24题 2021年上半年

67%

IP报文传输前默认使用(24)协议查找MAC地址;出现报文传输错误时使用(25)协议来报告差错。


知识点讲解
· 数据结构 · 队列 · 栈 · 栈和队列

数据结构

根据数据元素之间关系的不同特性，通常有下列4类基本的逻辑结构，即集合结构、线性结构、树形结构、图形结构。

1）线性结构

线性表是最常用且最简单的一种数据结构。线性表中除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，每个元素都只有一个直接后继。

栈是限定仅在表尾进行插入或删除操作的线性表，是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。

队列是一种先进先出（FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。

2）树

树是n（n≥0）个互不相交的有限集，当n=0时称为空树。在一棵非空树中，有且仅有一个节点称为根节点；当n>1时，其余的节点可分为若干个不相交的集合，其中每一个集合本身又是一棵树，这些集合称为根节点的子树。

3）图

图是由两个集合V和E组成的二元组，记为G=（V, E），其中V是顶点的非空有限集合，E是图中边的有限集合。

队列

队列的定义

队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头（front）。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。

由队列的定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（First In First Out, FIFO）的原则组织数据的，因此，队列也被称为"先进先出"表。

下图是一个队列的进出示意图，通常用指针front指示队头的位置，用指针rear指向队尾的位置。

队列的进出示意图

队列的基本操作

队列的基本操作主要有以下6种。

.InitQueue（&Q）：初始化操作，构造一个队列Q。

.QueueEmpty（Q）：若栈Q为空队列，返回1，否则返回0。

.EQueue（&Q, e）：插入元素e到队列Q的尾部。

.OQueue（&Q,&e）：删除Q的队首元素，并用e返回其值。

.GetQhead（Q,&e）：用e返回Q的队首元素。

.ClearQueue（&Q）：将Q清空为空队。

队列的顺序存储结构

顺序存储结构采用一维数组（向量）实现，设队列头指针front和队列尾指针rear，并且假设front指向队头元素的前一位置，rear指向队尾元素。若不考虑队满，则入队操作语句为Q[rear++]=x；若不考虑队空，则出队操作语句为x=Q[++front]。当然，出队时，并不一定需要队头元素（与退栈类似）。

按上述的做法，有可能出现假溢出，即队尾已到达一维数组的高端，不能再入队，但因为连续出队，队列中元素个数并未达到最大值。解决这种问题，可用循环队列。在循环队列中，需要区分队空和队满：仍用front=rear表示队列空，在牺牲一个单元的前提下，用front==（rear+1）% MAX表示队列满。在这种约定下，入队操作的语句为：rear=（rear+1）%MAX, MAX, Q[rear]=x；出队操作语句为：front=（front+1）% MAX。

顺序队列的类型定义如下：

顺序队列定义为一个结构类型，该类型变量有3个数据域：data、front、rear。其中data为存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，取值范围是0~QueueSize-1。约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置，这种顺序队列说明如下。

.初始化时，设置SQ.front=SQ.rear=0。

.队头指针的引用为SQ.front，队尾指针的引用为SQ.rear。

.队空的条件为SQ.front==SQ.rear；队满的条件为SQ.front=（SQ.rear+1）% QueueSize。

.入队操作：在队列未满时，队尾指针先加1（要取模），再送值到队尾指针指向的空闲元素。出队操作：在队列非空时，队头指针先加1（要取模），再从队头指针指向的队头元素处取值。

.队列长度为（SQ.rear+QueueSize-SQ.front）% QueueSize。

特别应注意的是：在循环队列的操作中队头指针、队尾指针加1时，都要取模，以保持其值不出界。

在循环队列上队列的实现基本操作的函数如下。

1）初始化initqueue（SQueue *SQ）

2）判空QueueEmpty（SQueue SQ）

3）入队EQueue（SQueue *SQ, ElemType e）

4）出队OQueue（SQueue *SQ, ElemType *e）

5）取队首元素GetQhead（SQueue *SQ, ElemType *e）

6）清队列ClearQueue（SQueue *SQ）

队列的链式存储结构

队列的链接实现称为链队，链队实际上是一个同时带有头指针和尾指针的单链表。头指针指向队头节点，尾指针指向队尾节点即单链表的最后一个节点。为了简便，链队设计成一个带头节点的单链表。

链队的类型定义如下：

链队列的说明如下。

.队列以链表形式出现，链首节点为队头，链尾节点为队尾。

.队头指针为LQ→front，队尾指针为LQ→rear，队头元素的引用为Q→front→data，队尾元素的引用为LQ→rear→data。

.初始化时，设置LQ→front=LQ→rear=NULL。

.进队操作与链表中链尾插入操作一样；出队操作与链表中链首删除操作一样。

.队空的条件为LQ→front==NULL。理论上，只要系统内存足够大，链队是不会满的。

在链队上实现队列基本操作的函数如下。

1）队列初始化InitQueue（LQueue *LQ）

2）入队EQueue（LQueue *LQ, ElemType e）

3）出队OQueue（LQueue *LQ, ElemType *e）

4）判空QueueEmpty（LQueue *LQ）

5）取队首元素GetQhead（LQueue *LQ, ElemType *e）

6）清队列ClearQueue（LQueue *LQ）

循环队列中的边界条件判别准则

判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一个布尔变量来区别队列的空和满；二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满；三是设置一个计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

双端队列的作用

双端队列是限定插入和删除操作在线性表的两端进行，可将其看成是栈底连在一起的两个栈，但其与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的，因而每个栈只需一个指针；而双端队列允许两端进行插入和删除元素，因而每个端点必须设立两个指针，如下图所示。

双端队列的示意图

在实际应用中，可对双端队列的输出进行限制（即一个端点允许插入和删除，另一个端点只允许插入），也可对双端队列的输入进行限制（即一个端点允许插入和删除，另一个端点只允许删除）。可见，采用双端队列可增加应用中的灵活性。

栈

栈的定义

栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶，相反，栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素，不含任何数据元素的栈称为空栈。栈的特点为后进先出（Last In First Out, LIFO）。

下图是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向桟底。栈顶指针top动态反映栈的当前位置。

栈的出入示意图

栈的基本操作

栈的基本操作主要有以下6种。

.InitStack（&S）：初始化操作，构造一个空栈S。

.StackEmpty（S）：若栈S为空栈，返回1，否则返回0。

.Push（&S, e）：插入元素e为新的栈顶元素。

.Pop（&S,&e）：删除S的栈顶元素，并用e返回其值。

.GetTop（S,&e）：用e返回S的栈顶元素。

.ClearStack（&S）：将S清为空栈。

栈的顺序存储结构

栈的顺序存储用向量作为栈的存储结构，向量S表示栈，m表示栈的大小，用指针top指向栈顶位置，S[top]表示栈顶元素，当在栈中进行插入、删除操作时，都要移动栈指针；而当top=m-1时，则栈满，当top=-1时，表示栈空。同时为了避免浪费空间可以采用双栈机制，即向量的两端为栈底。

栈的顺序存储结构的C语言描述如下：

栈的说明如下。

.由于C语言的数组下标的范围从0至StackSize-1，初始化设置sq.top=-1。

.栈空条件为sq.top=-1，栈满条件为sq.top=StackSize-1。

.栈顶元素为sq.data[sq.top]。

.元素压栈的规则为：在栈不满时，先改变栈顶指针（top=top+1），再压栈。出栈时，在桟非空时，先取栈顶元素的值，再修改栈顶指针（top=top-1）。

.栈中元素的个数为当前栈顶指针加1。

在顺序栈上实现基本操作的有关函数如下。

1）初始化InitStack（SqStack *S）

2）判空StackEmpty(SqStack S）

3）压栈Push（SqStack *S, ElemType e）

4）出栈Pop（SqStack *S, ElemType *e）

5）取栈顶GetTop（SqStack *S, ElemType*e）

6）清栈ClearStack（SqStack *S）

栈的链式存储结构

栈的链式存储也叫链栈，我们把插入和删除均在链表表头进行的链表称为链栈。链栈也分有头节点和无头节点两种。带头节点的链栈操作比较方便。

链栈的节点类型定义如下：

链栈的约定与说明如下。

.栈以链表的形式出现，链表（不带头节点）首指针为S，即栈顶为S，链表尾节点为栈底。

.初始化时，S=NULL（不带头节点）；S=（LStack *），malloc（sizeof（LStack）），S→next=NULL（带头节点）。

.栈顶指针的引用为S（不带头节点）或S→next（带头节点），栈顶元素的引用为S→data（不带头节点）或S→next→data（带头节点）。

.栈空条件为S==NULL（不带头节点）或S→next=NULL（带头节点）。

.进栈操作和出栈操作与单链表在开始节点的插入和删除操作一致。

对不带头节点的链栈，其基本操作函数如下。

1）初始化initstack（LStack *S）

2）压栈（入栈）push（LStack *S, ElemType x）

3）退栈（出栈）pop（LStack *S, ElemType *x）

4）读栈顶元素gettop（LStack *S, ElemType *x）

5）判栈空isempty（LStack *S）

栈的应用

栈具有广泛的应用，例如，求表达式的值及递归到非递归等。

1）表达式求值

在源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句X=4+8×2-3；，其正确的计算结果应该是17，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为：X=12×2-3=24-3=21。这个结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先法。

2）递归到非递归

将一个递归算法转换为功能等价的非递归算法有很多方法，可以使用栈保存中间结果。其一般形式如下：

例如，求n！的递归函数如下：

使用转换成等价的非递归算法如下：

其中，st[top][0]用于存放n值，st[top][1]用于存放n！值，在初始时，设置st[top][1]为0，表不n！尚未求出。

栈和队列

栈的定义和实现

栈（Stack）是一种特殊的线性表，是限定仅在表尾进行插入或者删除操作的线性表。进行插入和删除的那一端称为栈顶（top），另一端称为栈底（bottom）。栈的插入操作和删除操作也分别简称进栈和出栈。

如果栈中有n个结点｛k₀，k₁，k₂，…, k_n-1｝，k₀为栈底，k_n-1是栈顶，则栈中结点的进栈顺序为k₀, k₁, k₂，…，k_n-1，而出栈的顺序为k_n-1, k_n-2，…, k₁,k₀，如下图所示。

栈

栈的主要操作是桟的初始化、插入和删除运算、判断栈是否为空以及读取栈顶结点的值等操作。栈的类型的描述如下：

和顺序表类似，栈的实现方式一般也有两种：顺序存储和链式存储。下面主要介绍顺序栈。由于栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制，使得它们仅能在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。一般地，可以设定一个足够大的一维数组存储栈，数组中下标为0的元素就是栈底，对于栈顶，可以设一个指针top指示它。为了方便，设定top所指的位置是下一个将要插入的结点的存储位置，这样，当top=0时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系如下图所示。

栈的状态

栈的顺序存储结构用C语言描述如下：

顺序存储栈的几个基本操作的具体实现，具体如下所示：

表达式求值

表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。

在计算机中，任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。其中操作数可以是常数，也可以是变量或常量的标识符；运算符可以是算术运算体符、关系运算符和逻辑符；界限符为左右括号和标识表达式结束的结束符。在本节中，仅讨论简单算术表达式的求值问题。在这种表达式中只含加、减、乘、除四则运算，所有的运算对象均为单变量。表达式的结束符为“#”。

表达式一般分为中缀表达式和后缀表达式，具体如下：

中缀表达式

中缀表达式是通常使用的一种表达式，中缀表达式的计算规则如下。

（1）括号内的操作先执行，括号外的操作后执行。如有多层括号，则先执行内层括号内的操作，再执行外括号内的操作。

（2）先乘除，后加减。

（3）在有多个乘除或加减运算可选择时，按从左到右的顺序执行，即优先级相同的操作符按先后次序进行。

后缀表达式

后缀表达式中只有操作数和操作符，它不再含有括号，操作符在两个操作数之后。它的计算规则非常简单，严格按照从左向右的次序依次执行每一个操作。每遇到一个操作符，就将前面的两个操作数执行相应的操作。

队列

队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头（front）。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（FIFO，first in first out）的原则组织数据的，因此，队列也被称为“先进先出”表。下面用C语言描述队列类型为：

队列分为链队列和循环队列。链队列主要采取顺序存储方式，下面主要介绍链队列的顺序存储。队列的顺序存储在c语言中可以用一维数组表示，为了标识队首和队尾，需要附设两个指针front和rear，front指示的是队列中最前面，即队首结点在数组中元素的下标，rear指示的是队尾结点在数组中元素的下标的下一个位置，也就是说rear指示的是即将插入的结点在数组中的下标。下图所示的是队列的几种状态：

队列的状态

队列的顺序存储结构用C语言描述如下：

下面介绍顺序队列的基本运算操作：

（1）初始化队列。

（2）入队列操作。

（3）出队列操作。

链队列还有链式存储结构，与顺序表的链式存储结构类似。循环队列的操作与链队列相似，这里就不再累述了。

题号导航 2014年上半年网络管理员上午试卷综合知识

本试卷我的完整做题情况



	第12题在手机中做本题