2019计算机考研专业课核心考点梳理

　　一、队列和栈结构的概念理解

　　栈是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶。表中无元素时为空栈。栈的修改是按后进先出的原则进行的。通常栈有顺序栈和链栈两种存储结构。

　　队列是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头，允许插入的一端称为队尾，队列的操作原则是先进先出的。队列也有顺序存储和链式存储两种存储结构。

　　二、线性表中单链表相关算法设计与实现

　　一些基础但又重要的单链表相关算法，如：

　　1.打印单链表，voidPrintList(Listlist);使用一个指针遍历所有链表节点。

　　2.两个升序链表，打印tarList中的相应元素，这些元素的序号由SeqList指定，voidPrintLots(ListtarList，ListseqList);使用两个指针分别遍历两个链表，每次取出序列链表的一个序号后，根据该序号，到达目标链表指定节点。

　　3.两个升序链表的交集，ListIntersect(Listl1，Listl2)。

　　4.两个升序链表的并集，ListJoin(Listl1，Listl2)。

　　5.单链表就地置逆，voidReverse(Listl);使用三个指针表示前驱，当前和后继节点，每次将当前节点的Next指向前驱节点，然后向后遍历直到链表末尾。

　　三、二叉树的遍历

　　遍历的过程就是把非线性结构的二叉树中的结点排成一个线性序列的过程。

　　二叉树遍历方法可分为两大类，一类是“宽度优先”法，即从根结点开始，由上到下，从左往右一层一层的遍历;另一类是“深度优先法”，即一棵子树一棵子树的遍历。

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

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

　　设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.递归调整到叶子的时候，树就是大根堆了。

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

　　几种主要的排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、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]又是排好序的序列。

　　快速排序算法思想：快速排序的基本思想是基于分治策略的。