针对下图所示的有向图，从结点V出发广度遍历所得结点序列和深度遍历所得结点序列分别是..

2014年下半年上午试卷综合知识

第 51 题


知识点	栈与队列
关键词	遍历有向图
章/节	嵌入式系统程序设计

针对下图所示的有向图，从结点V,出发广度遍历所得结点序列和深度遍历所得结点序列分别是（51）。

A. V₁,V₂,V₃,V₄,V₅,V₆,V₇,V₈和V₁,V₂,V₃,V₈,V₅,V₇,V₄,V₆

B. V₁,V₂,V₄,V₆,V₃,V₅,V₇,V₈和V₁,V₂,V₃,V₈,V₅,V₇,V₄,V₆

C. V₁,V₂,V₄,V₆,V₃,V₅,V₇,V₈和V₁,V₂,V₃,V₈,V₄,V₅,V₆,V₇

D. V₁,V₂,V₄,V₆,V₇,V₃,V₅,V₈和V₁,V₂,V₃,V₈,V₅,V₇,V₄,V₆

相关试题 C程序设计基础

第60题

2017年下半年

执行下面C语言程序段的结果是（60)。
main ( ) {
int x=l,a=l,b=l;
switch(x) {
case 0: b++;
case 1: a++;
case 2: a++; b++;
}
printf (”a=%d..

第60题

2015年下半年

变量W_data定义如下：

则变量W_data所占的内存存储空间可表示为(60)。

第39题

2012年下半年

分别运行下列两段程序后，y1和y2的值是（39）。
程序段1：

知识点讲解

· 栈与队列

栈与队列

栈和队列是程序中常用的两种数据结构，其特点在于运算受到了限制：栈按“后进先出”的规则进行修改，队列按“先进先出”的规则进行修改。

栈

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出（FILO，或后进先出）的线性表。在栈中，进行插入和删除操作的一端称为栈顶（top），相应地，另一端称为栈底（bottom）。不含数据元素的栈称为空栈。

栈的基本运算如下。

（1）初始化栈initStack（S）：创建一个空栈S。

（2）判栈空isEmpty（S）：当栈S为空栈时返回“真”，否则返回“假”。

（3）入栈push（S，x）：将元素x加入栈顶，并更新栈顶指针。

（4）出栈pop（S）：将栈顶元素从栈中删除，并更新栈顶指针。

（5）读栈顶元素top（S）：返回栈顶元素的值，但不修改栈顶指针。

可以用一维数组作为栈的存储空间，同时设置指针top指示栈顶元素的位置。在这种存储方式下，需要预先定义或申请栈的存储空间，也就是说栈空间的容量是有限的。因此一个元素入栈时，需要判断是否栈满，若栈满（即栈空间中没有空闲单元），则元素入栈会发生上溢现象。

用链表作为存储结构的栈称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。链栈的表示如下图所示，其类型定义如下：

链栈示意图

以栈中元素类型为整型为例，实现栈基本运算的函数定义如下。

【函数】创建一个单链表表示的空栈。

【函数】元素入栈。

【函数】元素出栈。

【函数】读取并返回栈顶元素。

【函数】判断栈是否空。

队列

队列常用于需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。

队列是一种先进先出（FIFO）的线性表，只允许在队列的一端插入元素，而在另一端删除元素。在队列中，允许插入元素的一端称为队尾（rear），允许删除元素的一端称为队头（front）。

队列的基本运算如下。

（1）初始化队列initQueue（Q）：创建一个空的队列Q。

（2）判队空isEmpty（Q）：当队列为空时返回“真”值，否则返回“假”值。

（3）入队enQueue（Q，x）：将元素x加入到队列Q的队尾，并更新队尾指针。

（4）出队delQueue（Q）：将队头元素从队列Q中删除，并更新队头指针。

（5）取队头元素frontQueue（Q）：返回队头元素的值，但不更新队头指针。

可以用一组地址连续的存储单元存放队列中的元素，称为顺序队列。由于队中元素的插入和删除限定在两端进行，因此设置队头指针和队尾指针，分别指示出当前的队首元素和队尾元素。

设队列Q的容量为6，其队头指针为front，队尾指针为rear，头、尾指针和队列中元素之间的关系如下图所示。

队列的头、尾指针与队列中元素之间的关系

在顺序队列中，为了降低运算的复杂度，元素入队时只修改队尾指针，元素出队时只修改队头指针。由于顺序队列的存储空间容量是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到该上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。若将顺序队列设想为一个环状结构（通过整除取余运算实现），则可维持入队、出队操作运算的简单性，如下图所示，称之为循环队列。

循环队列的头、尾指针示意图

设循环队列Q的容量为MAXSIZE，初始时队列为空，且Q.rear和Q.front都等于0，如下图（a）所示。元素入队时修改队尾指针，即令Q.rear=（Q.rear+1）% MAXSIZE，如下图（b）所示。元素出队时修改队头指针，即令Q.front=（Q.front+1）% MAXSIZE，如下图（c）所示。

循环队列的头、尾指针示意图

根据队列操作的定义，当出队操作导致队列变为空时，就有Q.rear==Q.front，如上图（d）所示；若入队列操作导致队列满，则也有Q.rear==Q.front，如上图（e）所示。在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的，此时仅根据Q.rear和Q.front之间的关系无法判定队列的状态。为了区分队空和队满，可采用两种处理方式：其一是设置一个标志域，以区别头、尾指针的值相同时队列是空还是满；其二是牺牲一个元素空间，约定以“队列的尾指针所指位置的下一个位置是头指针”表示队列满，如上图（f）所示，而头、尾指针的值相同时表示队列为空。

设队列中的元素类型为整型，则循环队列的类型定义为：

【函数】创建一个空的循环队列。

【函数】判断队列是否为空。

【函数】元素入循环队列。

【函数】元素出循环队列。

队列的链式存储也称为链队列。为了便于操作，可给链队列添加一个头结点，并令头指针指向头结点，如下图所示。在这种情况下，队列为空的判定条件是头指针和尾指针相同，且均指向头结点。

链队列示意图

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5