数据结构期末考点
本文章notion版本链接（格式更好看一些）：https://www.notion.so/gryffinbitworkspace/5dbf3d58c5404a99bcaaba96cc42f58a
本文章PDF版本链接：https://gryffinbit.lanzous.com/i4duqknlove
数据结构期末考试考点，相关的附件：https://gryffinbit.lanzous.com/iTWTpknltyh
线性表
线性表及链表的添加、插入、删除（重点是指针的位置变化问题）
题
$Loc_{ai}=Loc_{a1}+(i-1)*l$
队列与栈
队列与栈的概念及基本操作（考选择题）
基本概念
栈后进先出
2比1后进，应该先出
数组和串
数组和串的基本概念（有两个左右的选择题）
广义表长度：表中所含元素的个数。深度：括号的层数
树
掌握树、二叉树、满二叉树、完全二叉树的相关概念，树转化为森林的方法。（这一张是考试重点，会有多种类型的考题）
重点掌握
二叉树的5个性质:
$叶子节点数： n_0 = n_2 + 1$
$第k层上，至多有2^{k-1}个结点$
$高度为h的二叉树，至多有2^h-1个结点$
结点i所在层次
n个结点的完全二叉树高度
树的几种遍历方法：
按某条搜索路径访问树中的每个结点，树的每个结点均被访问一次，而且只访问一次
先序遍历：根，左子树，右子树 NLR
中序遍历：左子树，根，右子树 LNR
后序遍历：左子树、右子树、根 LRN
层次遍历：从上至下，从左至右
哈夫曼树的构造及编码规则
平衡二叉树的构建
相关概念
树
二叉树
满二叉树
完全二叉树
左边是完全二叉树，右边是满二叉树。
只有最后一层，没有满。
树转化为森林的方法
题
$n=n_0 +n_1+n_2$
$n_0=n_2+1$
最后一个分支结点序号 = 结点/2 向下取正
叶子结点个数 = 总结点数 - 最后一个分支结点序号
$n_1$只有两种可能 0 或1
$结点固定，h范围： log_2最大结点数（向下取正） + 1 ～ 最大结点数$
$深度为h的满m叉树，结点个数 m^h-1, 第k层的结点数为m^{k-1}$
分支数为B，结点数为n
$n=B+1$
$B=度数*数量$
$哈夫曼树只有n_0和n_2结点$
$完全二叉树 n = n_0+n_1+n_2 且 n_1= 0\ or \ 1$
图
有向图，无向图，连通图的基本概率，图的邻接矩阵表示方法，图的遍历方法（深度遍历和广度遍历），最短路劲算法和关键路劲的算法；
最小生成树算法：Prim算法及Kruskal算法的概念；
最短路径算法：Dijkstra（迪杰斯特拉）算法（要求理解该算法的程序代码）
关键路径算法的求解
图的基本概念
- 一个图中，所有顶点度数之和 = 边数 * 2
- 有向图中，所有顶点出度之和 = 入度之和
- n个顶点的有向图，最多n(n-1) 条边
- n个顶点的连通图，用邻接矩阵表示，最少要有2(n-1)个非零元素
题
行为出度，列为入度。各顶点度是行列非零元素之和。
关键路径：从源点到汇点带权路径最长的
线性表
重点掌握：
线性表的顺序查找、折半查找和分块查找的概念
二叉排序树的查找、创建、插入、删除方法；
平衡二叉树的调整的4种方法；
堆排序（掌握如何建堆的过程）；
堆排列
小根堆，子树比根大
大根堆，子树比根小
顺序查找
对无序线性表进行顺序查找，查找失败时要遍历整个线性表
有序查找进行顺序查找，失败时不一定要遍历整个线性表
失败结点有n+1个
折半查找
仅适用于有序顺序表
计算平均查找长度：
ASL成功：第一层有一个结点，第二层两个结点，第三层三个
ASL失败：没有给出具体失败例子，以失败结点为单位，有12个失败结点。4层有4个失败结点，（4-1）*4
5层有8个失败结点，（5-1）*8
分块查找
命名：最大标号。
查找的时候，和标号比较
块内元素无序，块间有序
注意是，均匀分配b块
平衡二叉树的调整（4种方法）
LL平衡旋转（右单旋转）
H代表层数
RR平衡旋转
LR平衡旋转
RL平衡旋转
概念题
题
中间的为根，然后分为左右两部分，再取中间的为根，以此类推，且确定了根后，处在前面的是后面的根，比如3，4的位置。或者前面是左子树。这种顺序
关键字结点排序，比较大小，小的左子树，大的右子树
排序
基本概念
题
快速排序，左标记的值大于基准点时，且右标记移动到比基准值小时，左右两边交换。
左右两个标记重合时，那个值与基准点进行交换。这样就分为了，标记值左边是小于基准值的，右边是大于基准值的
小根堆
按层次排序把这个序列排成二叉树
大根堆
先无序排成二叉树，然后从底层开始交换顺序。根比孩子都大
算法
掌握起泡排序（要求理解该算法程序代码），直接插入排序（懂得原理）、希尔排序（懂得原理）、快速排序（懂得原理）；
