1、常见的哈希函数构造方法

直接定址法，数字分析法，平方取中法，除留余数法。

2、什么是哈希冲突？以及如何解决

① 哈希冲突：指的是在哈希表中，多个关键字映射同一个地址的情况。

② 如何解决？

（1）开放定址法（再散列法）

线性探测再散列、二次探测再散列、随机探测再散列

（2）再哈希法：同时构造多个不同的哈希函数；这种方法不易产生聚集、但增加了计算时间；

（3）链地址法：把所有的同义词用单链表连接起来。

（4）建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

3、谈一谈图都有哪些存储方式？

① 邻接矩阵：是图的顺序存储结构，用两个数组分别存储数据元素（顶点）信息和数据元

素之间的关系（边/弧）的信息。图的邻接矩阵表示是唯一的，无向图的邻接矩阵是对称

的。

② 邻接表：是图的链式存储结构，由单链表的表头形成的顶点表和单链表其余结点所形成

的边表两部分组成。

③ 十字链表：有向图的另一种链式存储结构。

④ 邻接多重表：无向图的链式存储结构。

4、循环队列的顺序表中，为什么要空一个位置？

这是为了用来区分队空与队满的情况。如果不空一个位置，则判断队空和队满的条件是一样的。

5、普里姆（prim）算法和克鲁斯卡尔（kruskal）算法的联系区别

① 都是为了求最小生成树。

② prim其基本思想为：从联通网络 N={V,E}中某一顶点 u0 出发，选择 与他关联的最小权值的边，将其顶点加入到顶点集S 中，此后就从一个顶点在 S 集中， 另一个顶点不在 S 集中的所有顶点中选择出权值最小的边，把对应顶点加入到 S 集中， 直到所有的顶点都加入到 S 集中为止。

③ kruskal其基本思想为：设有一个有 N 个顶点的联通网络 N={V,E},初试时建立一个只有 N 个顶 点，没有边的非连通图T，T 中每个顶点都看作是一个联通分支，从边集 E 中选择出权 值最小的边且该边的两个端点不在一个联通分支中，则把该边加入到 T 中，否则就再重新选择一条权值最小的边，直到所有的顶点都在一个联通分支中为止。

6、谈一下折半查找

条件：有序数组

操作：

1) 查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；

2) 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

3) 如果在某一步骤数组为空，则代表找不到。

4) 这种搜索算法每一次比较都使搜索范围缩小一半。

时间复杂度：O(log(n))

7、谈一下KMP算法

在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。 而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是其低效率的根源。

因此，可以从分析模式本身的结构 着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串 i 指针无须回溯，并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关。

8、如何实现单链表就地逆置

所谓 “就地”是指算法的辅助空间为 O(1)

思路：用指针 p 扫描原单链表，先将头节点 L 的 next 域设置为 NULL 而变成一个空链表，然后将*p 节点采用头插法插入到 L 中

9、什么是二叉排序树？以及它的原理、算法。（二叉排序树的查找过程）

二叉排序树又称二叉查找树，它或者是一颗空树，或者满足一下性质的二叉树：

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

        ② 若右子树不空，则右子树上所有结点的值均大于根节点的值；

        ③ 左右子树也分别是二叉排序树。

原理步骤：

        若根结点的关键字值等于查找的关键字，成功。

        否则，若小于根结点的关键字值，递归查左子树。

        若大于根结点的关键字值，递归查右子树。

        若子树为空，查找不成功。

10、谈谈哈夫曼树

定义：给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若带权路径长度达到最小的二叉树.

构造方法：假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

        (1) 将 w1、w2、…，wn 看成是有 n 棵树的森林(每棵树仅有一个结点)；

        (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

        (3)从森林中删除选取的两棵树，并将新树加入森林；

        (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

特点：权值越大的结点，距离根节点越近；树中没有度为一的结点。

应用：哈夫曼编码，减少编码的长度。哈夫曼编码就是长度最短的前缀编码。

11、谈一下深度优先搜索遍历和广度优先搜索遍历的过程？

深度优先搜索遍历

    基本思想：首先访问出发点 V，并将其标记为已访问；然后选取与 V 邻接的未被访问的邻接顶点 W，访问W；再选取与 W 邻接的未被访问的顶点访问，以此类推。当一个顶点所有的邻接顶点都被访问过时，则依次退回最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些顶点中去一个顶点进行上述的过程，直至图中所有顶点都被访问过为止。

广度优先搜索遍历

    基本思想：首先访问起始顶点 V，然后选取与 V 邻接的全部顶点 w1，w2，….，wn 进行访问，再一次访问与 w1，w2，… ，wn 邻接的全部顶点（不包括已访问过的顶点），以此类推，直至所有顶点都被访问过为止。

12、谈一谈你对最小生成树的理解

一个有 n 个结点的连通图的最小生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边。如果在最小生成树中添加一条边，必定成一个环。

13、什么是堆？有什么作用？

堆是一种数据结构，可以把堆看成一个完全二叉树，并且这个完全二叉树满足：

        任何一个非叶节点的值都不大于（或不小于）其左右子树的结点的值。

若父亲大孩子小，则为大顶堆；若父亲小孩子大，则为小顶堆。

作用：应用于堆排序。

14、如何实现循环队列？有何好处？

如何实现：把数组弄成一个环，让 rear 和 front 指针沿着环走，这样就可以产生循环队列。

好处：循环队列是顺序队列的改进，在顺序队列中，在元素进队的时候，rear 要向后移动，元素出队的时候，front 也要向后移动，这样经过一系列的出队和入队操作之后，两个指针最后会达到数组的末端，此时虽然队中已经没有元素了，但是还是不能让元素入队，即出现了“假溢出”的现象。循环队列就能避免出现“假溢出”现象。

15、描述⼀下栈和队列的区别

都是受限的线性表，队列是先进先出，所以适用具有这个特性的算法来使用，比如图的广度优先搜索、二叉树的层次遍历等等；栈是后进先出，一般用于括号匹配、递归调用。

16、谈一下什么是关键路径？

在AOE网中，路径长度最长的路径叫做关键路径，关键路径上的所有活动都是关键活动。

AOE网：在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如时间），则称这个网络为AOE网。

17、谈一下什么是贪心算法？

① 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

② 贪心算法的一般步骤：

        1）将复杂问题分解为多个子问题；

        2）子问题的解是当前所有解中的最优解；

        3）将所有子问题的解合并为原问题的解。

③ 说明：

贪心问题和动态规划较为相似，其中一个较为关键的区别是贪心算法是不可取消的，自顶向下求出子问题的当前最优解。而动态规划是每步做出的选择都依赖于子问题的解

18、谈谈动态规划。

① 动态规划和之前的贪心算法有点类似，都是将一个规模大的问题分解为几个小的问题，通过解决小的问题来得到整体的解。

② 动态规划的核心问题是问题的状态的定义和状态转移方程的求解。

③ 动态规划的关键在于，将重复出现的子问题在第一次求解之后就将其保存起来，以后再遇到时不用重复求解。动态规划是按照自底向上的方式计算最优解。