一种较线性表和树更为复杂的数据结构。图结构中结点之间的关系是任意的，图中任何两个节点都可能有关系。图通常用来描述某些事物之间的某种特定关系 ，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
有向图的基本算法： 拓扑排序（数据结构之拓扑排序）、联通分量、最短路径（Dijkstra算法和Floyd算法）。
无向图的基本算法：最小生成树（Prime算法。Kruska算法）、DFS、BFS、MFS、最短路径、最大连通图、强联通分量。
连通图、强连通图：有向图任意两个顶点都有路径相通，无向图任意两点之间都有来回路径。
极大连通子图、极小连通子图、极大强连通子图、极小强连通子图：极大连通子图即连通分量，极小连通子图即边最少的连通子图，极大强连通子图即强连通分量、极小强连通子图在保持任意两结点来回互通的情况下弧最少的连通子图。
（广度BFS和深度DFS）broad和deep
后者类似：不撞南墙不回头，类似于二叉树的先序遍历。
相同点： （唯一便是唯一）
同图用邻接矩阵表示唯一，深度广度遍历序列就唯一，深度广度生成树也唯一。
同图用邻接表则表示不唯一，深度广度遍历序列不唯一，深度广度生成树也不唯一。
（BFS）：只适合不带权的路径；（O（|V|2））或（O（|V|+|E|））
（Dijkstra）迪杰斯特拉可带权，但是单点出发（且不能算负值）
（Floyd）佛洛依德算法： 各顶点最短路径（O（|V|3））
拓扑结构：将入度为0的顶点取出,可用于检测AOV网是否有环。
AOV网
一种以顶点表示活动，以边表示活动的先后次序且没有回路的有向图
反映出整个工程中各个活动之间的先后关系的有向图。
关键活动：关键路径上的活动为关键路径，关键活动的最早开始时间等于最晚开始时间。由于AOE网中的某些活动是可以同时发生的，所以完成整个工程的时间应该是从始点到终点的最大路径长度，关键路径长度即为工程的最短完成时间。
AOV和AOE的区别
相同点: 都是无环图
不同点：AOV活动在顶点，边无权值，代表活动之前的先后关系， AOE活动在边，边有权值，代表活动持续的时间
- 经过一趟排序，能保证一个关键字到达最终位置
冒泡排序、快速排序（交换类）
简单选择、堆排序（选择类）
- 关键字比较次数和原始序列无关
简单选择、折半排序
- 排序趟数和原始序列无关
冒泡排序、快速排序（交换类）
- 将顺序存储更换为链式存储，时间效率低
希尔排序、堆排序
- 排序最优和最差相同的排序算法
简单选择、归并排序、堆排序
- 排序算法中那些最坏和平均的时间复杂度是一样的
直接插入、折半插入、冒泡排序、简单选择、堆排序、归并排序
堆：是一种特殊的完全二叉树，叶子结点的值大于或者小于根结点的值
（PS：完全二叉树是指第n-1层，每一层的结点数是2^(n-1),最后一层的结点可以不放满，但是必须是从左至右放的）
什么是大根堆？什么是小根堆？
大根堆：父结点的值大于等于其子结点的值；小根堆：父结点的值小于等于其子节点的值。
快排的时间复杂度
时间复杂度最快平均是O（nlogn）,最慢的时候是O(n2);辅助空间也是O(logn)；
优化：
1.当整个序列有序时退出算法；
2.当序列长度很小时（根据经验是大概小于 8），应该使用常数更小的算法，比如插入排序等；
3.随机选取分割位置；
4.当分割位置不理想时，考虑是否重新选取分割位置；
5.分割成两个序列时，只对其中一个递归进去，另一个序列仍可以在这一函数内继续划分，可以显著减小栈的大小（尾递归）：
6.将单向扫描改成双向扫描，可以减少划分过程中的交换次数
优化1：当待排序序列的长度分割到一定大小后，使用插入排序
原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排
优化2：在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割
优化3：优化递归操作
快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化
优点：如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。
顺序查找：可以对有序表、也可以无序表。适用于顺序和链式存储。
折半查找：对有序表的查找。用到折半查找判定树。适用于顺序存储。
分块查找：顺序查找和折半查找的结合，块内无序、块间有序。
关键字：数据元素中某个数据项的值，用它可以标识一个数据元素。
散列表：根据关键字直接进行访问的数据结构，建立了关键字和物理存储的直接映射。（其实是空间换时间的方法）
冲突：不同关键之映射到同一地址的情况。
当冲突了，需要解决冲突，讲两种方法（拉链法）和（开放定址法）:主要是线性和平方。
冲突解决方法
散列查找效率影响因素
填装因子，散列函数，处理冲突的方法。
平均查找长度ASL依赖于填装因子。填装因子是所存储的数据元素和整个申请存储空间的比值，即表的装满程度。
答：贪心算法是指从上到下，每次都求解局部最优解的算法，特点是每次求解最优解，但是最终的结果不一定是最优，经典例子是背包问题。
动态规划是将一个大问题划分成若干个子问题，问题之间存在重叠，从上到下，求解整体最优解，每一次的求解会对下一次的问题造成影响，最终的最优解不一定包含每次的最优解，但是一定有部分最优解。经典例子是求最长子串。
分治算法是将一个大问题划分成若干个和大问题相似的子问题，再对子问题进行递归求解，最终合并得到最后的结果。特点是大问题的划分与子问题相似，并且每个问题之间是相互独立的。经典例子是二路归并排序、快速排序
递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。
递归算法
优点：代码简洁、清晰，并且容易验证正确性。
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。
但是，对于某些问题，如果不使用递归，那将是极端难看的代码。在编译器优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。
循环算法
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。
在实现函数调用的时候，系统底层就是用栈来保护现场的；具体来说，每次调用函数时，会把当前函数的局部变量和返回地址都压栈保存起来，当系统调用结束返回时，再把局部变量从栈中弹出来；
递归的核心就是重复的函数调用，如果要变成非递归，就需要自己实现栈的数据结构来保存一些状态变量，这其实就是模拟函数的调用。
实现队列的入队（enqueue）和出队（dequeue）操作。
图（2）：将stack1中的元素pop进stack2中，此时pop一下stack2中的元素，就可以达到和队列删除数据一样的顺序了；
图（3）：可能有些人很疑惑，就像图3，当stack2只pop了一个元素a时，satck1中可能还会插入元素e,这时如果将stack1中的元素e插入stack2中，在a之后出栈的元素就是e了，显然，这样想是不对的，我们必须规定当stack2中的元素pop完之后，也就是satck2为空时，再插入stack1中的元素。
图（2）：将元素“abc”从q1中头删，然后再q2中尾插进来之后，头删q1中的元素“d”，就相当于实现了栈顶元素的出栈；
图（3）：同理，将元素“ab”从q2中头删，然后尾插到q1中，然后再头删q2中的元素“c”;
图（4）：同理，删除元素“b”;
图（5）：当栈又插入一个元素“e”时，此时元素“a”不能从队列中删除，而是将元素“a”插入q2中，再删除q1中的元素“e”,最后再删除元素“a”。