面试常问的数据结构

1. 线性数据结构：

**栈：**是一种线性表，只能在表尾插入或删除，具有先进后出特性。
**队列：**也是一种线性表，只能在一端进行插入，另一端进行删除操作，具有先进先出特性。
**链表：**也是一种线性表，但不会按线性的顺序存储数据，使用不连续的内存空间存储数据。插入和删除操作复杂度为O(1)，查找or访问某位置节点时复杂度为O(n).
**数组：**由相同类型的元素组成，使用连续的内存存储。

2. 跳表：

是一种查找数据结构，支持快查、插入和删除，时间复杂度均为O(logn).

3. 图：

由顶点的有穷非空集合和顶点之间的边组成的集合。可分为无向图和有向图，无权图和带权图。

• 连通图：无向图中，任意两个顶点ViVi与VjVj都有路径相通，则此无向图为连通图。
• 强连通图：有向图中，任意两个顶点ViVi与VjVj都有路径相通，则此有向图为强连通图。
  图的深度优先搜索DFS：
  将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点V0为起始点出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。
  图的广度优先搜索：
  从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。

4. 邻接矩阵：

用一个二维数组存放图顶点间关系的数据，此二维数组称为邻接矩阵。对于无向图，邻接矩阵是对称矩阵。

5. 邻接表：

邻接表是通过链表表示图连接关系的一种方式，对于表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单链表中。

6. 哈希表：

即散列表。是根据关键码值进行访问的数据结构，通过key获取指定的value，速度很快。

哈希冲突：由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。（两个不同的数据计算后的结果一样）

解决Hash冲突的方法：

• 开放定址法：发生哈希冲突时，若哈希表未被装满，那么可以把这个值存放到冲突位置中的下一个空位置中去。
• 链地址法：对相同的哈希地址，设置一个单链表，单链表内放的都是哈希冲突元素。

7. 树：

是一种由有限节点组成的层次关系的集合。具有特点如下：

1. 每个节点有0个或多个子节点；
2. 只有一个节点没有父节点，则该节点称为根节点；
3. 除根节点外，每个节点有且只有一个父节点。

常见树的类型如下：

二叉树：是有n个有限元素的集合，该集合可以为空，也可以由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

满二叉树：若二叉树每一个层的结点数都达到最大值即为满二叉树。
完全二叉树：对于一个树高为h的二叉树，其第0层至第h-1层的结点都满。若最下面一层结点不满，则所有的结点在左边的连续排列，空位都在右边，即为完全二叉树。

平衡树（Treap):是二叉搜索树和堆合并构成的新数据结构。每个节点的数据域包含key和weight2个值。

• key:满足左子树<根节点<右子树
• weight：随机产生，根节点的weight值小于等于（或大于等于）左右儿子节点。如下图:
  

二叉搜索树（又称二叉查找树、二叉排序树。英文名：BST。左小右大):或是空树，或是具有如下性质的二叉树：

• 左子树不为空，则左子树上所有结点的值小于根结点的值；
• 右子树不为空，则右子树上所有结点的值大于根结点的值；
• 左右子树也分别是二叉搜索树；
• 没有键值相等的结点。

二叉搜索树如图：

平衡二叉树（AVL)：是一种改进的搜索二叉树，其引入平衡因子（左右子支高度差的绝对值），通过旋转使其尽量保持平衡。任何一个节点的左右子支高度差的绝对值不超过1.

红黑树：是自平衡的二叉查找树，是一种含有红黑结点并能自平衡的二叉查找树。红黑树通过重新着色和左右旋转，高效完成插入和删除后的自平衡调整。满足如下性质：

• 每个节点要么是黑色，要么是红色；
• 根节点是黑色；
• 每个叶子节点(Nil)是黑色；
• 每个红色结点的两个子结点一定都是黑色；
• 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
  时间复杂度是O(logn)简单的红黑树如下：
  

B树（B-树、平衡多路查找树）：是一种自平衡数据结构，有维护数据并允许以对数时间进行搜索、顺序访问、插入、删除。定义如下：
B树是一种平衡的多分树，B树中所有结点的子树个数的最大值为B树的阶。一般m阶的B树满足如下条件：

• 树中每个结点至多有m-1个关键字（若只有1个关键字辩称了二叉排序树），最多只有m个子结点，即m棵子树；（叶子结点也是B树的结点）
• 除根节点外，所有非叶结点至少含有[m/2]-1个关键字，即[m/2]棵子树。
• 所有叶结点都在同一层上（各子树没有高度差，绝对平衡）。叶结点不带信息，实际不存在，可看成查找失败的结点。
  B树如下图：
  

B+树：能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。是B树的一种变形形式，m阶B+树满足以下条件：

• 每个结点最多有m个孩子；
• 除根结点和叶结点外，每个结点至少有（M+1）/2个孩子；
• 若根结点不为空，根结点至少有2个孩子；
• 所有叶子结点增加一个链指针，所有关键字都在叶子结点出现。
• 除了叶结点，结点的孩子数目=关键字数目。B+树中非叶子结点存储的不是关键字数据的地址，而是指向叶子结点中关键字的索引。（所以任何关键字的查找必须走一条从根结点到叶子结点的路）
  优点：
• B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
• B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
• B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
• B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

字典树（Trie树、前缀树）：是一种空间换时间的数据结构，常用于统计、排序、保存大量字符串。利用字符串的公共前缀减少查询时间，最大限度减少无谓的字符串比较，查询率比哈希树高。
重要性质：
除了根结点每个结点都只包含一个字符。
从根结点到某一个结点，路过字符串起来就是对应的字符串。
每个结点的子结点字符不同，即找到对应单词、字符是唯一的。

8. 堆：

是一种完全二叉树形式，其中任意一个节点的值都大于等于（或小于等于）所有子节点的值。分为最大堆和最小堆。

9. set

Set是一种集合。集合中的对象不按特定的方式排序，且没有重复对象。

10. 二叉树的前中后序遍历算法

前序遍历：若二叉树为空，则执行空逻辑，否则：

1. 访问根节点；
2. 递归前序遍历左子树；
3. 递归前序遍历右子树。

中序遍历：若二叉树为空，则执行空逻辑，否则：

1. 递归中序遍历访问左子树；
2. 访问根节点；
3. 递归中序遍历访问右子树。

后续遍历：若二叉树为空，则执行空逻辑，否则：

1. 递归后序遍历左子树；
2. 递归后序遍历右子树；
3. 访问根节点。

11. 最小生成树和其对应的算法

• 对于有n个结点的原图，生成原图的极小连通子图，其包含原图中的所有n个结点，并保持图连通的最少边。
• 克鲁斯卡尔（Kruskal）算法： 先构造一个只含n个顶点的子图SG，从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。如下图：
  
• 普里姆（Prim)算法：
  取图中任意一个顶点V作为生成树的根，之后往生成树上添加新的顶点W。在添加的顶点W和已经在生成树上的顶点V之间必定存在一条边，且该边的权值在所有连通顶点V和W之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。如下图：
  

12. 最短路径算法：

Dijkstral算法为求解一个点到其余各点最小路径的方法，其算法为： 如求解顶点V到其余各个点的最短距离。n次循环至n个顶点全部遍历：

1. 从权值数组中找到权值最小的，标记该边端点k
2. 打印该路径及权值
3. 若存在经过顶点k到顶点i的边比v->i的权值小
4. 更新权值数组及对应路径

13. 稳定排序和非稳定排序的区别：

稳定排序：排序前后两个相等的数相对位置不变，则算法稳定。
非稳定排序：排序前后两个相等的数相对位置发生了变化，则算法不稳定。

14. 常见的稳定排序算法：

• 插入排序：每一趟将一个待排序记录按其关键字的大小插入到已排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。时间复杂度O(n²),空间复杂度O(1)。
• 冒泡排序：比较相邻的元素，若第一个比第二个大进行交换，对每一对相邻元素做同样的工作。时间复杂度O(n²),空间复杂度O(1)。
• 归并排序：将待排序序列分为两部分，并分别对这两部分进行递归排序，最后合并。时间复杂度都为 O(nlogn)，空间复杂度为 O(n)。

15. 常见的不稳定排序算法：

• 希尔排序：把记录按下标的一定增量分组，对每组进行直接插入排序，每次排序后减小增量，当增量减至1时排序完毕。时间复杂度 O(nlogn)，空间复杂度 O(1)。
• 直接选择排序：每次在未排序序列中找到最小元素，和未排序序列的第一个元素交换位置，再在剩余未排序序列中重复操作直到所有元素排序完毕。时间复杂度 O(n²)，空间复杂度 O(1)。
• 堆排序：将待排序数组看作一个树状数组，建立一个二叉树堆。通过对这种数据结构进行每个元素的插入，完成排序工作。时间复杂度 O(nlogn)，空间复杂度 O(1)。
• 快速排序：随机选择一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，一部分全部小于等于基准元素，一部分大于等于基准元素，再按此方法递归对这两部分数据进行快速排序。O(nlogn)，空间复杂度 O(logn)。

参考：后端技术小牛说