数据结构应该会的操作型应用题
结合王道辅导书总结了几点数据结构里需要理解的应用题型，算是作为最后几天复习应用题时的一个引导吧（并没有详细的解释过程 只能算是一个清单略加几点备注说明而已），
如有错误，欢迎指正（这是 篇总结 张草稿纸，23333，自用留档）
二叉排序树的删除操作
⑴右子树空，用左子女填补
⑵左子树空，用右子女填补
⑶左右均不空，用右子树中序遍历第一个子女结点填补
平衡二叉树
各种昏天黑地的旋转：
LL（右单旋转）：由结点A的左孩子（L）的左孩子（L）引起的不平衡
RR（左单旋转）：由结点A的右孩子（R）的右孩子（R）引起的不平衡
LR（先左后右双旋转）：由结点A的左孩子（L）的右孩子（R）引起的不平衡
RL（先右后左双旋转）：由结点A的右孩子（R）的左孩子（L）引起的不平衡
平均查找长度
二叉树 的平均查找长度（ASL）应注意的是查找失败时候的ASL的计算易错的地方：
每一层上失败结点的个数 * 失败结点上一个结点（因为失败结点实际上是不存在的）到跟结点的路径长度
注：注意折半查找和分块查找
邻接矩阵，邻接表的画法
这个很简单了，翻下资料注意下细节就可以了。
图的遍历
图的遍历有两种，一个是广度优先（BFS），一个是深度优先（DFS）：
I.广度优先就是先找完一个结点的所有相邻结点（直连的，一步到位的结点，不用转车）然后查找相邻结点的相邻结点，过程同二叉树的层次遍历
II.深度优先就是一条道走到黑，不到死胡同不回来，有回退，退回到死胡同的上一个路口换条路继续走（并不是回退到根结点）
最小生成树
Prim（普里姆）算法和Kruskal（克鲁斯卡尔）算法：
P：从已有点集（已经选中的点）中找与这些点相连的权值最小的边，由点找边
K：从所有边中找权值最小的边和两端的结点（保证不会与已有的边构成回路），由边找点
最短路径
⊙ 一个是单源最短路径，Dijkstra算法
每一轮中路径最小的值对应的结点作为新的中转站，同时确定了结点的最短路径
⊙ 一个是多源（我是这么记得，王道上好像没这个词）路径最短，Floyd算法
拓扑排序
AOV网 ，V顶点集 顶点表示活动
注：拓扑序列唯一，图不一定唯一
关键路径
AOE网，E边集 边表示活动
I.事件的最早发生时间Ve(i) 前提事件完成用的最短时间
II.事件的最迟发生时间Vl(i） 从后往前推
III.活动的最早发生时间e(i) 弧尾的Ve（i）
IV.活动的最迟发生时间l(i) 弧头的Vl(i)-weight
B树的插入和删除
删除分为分为被删结点在终端结点和非终端结点两种情况
插入和删除的难点在于分裂和合并，实际操作一下就明白了
Hash函数
构造散列表比较简单，需要理解的是ASL的求解，可以参看一下王道书上P269页的第三题
KMP算法
搞懂一次忘一次，我太难了。。。。。
各种排序算法每一趟的结果
主要就是三类：插入，交换，选择；外加一个归并
原来打字也好麻烦啊，敲不动了
