算法与数据结构常见面试题整理

1、排序算法

二分查找

最坏情况至多比较次数是⌊log2(n)⌋+1,其中⌊ ⌋表示向下取整

2、其他算法

（1）负载均衡算法

（2）加密算法

（3）页面置换算法

LRU算法

4、数据结构总结

线性表

（1）顺序表

（2）单链表

（3）双链表

（4）循环单链表

非循环单链表改为循环单链表：将尾结点的next指针域由原来的空改为指向头结点。因此，从表中任一点出发（单链表向后）都能找到链表中的其他结点

（5） 循环双向链表

非循环双链表改为循环双链表：将尾结点的next指针域由原来的空改为指向头结点，将头结点的prior指针域由原来的空改为指向尾结点。

二叉树

（1）基本概念

度（0，1，2）

节点的度：结点拥有的子树数目称为结点的度，叶子结点 就是度为0的结点
树的度：树内各结点的度的最大值
在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一个

遍历
前序： 根->左->右
中序： 左->中->右
后序： 左->右->根

（2）完全二叉树和满二叉树

满二叉树：除最后一层无任何子节点外，每一层的所有节点都有两个子节点。
完全二叉树：从满二叉树的定义发展而来，如果完全二叉树的深度为h，除第h层外，其他各层（1~h-1）的节点数都达到最大，第h层的所有节点集中在最左边。
性质：至上而下，从左至右编号，父节点编号为K，左节点为2K，右节点为2K+1

（3）哈夫曼树（最优二叉树）

概念 哈夫曼树是一种带权路径长度最短的二叉树。下面以一副图说明。

图a： WPL=52+72+22+132=

图b： WPL=53+23+72+131=48

可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

求解过程
一般可以按下面步骤构建：

1，将所有左，右子树都为空的作为根节点。

2，在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值。

3，从森林中删除这两棵树，同时把新树加入到森林中。

4，重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。

下面是构建哈夫曼树的图解过程：

哈夫曼编码
利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码。

就拿上图例子来说：

A，B，C，D对应的哈夫曼编码分别为：111，10，110，0

用图说明如下：

（4）B树和B+树

B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。

A.根节点至少有两个子节点
B.每个节点有M-1个key，并且以升序排列
C.位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
D.其它节点至少有M/2个子节点

下图是一个M=4 阶的B树,可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素:

B+树是对B树的一种变形树，它与B树的差异在于：

A.有k个子结点的结点必然有k个关键码；
B.非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
C.树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

如下图，是一个B+树:

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B+ 树的优点在于：
— 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
— B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

（5）大小根堆

概念大小堆其实就是二叉堆，内部就是一颗二叉树。左图为大根堆，右图为小根堆。

堆是利用完全二叉树的结构来维护一组数据，然后进行增删改查的操作，一般的增删改查操作进行一次的时间复杂度在O(1)~O(logn)之间。采用push实现大根堆，每次输入后，为了保证是大根堆，每插入一个元素，调整一次。

例题：

构建过程如下：

因此选D

（6）平衡二叉树（AVL树）

概念
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。
平衡因子：左孩子-右孩子高度=1 / 左孩子高度 = 右孩子高度 / 左孩子-右孩子=-1

（7）二叉查找树

概念
又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

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

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

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

4) 没有键值相等的节点。

（8）红黑树

概念
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。此外，红黑树还是2-3-4树的一种等同，它们的思想是一样的，只不过红黑树是2-3-4树用二叉树的形式表示的。

红黑树的性质：
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制的一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色（叶子是NIL节点）。

性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
　　下面是红黑树的图例：

队列

（1）循环队列

为了方便起见，约定：初始化建空队时，令
front=rear=0,
当队空时：front=rear
当队满时：front=rear 亦成立
因此只凭等式front=rear无法判断队空还是队满。 有两种方法处理上述问题：
（1）另设一个标志位以区别队列是空还是满。
（2）少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即：
队空时： front=rear
队满时： (rear+1)%maxsize=front

front指向队首元素，rear指向队尾元素的下一个元素。
队列元素个数：（rear-front+Max）%Max

队空：

队满：

队列未满（此时队列有三个元素）

（2）双端队列

4、图

（1）有无环路判断

概念
入度：以这个顶点为终点的有向边的数量。
出度：以这个顶点为起点的有向边的数量。

（2）强连通、强连通图、强连通分量

概念
在有向图G中：
强连通：如果两个顶点间至少存在一条互相可达路径，称两个顶点强连通。
强连通图：如果任意两个顶点都强连通，称G为强连通图。
强连通分量：非强连通图的极大强连通子图，称为强连通分量。
求解强连通图分量的算法有Kosaraju、Tarjan、Gabow。

（3）关键路径

概念
AOV网：是一个表示工程的有向图，顶点表示活动，弧用来表示活动之间的优先关系。
AOE网：是一个表示工程的带权有向图，其中顶点表示某个事件，弧用来表示活动，弧上的权值用来表示活动持续的时间内。
关键路径：找出AOE网中的关键活动，这些关键活动的路径表示关键路径。
具体实现：
A.首先初始化每个顶点的最早开始时间为0，然后对AOE网进行拓扑排序，在排序过程中获取每个顶点的最早开始时间；
B. 获取拓扑排序后，初始化每个顶点的最晚开始时间为汇点的最早开始时间，并从AOE网的汇点开始，从后往前，对每个顶点找到求其最晚开始时间；
C. 遍历图中的每条边（方法是遍历图中每个顶点的边表），求其最早开始时间和最晚开始时间，如果二者相等，则这是个关键活动，将其加入关键路径中。