XX考研计算机数据结构复习要点

XX考研计算机数据结构复习要点核心测试点1:对队列和堆栈结构的概念理解堆栈是限制仅在表格一端插入和删除操作的线性表格，插入和删除是堆栈的顶部。如果表格中没有元素，则为空堆叠。堆栈修改是根据后进先出原则进行的。堆栈通常有两种存储结构：顺序堆栈和链堆栈。队列插入到表的一端，从表的另一端删除，允许删除的一端称为队列标头，允许插入的一端称为队列尾，队列的工作原理是先发制人的。队列还有两种存储结构：顺序存储和链存储。核心测试点2:线性表中单链表相关算法的设计与实现以下是一些基本但重要的单个链接列表相关算法：1.单个链接列表，void print List(List List)；)打印。使用一个指针导航所有关联的列表节点。2.两个升序链接列表，用于打印序号由SeqList指定且为void print lots (list tarList，list seq list)的tarList的相应元素；使用两个指针分别遍历两个链接的列表，每次检出序列链接列表中的一个序列号时，根据该序列号到达目标链接列表指定节点。3.两个升序链接列表的交叉点，List Intersect(List L1，List L2)；4.合并两个升序链接列表，List Join(List L1，List L2)；5.单链路列表位置反向，void reverse(list l)；使用三个指针表示前置任务、当前和后置节点，分别将当前节点的Next指向前置节点，然后向后遍历到关联列表的末尾。核心测试点3:遍历二叉树遍历过程是将非线性结构的二叉树节点按线性序列排列的过程。二叉树遍历方法可以分为两类：从根节点开始，从上到下，从左到右进行一层遍历的“宽度优先”方法。另一个类是“深度优先级方法”。即，一个子树的一个子树的遍历。从二叉树结构的整体来看，左、右子树可以分为三部分，即使遍历二叉树也是如此。如果将d设置为根节点，将l设置为左侧子树，将r设置为右侧子树，则DLR的总共6种组合(DLR、DRL、LDR、LRD、RDL和RLD)。如果存在左右方向的限制，则只有三种类型的DLR、LDR和LRD具有第一种(前一种)顺序(第一种根顺序)、中间顺序(中间根顺序、对称)和最后一种顺序(最后一种根顺序)。三种遍历递归算法是：1.第一顺序(DLR)如果二进制树为空，则为空。否则，是否访问根节点？先遍历左边的子树吗？依次导航右侧的子树。2.中间顺序(LDR)如果二叉树为空，则为空，否则遍历左侧子树？存取根节点？遍历中间顺序右侧的子树。3.后置顺序(LRD)如果二进制树为空，则为空。否则，将遍历左侧子树。依次导航右侧的子树？存取根节点。核心测试点4:计算完整二叉树的相关节点数整个二进制树的定义：只有当每个节点与深度为k的整个二进制树的编号为1到n的节点一一对应时，具有n个节点的二进制树才称为整个二进制树。二进制树的树叶总数为(n 1)/2去除整数。考研计算机核心测试点5:福雷斯特和二叉树之间转换和转换过程中节点之间的关系将树转换为二叉树的方法如下：1.在树的所有相邻兄弟之间添加一个连接。2.对于树中的每个节点，只保留与第一个子节点的连接，删除与其他子节点的连接。3.旋转树根节点，以顺时针方向倾斜整个树，使结构清晰。要将森林转换为二叉树，请执行以下操作：1.将森林中的每棵树转换为相应的二叉树。2.第一个二进制树保持不动，从第二个二进制树开始，依次使用下一个二进制树的根节点作为前一个二进制树根节点的右侧子节点，连接所有二进制树后，生成的二进制树将转换为树系并获得的二进制树。树和森林都可以转换成二叉树。区别在于，树转换成的二叉树，根节点不一定有右边的孩子，森林转换后，二叉树在根节点有右边的孩子。将二叉树还原到树或树系，如下所示：1.如果某个节点是那个父母的左边孩子，那个节点的右边孩子，右边孩子的右边孩子，节点的两个父节点通过线连接。2.删除原始二进制树的所有父节点和右侧子节点的连接。3.明确树木或森林结构的第一，二阶段。核心测试点6:对全向连通图性质的理解无向图的每个边在顶点计算中用于计算两次(与边2关联的两个顶点)，因此所有顶点的度数都是偶数。n个顶点大于或等于N-1的全向连接图。在“无向连接”图形中，所有顶点的角度都可以大于1。核心测试点7:对m阶b树定义的理解m次b树符合以下条件：1.每个节点最多包含m个子树。2.除根节点外，其他每个分支至少有两个子树。3.根节点至少有两个子树(b树中只有一个节点时除外)。所有叶节点都位于同一层上。b树的叶节点被视为外部节点，不包含任何信息。5.具有id和j的非叶节点正好具有j-1键，并且关键点代码按升序排序。节点包含以下信息(P0、k1、P1、k2、p2、kj-1，pj-1)其中ki是键码，符合ki核心测试点8:带权重图的最短路径算法及其应用Dijkstra算法查找单个源最短路径、算法思想：将S设置为最短距离的顶点集(称为红色点集)，V-S是最短距离的未定义顶点集(视为蓝色点集)。1.初始化：由于初始化时仅知道源点S的最短距离(SD(s)=0)，因此红色点集S=s，蓝色点集为空。2.通过重复以下操作，按路径长度增量的顺序为每个顶点创建最短路径，通过从当前蓝色点集中选择最短距离的蓝色点扩展一组红色点，算法可以按路径长度增量的顺序为每个顶点创建最短路径。如果仅剩下最短距离为的蓝色点，或者所有蓝色点均延伸到一组红色点，则将计算从s到所有顶点的最短路径。注如果从源点到蓝点的路径不存在，则可以假定蓝点的最短路径是无限的虚拟路径。从源点s到终点v的最短路径简称为v的最短路径。从s到v的最短路径长度简单地称为v的最短距离，以SD(v)记录。考研计算机核心测试点9:堆排序大根堆的定义：完全二叉树，其中一个不是叶子的节点比那个孩子大。也就是说，根节点最大。显然，大根堆中的任何一棵子树都是大根堆。堆排序的基本思路：记录区分为无序区和有序区前后两部分。用无序区域的数量创建一个大根堆，并将结果根(最大)和无序区域的最后数量，即根分组到有序区域的最前端；重复操作，直到有序区域扩展到整个记录区域。具体操作可以通过以下步骤完成：1.建一个大根堆2.交换根和无序区域的最后数目3.重建大根桩。交换只是简单地改变了根，左右树仍然各是根堆。4.根，比较左侧子树的根和右侧子树的根，根最大，不再需要调整，树已经是一大堆根；如果左侧子树的根最大，请交换根，然后递归调整左侧子树。如果右侧子树的根最大，请交换根，然后递归调整右侧子树的数目。5.递归地用树叶调整时，树就是大根堆。核心测试点10:与各种排序算法的特性比较一些关键排序算法：冒泡排序、排序选择、插入排序、快速排序、排序、shell排序、堆排序。冒泡排序算法思想：将要排序的元素视为垂直排列的“气泡”，较小的元素较轻，向上移动。冒泡排序算法需要对这个“冒泡”序列进行几次处理。也就是说，此序列是从上到下检查一次，并始终检查两个相邻元素的顺序是否正确。如果两个相邻元素的顺序错误(即“轻”元素在下面)，则交换它们的位置。选择排序算法思路：选择排序的基本思路是n-1次处理排序的记录顺序，I过程处理是lI.与最小的一个交换Li。这样，I pass处理后的前I个记录的位置已经正确。插入排序算法思想：i-1处理过程后的l 1.I-1已对齐。I通过过程将Li转换为l 1.仅在I-1的适当位置插入，因此l 1.I再次成为有序序列。快速排序算法思想：快速排序的基本思想基于分割策略。输入的子序列lp.r的情况是，如果大小足够小，则直接对齐，否则处理为步骤3。1.分解：输入的序列l p.r为两个非空序列l p.q和l q 1.除以r，再除以l p.q的任意元素值为l q 1.确保不大于r中的任意元素值。2.递归求解(Conquer):递归调用快速排序算法，每个算法为lp.q和l q 1.r对齐。3.合并(Merge):lp，因为两个分解子序列的对齐是在原地完成的.q和l q 1.r全部对齐后，lp.r无需执行计算。合并排序算法思想：分割。的(divide-conquer)。每个迭代过程包括三个阶段。1.分解(explode)-将要排序的n个元素的序列分解为两个子序列，每个子序列包含n/2个元素。2.治理，对每个子序列分别调用合并排序MergeSort以执行递归操作。3.合并两个连续的子序列以生成排序结果。shell排序算法思想：算法中要首先排序的组数按增量d分组，每组中记录的下标与d相差。先排序每个组中的所有图元，再按较小的增量排序，然后在每个组中排序。增量减小到1时，要排序