- 最短路径，弗洛伊德和迪杰斯特拉有什么不同，用于什么情况
- 最小生成树，时间复杂度
- 排序算法
- 散列表，冲突处理
- 图的深度和广度遍历是什么，工程上有什么实际应用？
- 线性存储和链式存储的优缺点比较
- 图的存储
- 图的遍历和树的遍历有什么不同
- 关键路径与关键活动的定义
原理：两点间的最短路径也包含了路径上其他顶点间的最短路径
迪杰斯特拉：带权有向图或无向图，权不可为负，单源，O(V^2 ) 弗洛伊德：带权有向图或无向图，权可为负，负权边不可为环，所有顶点之间，O(V^3 )
生成树 为极小连通子图，包含所有点，尽可能少的边。 最小生成树 为边权值之和最小的边。一般不唯一，只有在边权值都不相等时唯一。
普里姆 以点为中心，每次加最小边使一点加入联通子图，O(V^2 )，适合边密集图 克鲁斯卡尔 以边为中心，每次加最小边连接两个连通分量，O(E^2 )，适合边稀疏图
散列函数：直接定址法，除留余数法，数字分析法，平方取中法，折叠
冲突：散列函数将多个关键字映射到同一地址 处理冲突：
| 类别 | 名称 | 特点 |
|---|---|---|
| 拉链法 | 同义词存在链表中 | |
| 开放定址法 | 线性探测 | di=0,1,2,... 大量元素在相邻的散列地址上堆积，大大降低查找效率 |
| Hi=(H(key)+di)%m | 平方探测 | di=0^2 ,1^2 ,-1^2 ,2^2 ,-2^2 ,... 不能够探测到所有位置，至少一半 |
| 再散列 | di=hash2(key) | |
| 伪随机数 | di=伪随机数 | |
| 开放定址法，不能随便删除元素，会截断有相同散列地址的元素查找。可添加删除标记做逻辑删除，需要定期维护散列表，将逻辑删除的元素进行物理删除。 |
DFS，类似先序，先子节点再兄弟，递归工作栈 BFS，类似层序，先兄弟再子节点，辅助队列
两种遍历的性能一致，时间复杂度与图的存储结构有关 空间：最坏O(V) 时间：临接矩阵-》O(V^2 )；邻接表-》O(V+E)
临接矩阵，临接表 临接多重表：无向图，每条边只有一个边节点，解决了无向图的邻接表删除边不方便的问题 十字链表：有向图，可以看成临接表和逆临接表的结合，能够解决有向图求一点入度不方便的问题。
带权有向无环图DAG中，以顶点表示事件，以有向边表示活动，以边权表示完成该活动的开销，构成的网络称为AOE（activity on edge）网。 AOE网具有以下性质：
- 只有顶点所代表的事件发生后，该顶点出发的各有向边代表的活动才能开始
- 只有在进入某一顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生
从源点到汇点的有向路径有多条，其中具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。
- 可以通过加快关键活动来缩短整个工程的周期，但不能任意缩短，因为一旦缩短到一定程度，该关键活动就可能变为非关键活动。
- 网中的关键路径不唯一，对于有多条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
- 简单选择，堆排，归并，基数三个时间相同
- 快排有最快（平均等于最快），直插和冒泡有最好
- 稳定的排序：插入、冒泡、归并、基数
树中一个节点的子结点个数称为结点的度，树中节点的最大度数称为树的度
- 度为2的树子树是无序的，二叉树的子树有左右之分
- 度为2的树度一定是2，不包含空树；而二叉树的度可能为0，1，2，可以有空树的
- 集合，元素之间除了同属一个集合外，没有其他关系
- 线性，元素之间一对一
- 树形，元素之间一对多
- 图状或网状，元素之间多对多
| 名称 | 特点 | 优点 | 缺点 |
|---|---|---|---|
| 顺序 | 逻辑上相邻的元素物理存储上也相邻，元素之间的关系由存储单元的临接关系所体现 | 支持随机存储，每个元素占用最少的内存空间 | 只能使用相邻的一整块存储单元，可能产生较多的外部碎片 |
| 链式 | 逻辑上相邻的元素物理存储上不一定相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系 | 不会产生碎片，能充分利用所有存储单元 | 只能顺序存取 |
| 索引 | 建立附加索引表，每个索引项一般形式为（关键字，地址） | 检索速度快 | 索引表占用较多的存储空间，增加和删除时需要修改索引表，需要更多的时间 |
| 散列 | 根据元素的关键字直接计算存储地址 | 检索、增加、删除都很快 | 若散列函数不好，可能出现元素存储单元的冲突，解决冲突会增加时间和空间开销 |
对于n个结点的二叉树，其二叉链表存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。引入线索二叉树是为了加快查找节点前驱和后继的速度。
一棵空树，或者是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 左、右子树也分别为二叉排序树；
- 没有键值相等的结点。
对二叉排序树进行中序遍历，可得到递增序列。 二叉排序树的删除：叶子节点直接删除；只有一颗左子树或右子树，直接替代；左右子树都存在，用直接后继替代，且删除直接后继