平衡二叉树建立步骤及失去平衡情况解析

其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。插入26后出现了不平衡现象，此时失去平衡的最小子树根结点为7。至此，平衡二叉树建立完成。

理论教育 2023-11-03

2019版数据结构高分笔记：插入过程详解

插入过程：取表R中的第一个元素A[m]存入辅助变量temp中，让temp逐个与A[m-1]，…，A[0]进行比较，当temp＜A[j]时，将A[j]后移一位，否则将temp存入A[j+1]中。最后，p与q任一指针为NULL时算法结束。

理论教育 2023-11-03

单链表操作-2019数据结构高分笔记

知识点总结：例2-3中涵盖了两个知识点：一个是尾插法建立单链表；另一个是单链表的归并操作。上面的程序就是单链表归并操作的标准写法，希望同学们熟练掌握。下面提取出尾插法建立单链表的算法，供参考。第一个问题引出了本章要讲的单链表中最后一个重要操作——链表中结点的查找。下面要介绍的是双链表、循环链表以及循环双链表的操作。

理论教育 2023-11-03

数据结构高分笔记：置换-选择排序

采用置换-选择排序算法构造初始归并段的过程：根据缓冲区大小，由外存读入记录，当记录充满缓冲区后，选择最小的写回外存，其空缺位置由下一个读入记录来取代，输出的记录成为当前初始归并段的一部分。用同样的方法继续生成下一个初始归并段，直到全部记录都处理完毕为止，这就是置换-选择排序法。由例8-1可知，通过置换-选择排序算法得到的m个初始归并段长度可能是不同的。

理论教育 2023-11-03

数据结构高分笔记：二叉树主要性质解析

结点最多的情况即为满二叉树的情况，此时二叉树每层上的结点数构成了一个首项为1、公比为2的等比数列。换句话说，满二叉树中前k层的结点个数为2k-1。图6-5 有5个结点的完全二叉树性质5 函数Catalan（）：给定n个结点，能构成h种不同的二叉树，性质6 具有n（n≥1）个结点的完全二叉树的高度（或深度）为[log2n]+1。证明：由性质3可知：2h-1-1＜n≤2h-1，其中h为完全二叉树的高度。

理论教育 2023-11-03

2019版数据结构高分笔记：拓扑排序核心算法

以邻接表为存储结构，怎样实现拓扑排序的算法呢？如果相等则返回1，拓扑排序成功；否则返回0，拓扑排序失败。由此可以写出以下算法代码：注意：拓扑排序序列可能不唯一。若AOV网中考查各顶点的出度并以下列步骤进行排序，则将这种排序称为逆拓扑排序，输出的结果称为逆拓扑有序序列。

理论教育 2023-11-03

2019高分数据结构笔记习题+真题精选

A.单链表 B.不带头结点的单循环链表C.双链表 D.不带头结点且有尾指针的单循环链表6.静态链表中指针指示的是（ ）。A.必须是连续的 B.一定是不连续的C.部分地址必须是连续的 D.连续与否均可以19.线性表的静态链表存储结构与顺序存储结构相比，其优点是（ ）。

理论教育 2023-11-03

数据结构高分笔记:B-树操作详解

图9-10 在B-树中查找关键字42的路线2.B-树关键字的插入和删除下面通过例子来讲解B-树的插入和删除操作的一般方法。对于该B-树，给出删除关键字8、16、15、4的过程。图9-16 插入关键字20后的结果7）按照上述步骤将关键字3、12、14、18、19插入后的B-树如图9-17所示，在插入过程中也需要拆分操作。因为这样做会使15所在的结点中关键字的个数小于2，不满足B-树的规定。

理论教育 2023-11-03

2019版数据结构高分笔记-基数排序步骤详解

桶0：930桶1：没关键字，不收集桶2：没关键字，不收集桶3：063，083桶8：278，008桶9：109，589，269将每桶收集的关键字依次排开，所以第一趟收集后的结果为：930 063 083 184 505 278 008 109 589 269注意观察，最低位有序了，这就是第一趟基数排序后的结果。基数排序每一趟都要进行“分配”和“收集”。

理论教育 2023-11-03

k路归并中，使用败者树能减少比较次数

在k路归并中，若不使用败者树，则每次对读入的k个值需进行k-1次比较才能得到最值。图8-20 17与5比较图8-21 29与15比较3）步骤1）中胜者5与第三个叶子结点10比较，10为败者，5为胜者，因此10的下标2替换到5的下标1的位置，5的下标1向上一级，成为下标2的父结点，如图8-22所示。调整过程：1）44和17比较，44败，17胜，因此44所在序号1作为两者父结点，17所在序号0作为1候选父结点，如图8-25方框内所示。

理论教育 2023-11-03

迪杰斯特拉算法详解2019版数据结构高分笔记

通常采用迪杰斯特拉算法求图中某一顶点到其余各顶点的最短路径。迪杰斯特拉算法执行过程如下：1）从当前dist[]数组中选出最小值，假设为dist[vu]，将set[vu]设置为1，表示当前新并入的顶点为vu。

理论教育 2023-11-03

高效弗洛伊德算法，2019数据结构笔记

迪杰斯特拉算法是求图中某一顶点到其余各顶点的最短路径，如果求图中任意一对顶点间的最短路径，则通常用弗洛伊德算法。图7-24所示为一个有向图，各边的权值如图所示，用弗洛伊德算法求解其最短路径的过程如下。反映其执行过程的伪代码如下：从上述示例中可以总结出用弗洛伊德算法求解最短路径的一般过程，具体如下：1）设置两个矩阵A和Path，初始时将图的邻接矩阵赋值给A，将矩阵Path中元素全部设置为-1。

理论教育 2023-11-03

2019版数据结构高分笔记：考研C与C++语言基础

本节的标题是C语言及C++语言，而不是单一的一种语言，是因为本书有些程序的书写包含了这两种语法。对于考试答题来说，C++不因为它是C语言的升级版就能取代C。C和C++是各有所长的，我们从两者中挑选出来对考研答卷有利的部分，组合起来应用。下面具体介绍针对考研数据结构的C和C++语言基础。而对于结构体a，a.a、a.b、a.c分别对应于结构体变量a中第一、第二、第三个元素的值，两者十分相似。

理论教育 2023-11-03

数据结构高分笔记：树转换为二叉树

如图6-19所示，最左边是一棵树，最右边是这棵树转化为二叉树后存储在二叉链表中的情形。这就是本节的主要内容，将树转化为二叉树。以图6-19所示的树为例，将其转化为二叉树的过程如下：1）将同一结点的各孩子结点用线串起来，如图6-20所示。1）图6-23a所示是一棵二叉树，先把它从左上到右下分为若干层。

理论教育 2023-11-03

数据结构高分笔记：树和森林遍历技巧

图6-27 树的遍历7）访问A的第三棵子树，访问子树时先访问根结点D。如图6-25所示的森林，对其进行后序遍历的结果为：BCDA，FE，HJIG，其实就是对森林中的每一棵树分别进行后序遍历的结果。对其进行中序遍历得到：BCDAFEHJIG，与森林的后序遍历序列相同。森林转换为二叉树中，森林的先序遍历对应二叉树的先序遍历，森林的后序遍历对应二叉树的中序遍历。

理论教育 2023-11-03

数据结构高分笔记-顺序表操作

如果p的输入不正确，则返回0，代表插入失败；如果p的输入正确，则将顺序表第p个元素及以后元素右移一个位置，腾出一个空位置插入新元素，顺序表长度增加1，插入操作成功，返回1。插入操作代码如下： 删除顺序表L中下标为p的元素，成功返回1，否则返回0，并将被删除元素的值赋给e。由此可以写出以下代码：说明：通过以上两个例题，可以总结出顺序表的查找、插入和删除三种操作。

理论教育 2023-11-03