软考 · 数据结构

线性结构

1、链表和线性表的优缺点对比。

2、链表的插删。

3、栈的进出顺序，后缀表达式的栈计算。

4、循环队列的空和满 判。

5、串，kmp算法（求next数组）。

找k的技巧是找到左右对称的分界点，左边的串长度+1作为next数组的值，如无则为1

6、数组与矩阵的下标计算。可以通过特殊值代入法进行计算。稀疏矩阵存储；十字链表和三元组

7、广义表。左括号的个数就是广义表的重数。除了第一元素外，其他元素都是一个表。

树与图

1、

2、满二叉树：都具有左右孩子。完全二叉树：在满二叉树的情况下，缺少顺序末尾的结点。

二叉树第i层最多个 $2^{i-1}$ 结点。深度为k的二叉树最大有 $2^k-1$ 结点。度为2的结点个数n_2，叶子结点的个数n_0，则 $n_0=n_2+1$ 。总节点数等于分支总数+1。

3、线索二叉树

4、最优二叉树（哈夫曼树）

哈夫曼树构建。左小右大。哈夫曼编码是左边为0，右边为1。

2、图使用邻接矩阵和邻接表存储。深度和广度遍历，使用邻接矩阵的辅助度为O(n^2) 邻接表是O(n+e)。

3、最小生成树。普利姆算法 （O(n^2)）适合稠密图（边多的）和 克鲁斯卡尔算法 (O(elog2e)) 适合稀疏图（边少的）

4、拓扑排序：选择入度为0的任意一节点，删除其相关的边（弧）形成新图，重复上述直至仅剩一个结点。

5、AOE网。关键路径：最长的路径。

6、最短路径。迪杰斯特拉（贪心）和佛洛依德（动态规划）

查找和排序

1、顺序查找。

2、折半查找。有序的。(O(log2n))

3、分块查找。需要分块，建立索引表（存放开始下标，和局部最大值），块内部无需有序。效率在1，2之间

4、哈希。主要是记得解决冲突的方式。注意平均查找长度的计算。

1、插入排序

2、希尔排序，不稳定

3、冒泡排序

4、快速排序。O(nlog2n)（分治）

5、简单选择排序。不稳定

6、堆排序。O(nlog2n) O(n)

7、归并排序（分治）O(nlog2n) O(n)

8、基数排序 稳定的