软考-软件设计师(3)-数据结构与算法:树、图、队列、查找算法、排序算法、霍夫曼编码/树、环路复杂性、算法/时间复杂度/空间复杂度等高频考点

场景

软考-软件设计师-数据结构与算法模块高频考点整理。

以下为高频考点、知识点汇总，不代表该模块所有知识点覆盖，请以官方教程提纲为准。

注：

博客：
霸道流氓气质-CSDN博客

实现

知识点

树：节点的度、树的度、深度、高度、满二叉树、完全二叉树、平衡二叉树、B树、二叉排序树

节点的度：节点含有子树的个数

树的度：树中最大节点的度就是树的度

树的深度：从根节点开始、自顶向下逐层累加

树的高度：从叶节点开始、自底向上逐层累加

一棵有n个结点的树的所有节点的度数之和为n-1

1、满二叉树：

一个二叉树，如果每一层的节点数都达到了最大值（均为2），则这个二叉树就可以被称作为 "满二叉树"

已知层数求总和:M=₂ⁿ−1,n为层数，M为总数

已知总数求层数:n=log₂(M+1)

2、完全二叉树：

若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，

则这样的二叉树称为完全二叉树

前 h−1层是满的，最后一层不满，但是最后一层从左到右是连续的

有n个节点的完全二叉树的深度/高度为[log₂ⁿ]+1

技巧：此类题可以画出完全二叉树并代入公式验证

3、平衡二叉树：

平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树:

它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

4、B树：

B树又叫B-树

是一种多路平衡搜索树，它的阶数m指它最多可以有多少个子结点，当m为2时，B树就成了二叉搜索树

一棵m阶的B树定义：

每个结点最多可以有m-1个关键字，可以是键值对

根结点最少可以只有1个关键字

非根结点最少有m/2个关键字

每个结点的关键字按照从小到大排序，它左子树结点的关键字都小于它，右子树结点的关键字都大于它

所有叶子结点位于同一层，也就是根结点到所有叶子的路径长度相同

每个结点都存有索引key和数据value

5、二叉排序树/二叉查找树/二叉搜索树

二叉排序树或者是一棵空树，或者是具有下列特点的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

举例：用关键字序列10、20、30、40、50构造的二叉排序树为

6、经典题目：已知结点的度数和个数求叶子结点个数

一棵度为4的数T中，若有5个度为4的结点，7个度为3的结点，3个度为2的结点，9个度为1的结点，则树T的叶子结点个数

根据树中结点总数为n,n=分支数+1，而分支数等于树中各个节点的度之和，所以根据5*4+7*3+3*2+9*1+1=叶子数+5+7+3+9;因此叶子数为33个

图：邻接矩阵、邻接表、有向图、无向图

1、邻接矩阵

借助矩阵（二维数组）表示元素（图的任意两个顶点）之间的关系

在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数是：邻接大小是n²，非零元素的个数为2e,所以零元素的个数是n²-2e

在含有n个顶点、e条边的简单有向图采用邻接矩阵存储结构，则该矩阵的元素数目为n²，其中非零元素数据为e

对于有向图，其邻接矩阵中非零元素的数目表示有向弧的个数

无向图的邻接矩阵是对称矩阵

无向图中一个顶点的度是指图中与该顶点相邻的顶点数

有向图和无向图及其邻接矩阵图示：

有向图的邻接矩阵表示法

2、邻接表

3、根据邻接矩阵求各顶点的出度

邻接矩阵A为非对称矩阵，说明图是有向图，各顶点的出度为矩阵行中1的个数，即2,2,1,1

队列：循环队列、优先队列

1、循环队列

对于循环队列，求队头元素的指针的计算公式为(rear-