结点

2019年3月计算机二级C语言考试冲刺练习009 第1页：计算机二级C语言考试冲刺练习1-10 1.某循环队列的存储空间为Q(1：m)，初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m一1，real"=m，则该循环队列中的元素个数为( )。 2.能从任意一个结点开始没有重复地扫描到所有结点的数据结构是( )

给定一棵树，树的某个结点上有一个硬币，在某一时刻硬币会等概率地移动到邻接结点上，问硬币移动到邻接结点上的期望距离。 设 代表 结点走到其父结点 的期望距离，则有： 分子中的前半部分代表直接走向了父结点，后半部分代表先走向了子结点再由子结点走回来然后再向父结点走；分母 代表从 结点走向其任何邻接点的概率相同。 当树上所有边的边权都为 时，上式可化为： 即 子树的所有结点的度数和，也即 子树大小的两倍 （每个结点连向其父亲的边都有且只有一条，除 与 之间的边只有 点度数的贡献外，每条边会产生 点度数的贡献）

给定一棵二叉树，你需要计算它的直径长度。 一棵二叉树的直径长度是任意两个结点路径长度中的最大值。 提示：这条路径可能穿过也可能不穿过根结点

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。 以下面这道题为例，介绍一下树形 DP 的一般过程

无线通信组网中的单跳(single-hop)和多跳(multi-hop) 在传统的无线局域网(WLAN)中，每个客户端均通过一条与AP相连的无线链路来访问网络，用户如果要进行相互通信的话，必须首先访问一个固定的接入点(AP)，这种网络结构被称为单跳网络 在无线网络中，任何无线设备节点都可以同时作为AP和路由器，网络中的每个节点都可以发送和接收信号，每个节点都可以与一个或者多个对等节点进行直接通信。 在无线多跳网络中，源结点到目的结点之间的典型路径是由多跳组成的，该路径上的中间结点充当转发结点。因此，无线多跳网络中一个结点具有两种功能，首先结点可以充当端结点产生或接受数据分组，其次结点可以充当路由器对来自其它结点的数据分组进行转发

2.满二叉树(Full Binary Tree)： 要么是叶子结点(结点的度为0)，要么结点同时具有左右子树(结点的度为2)。 3.完全二叉树(Complete Binary Tree)： 每层结点都完全填满，在最后一层上如果不是满的，则只缺少右边的若干结点。 4.完美二叉树(Perfect Binary Tree) 所有的非叶子结点都有两个孩子，所有的叶子结点都在同一层

给定一棵树，树的某个结点上有一个硬币，在某一时刻硬币会等概率地移动到邻接结点上，问硬币移动到邻接结点上的期望距离。 设 代表 结点走到其父结点 的期望距离，则有： 分子中的前半部分代表直接走向了父结点，后半部分代表先走向了子结点再由子结点走回来然后再向父结点走；分母 代表从 结点走向其任何邻接点的概率相同。 当树上所有边的边权都为 时，上式可化为： 即 子树的所有结点的度数和，也即 子树大小的两倍 （每个结点连向其父亲的边都有且只有一条，除 与 之间的边只有 点度数的贡献外，每条边会产生 点度数的贡献）

数据的逻辑结构：结构定义中的“关系” 描述的是数据元素之间的逻辑关系，又称为逻辑结构，比如平常教学中所画的内存图，数组等为数据的逻辑结构. 数据的物理结构：数据结构在计算机中的实际表示形式称为数据的物理结构又称为物理存储。 线性结构中又分为顺序表和链表（按物理存储结构划分），顺序表按顺序存储结构，链表按链式存储结构。 按顺序存储结构存储，内存中分配连续一段地址

Prim算法是直接查找，多次寻找邻边的权重最小值，而Kruskal是需要先对权重排序后查找的；Kruskal在算法效率上是比Prim快的，因为Kruskal只需一次对权重的排序就能找到最小生成树，而Prim算法需要多次对邻边排序才能找到。 深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点；广度遍历类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。 Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题

拆点是一种图论建模思想，常用于 网络流，用来处理 点权或者点的流量限制 的问题，也常用于 分层图。 如果把结点转化成边，那么这个问题就可以套板子解决了。 我们考虑把有流量限制的结点转化成这样一种形式：由两个结点 和一条边 组成的部分

给定一棵树，树的某个结点上有一个硬币，在某一时刻硬币会等概率地移动到邻接结点上，问硬币移动到邻接结点上的期望距离。 设 代表 结点走到其父结点 的期望距离，则有： 分子中的前半部分代表直接走向了父结点，后半部分代表先走向了子结点再由子结点走回来然后再向父结点走；分母 代表从 结点走向其任何邻接点的概率相同。 当树上所有边的边权都为 时，上式可化为： 即 子树的所有结点的度数和，也即 子树大小的两倍 （每个结点连向其父亲的边都有且只有一条，除 与 之间的边只有 点度数的贡献外，每条边会产生 点度数的贡献）

既然理解了链表的构成，对链表的访问也就不成问题了。不过要特别注意的是，对于数组，我们可以利用下标直接访问任何一个元素（这被称为“随机访问”），而对于单向链表，只能从头结点开始，依次进行“顺序访问”。 假设我们已经按照前文创建了一个链表，下面我们设计一个函数，查找是否存在某数据： 尤其要注意第3行，由于我们的链表有不存储数据的头结点，要先将指针指向下一个结点，再访问数据

线性表如果要频繁的执行插入和删除操作，以下哪种存储结构效率更高__？ 在一颗二叉树上第5层的结点数最多是__? 针对如下描述，请问请问 E 的下⼀个是__? 关于链表特点的说法中，下⾯哪些不是链表的特征? 数据结构中，单循环链表的主要优点是__? 假设以行序为主序存储二维数组 A=array[100][100]，设每个数据元素占2个存储单元，基地址为10，则A[55]的地址为__? 用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是__? 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是__?

二叉树是n(n>=0)个结点的有限集合： 或者为空二叉树，即n=0。 或者由一个根结点和两个互不相交的被称为跟的左子树和右子树组成。左子树和右子树又分别是一棵二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。 如上图所示，因为按层打印的顺序决定应该先打印根结点，所以我们从树的根结点开始分析。为了接下来能够打印值为8的结点的两个子结点，我们应该在遍历该结点时把值为6和10的两个结点保存到一个容器里，现在容器内就有两个结点了

二叉树的问题用分治的思想来做都比较简单，这道题首先想到的就是递归。 我们要求21的坡度，其实就是求21的左子树上的结点之和以及右子树上的结点之和的差值。21的左子树上的结点之和 = 7 + 7的左子树之和 + 7的右子树之和，并且在求和的同时我们可以把坡度算出来