考研计算机专业的考点解析；加权图的最短路径算法及其应用Di jkstra算法求单源最短路径，算法思想:设S为最短距离已确定的顶点集(见红点集)，V-S为最短距离未确定的顶点集(见蓝点集)。
1.初始化:初始化时，只知道源点S的最短距离(SD(s)=0)，所以红点集合S={s}，蓝点集合为空。
2.重复下面的工作，按照路径长度递增的顺序生成每个顶点的最短路径，从当前蓝点集合中选择一个距离最短的蓝点来扩展红点集合，保证算法按照路径长度递增的顺序生成每个顶点的最短路径。当蓝点集合中只剩下距离∞最短的蓝点，或者所有蓝点都已经扩展到红点集合时，就会找到从S到所有顶点的最短路径。

武汉考研一对一辅导班排名一览-计算机专业考研
注:①如果从源点到蓝点的路径不存在，可以假设蓝点的最短路径是一条无限长的虚拟路径。②从源点S到目的点V的最短路径简称为V的最短路径；从S到V的最短路径长度缩写为V的最短距离，记为SD(v)。
堆排序大根堆的定义:完全二叉树，任意非叶节点大于等于其子节点，即根节点最大。显然，一个大根堆的任何子树也是一个大根堆。堆排序的基本思想:记录分为前后两部分:无序区和有序区。利用无序区域的个数建立一个大的根堆，然后将得到的根(最大个数)与最后一个无序区域的个数交换。也就是说，根被分类为有序区域的前端。重复该操作，直到有序区域扩展到整个记录区域。具体操作可以按照以下步骤实现:

武汉考研一对一辅导班排名一览-计算机专业考研
1.建一个大根桩
2.交换无序区的根和最后一个数。
3.重建大根堆，因为交换只改变根，所以左右子树分别还是大根堆。
4.比较根，左边子树的根和右边子树的根。如果根最大，就不需要做任何调整。树已经是大根桩了；如果左子树的根最大，则与根交换，然后递归调整左子树；如果右子树的根最大，就和根交换，然后递归调整右子树的个数。
5，递归调整到叶子，树就是一大堆。
各种排序算法的特点和比较几种主要的排序算法:冒泡排序、选择排序、插入排序、快速排序、归并排序、外壳排序、堆排序等等。
冒泡排序算法的思想是，将待排序的元素视为垂直排列的“冒泡”，较小的元素较轻，要向上浮动。在冒泡排序算法中，我们要多次处理这个“冒泡”序列。所谓一次处理，就是自下而上检查顺序，时刻注意相邻两个元素的顺序是否正确。如果发现相邻的两个元素顺序不对，也就是“轻”的元素在下面，就交换。