【中级软件设计师】—数据结构与算法基础考点总结篇（八）

课程大纲

1.1 数组

按行存储：a+(2*5+3)*2 其中a表示的就是a[0][0]

1.2 稀疏矩阵

本题采用代入法，首先代入A0,0，A0,0存入的位置是M【1】，把i=0,j=0分别代入A、B、C和D选项中，

代入之后我们排除了B和C，在代入A1,1，存储在M【3】中，在A和D选项中我们得知A符合题意，选A

1.2 数据结构的定义

1.3 线性表的定义

1.4线性表—顺序存储与链式存储对比

1.5 线性表—队列与栈

1.6 广义表

1.7 树与二叉树

1.8 二叉树的遍历

前序遍历根左右(前就是根在前，左右在后面)。中序遍历左根右(中就是根在中间，左右在旁)。后序遍历左右根(因为有后，就是根在后面，那左右就在前面了。)

前：12457836 根：42785136 后：48752631 层：12345678

1.9 树与二叉树—反向构造二叉树

2.0 树转二叉树

2.1 查找二叉树

2.2 树与二叉树—哈夫曼树（最优二叉树）

构成哈夫曼树的步骤：

1)从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树

2)取出根节点权值最小的两颗二叉树

3)组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4)再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到哈夫曼树

2.3 线索二叉树

无左孩子，前趋，无右孩子，后继

2.4 树与二叉树—平衡二叉树

2.5 图的基本概念

图的存储—邻接矩阵

图的存储—邻接表

2.6 图的遍历

2.7 图— 拓扑排序

拓扑排序：找入度为0的结点，由该入度为0的结点也删除掉，重复以上操作。

上图的拓扑排序为：

2.8 图的最小生成树—普里姆算法

🎈生成树

图中ABCDEF一共有六个节点，连接起来，最少需要n-1条边。如果选的五条边是最短的五条边，并且没有形成环路。因此，最少需要1300长的线路，才能保持城市的通信连通。

普里姆算法

克鲁斯卡尔算法

2.9 算法基础—算法的特性

算法基础—时间复杂度

3.0 查找—顺序查找

3.1 二分查找

3.2 散列表

3.3 排序

常见的排序有：

排序算法的稳定性

3.4 直接插入排序

3.5 希尔排序

3.6 直接选择排序

3.7 堆排序

• 大顶堆：每个结点的值都大于或等于其左右孩子结点的值。
• 小顶堆：每个结点的值都小于或等于其左右孩子结点的值。
  
  

3.8 冒泡排序

3.9 快速排序

4.0 归并排序

4.1 基数排序

4.2 排序算法总结