计算机#2020计算机考研究生#计算机重要考点梳理[二]

类目：三人行考研网>计算机>正文

时间：2019-10-2918:19:57

在考研冲刺强化的阶段，各位计算机学科的考研er在根据自己的进度按部就班进行复习的同时 ，也需要这样一份冲刺复习计划
，有效的复习方法是很重要的，今天三人行考研网小编大家整理的“2020计算机考研：计算机重要考点梳理(二)
” ，希望对大家有所帮助！

带权图的最短路径算法及应用

迪杰斯特拉(Dijkstra)算法求单源最短路径
，算法思想：

设S为最短距离已确定的顶点集(看作红点集)，V-S是最短距离尚未确定的顶点集(看作蓝点集)
。

1.初始化：初始化时 ，只有源点s的最短距离是已知的(SD(s)=0)
，故红点集S=s，蓝点集为空。

2.重复以下工作 ，按路径长度递增次序产生各顶点最短路径
，在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径 。当蓝点集中仅剩下最短距离为&infin的蓝点 ，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了
。

注意：①若从源点到蓝点的路径不存在
，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。②从源点s到终点v的最短路径简称为v的最短路径s到v的最短路径长度简称为v的最短距离，并记为SD(v) 。

堆排序

大根堆的定义：完全二叉树 ，任一非叶子结点都大于等于它的孩子
，也就是说根结点是最大的
。而且显然大根堆的任一棵子树也是大根堆。

堆排序的基本思想：记录区的分为无序区和有序区前后两部分用无序区的数建大根堆，得到的根(最大的数)和无序区的最后一个数交换 ，也就是将该根归入有序区的最前端如此重复下去
，直至有序区扩展至整个记录区 。

具体操作可按下面步骤实现：

1.建大根堆

2.交换根和无序区最后一个数

3.重建大根堆，因为交换只是使根改变了 ，所以左右子树依然分别是大根堆
。

4.比较根
，左子树的根和右子树的根，如果根最大 ，则无须再作调整
，树已经是大根堆了如果左子树的根最大，交换它与根 ，再递归调整左子树如果右子树的根最大，交换它与根
，再递归调整右子数。

5.递归调整到叶子的时候，树就是大根堆了 。

各类排序算法的特点及比较

几种主要的排序算法：冒泡排序、选择排序 、插入排序
、快速排序、归并排序 、Shell排序
、堆排序等
。

冒泡排序算法思想：将待排序的元素看作是竖着排列的“气泡” ，较小的元素比较轻
，从而要往上浮。在冒泡排序算法中我们要对这个“气泡 ”序列处理若干遍 。所谓一遍处理，就是自底向上检查一遍这个序列 ，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对
，即“轻
”的元素在下面，就交换它们的位置
。

选择排序算法思想：选择排序的基本思想是对待排序的记录序列进行n-1遍的处理 ，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样
，经过i遍处理之后，前i个记录的位置已经是正确的了 。

插入排序算法思想：经过i-1遍处理后,L[1..i-1]己排好序
。第i遍处理仅将L[i]插入L[1..i-1]的适当位置 ，使得L[1..i]又是排好序的序列。

快速排序算法思想：快速排序的基本思想是基于分治策略的 。对于输入的子序列L[p..r]
，如果规模足够小则直接进行排序，否则分三步处理：1.分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r] ，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值
。2.递归求解(Conquer)：过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。3.合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序 。

归并排序算法思想：分而治之(divide-conquer)
。每个递归过程涉及三个步骤：1.分解
，把待排序的n个元素的序列分解成两个子序列，每个子序列包括n/2个元素。2.治理 ，对每个子序列分别调用归并排序MergeSort
，进行递归操作 。3.合并，合并两个排好序的子序列,生成排序结果
。

Shell排序算法思想：算法先将要排序的一组数按某个增量d分成若干组 ，每组中记录的下标相差d.对每组中全部元素进行排序
，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时 ，整个要排序的数被分成一组
，排序完成 。

堆排序算法思想：用大根堆排序的基本思想：1.先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区。2.再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换 ，由此得到新的无序区R[1..n-1]和有序区R[n]
，且满足R[1..n-1].keys&leR[n].key
。3.由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。

以上就是三人行考研网小编整理的“2020计算机考研：计算机重要考点梳理(二)”相关内容 ，希望对大家有所帮助，预祝大家能考上理想的院校 。更多计算机考研信息尽在三人行考研网计算机频道！

相关推荐：

2020计算机专业考研操作系统知识点汇总

2020计算机考研院校排名推荐

2020计算机考研：计算机网络部分六大重要知识点