2019考研计算机核心考点集合(二)

更新时间:2018-12-05 13:19作者:王华老师

    考研计算机复习内容繁多,考察面非常广,而且理解起来也是相当困难,一直以来都是学生们头疼的科目,但是即使这样也挡不住考生们对计算机学科的热爱,近几年考研计算机一直都是热门学科。为方便大家复习,将内容化繁为简,整理总结了2019考研计算机的核心考点汇总,帮助大家后续的复习。

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

    迪杰斯特拉(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]又是排好序的序列。

    快速排序算法思想:快速排序的基本思想是基于分治策略的。对于输入的子序列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]就已排好序。

    归并排序算法思想:分而治之(pide - 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≤R[n].key。3.由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。

    为您推荐

    考研复试综合面试问题大总结

    考研复试面试很重要,如何过了这关是很多人烦恼的问题,爱扬教育网小编为大家整理了复试综合面试问题大总结,大家来看看都可能遇到什么问题:

    2019-02-15 15:11

    2019年艺术生文化科目复习策略整理

    我省2019年普通高考艺术类专业统考部分已经结束,一些艺考生往往无法像普通考生那样专心备考文化课,通常存在一个较长时间的“备考荒芜期”。小招收集整理了一些复习策略,以供参考。

    2019-01-24 16:34

    艺术类专业应该怎么填报志愿

    我国独立设置艺术类专业的院校有31所、还有985和211等重点院校、普通二本院校、等等。首先考生可依据2018年各院校的录取原则,看哪些学校是按专业分录取,哪些学校是按综合分录取,哪些学校是按文化分录取的。结合自己的实际情况,成绩在在哪方面占优势,在哪方面属于劣势,为选报学校先做一个规划。

    2019-01-24 15:17

    艺术生高考志愿该怎么填?

    许多艺考生在高考考试过后,不太知道自己在填志愿的时候该注意些什么,那么在这里爱扬教育网就为各位分享,艺考生到底该如何去填志愿,希望对大家有所帮助。

    2019-01-24 15:15

    艺考时的考试科目有哪些?

    现在很多人都想在高考的时候走艺考,可是又不知道艺考都考些什么?现在爱扬教育网小编就为大家整理了艺考的考试科目,希望能对大家有所帮助。

    2019-01-24 14:28

    2019年艺考政策有什么变化?

    随着教育改革的不断深入形式也越发严峻,2019届艺考生面临着巨大的挑战2019年艺考形势发生了什么变化?考生应该如何应对?今天爱扬教育网小编就给大家全面剖析,希望可以给大家带来帮助!

    2019-01-24 13:43

    2019年济南大学等高校面向山东省招生音乐类专业联考方案

    爱扬教育网小编从济南大学了解到,2019年济南大学等高校面向山东省招生音乐类专业联考方案已公布,具体如下:

    2019-01-24 11:42

    考研数学陌生难题再也不怕

    为了通过考试,我们都要付出很大的努力去学习各个知识点,但是,在考试的时候,总会出现一些我们比较陌生的题型,往往让人措手不及,今天就给大家分享考场答题的一些小技巧,如果在考场遇到陌生的题型,也不要慌,那么看下去吧。

    2019-01-18 16:11

    考场上如何超水准发挥

    每当到了考试临近,对于数学,很多人都比较紧张,其实,在这时候也不需要再做大量的题目,主要是回归教材,总结基本概念、基本公式、基本定理,放慢节奏,调整心态,将自己调整为最佳状态,争取将平时的积累最大化的发挥出来。今天来和你们谈谈在考场如何更好地发挥出自己的水准。

    2019-01-18 16:09

    金融专硕考研备考方法

    近年来,金融专硕就业好,学习年限低,是十分有前景性价比的一个考研专业,可是初备考的小伙伴对于该如何进行金融专硕的备考还是一头雾水。今天帮帮给大家带来详细的复习建议和规划指导,希望对大家有用~

    2019-01-18 16:04

    考研数学也需要背诵来复习

    学习生涯中,你是否因为学习数学而痛不欲生彻夜难眠?你是否因为学习数学而中年早秃面容沧桑?帮帮带来一位学姐的备考方法,让我们一起快乐的学习吧!这位同学的背景是本科双非普通一本,二战狗,初试364分,数一125分。一起来看看吧!

    2019-01-18 16:01

    考研数学这些坑你要避开

    对于准备考研的考生来说,有这么一句话,考研难,考研数学更难,这句话很多考研人都会听到。也有很多考研的同学在还没开始复习数学时就已经对数学产生了畏惧情绪。考研过程会遇到的九大锁喉题,克服了你就赢了!

    2019-01-18 15:38

    2019年高级会计师考试科目已公布

    根据《全国2019年高级会计师考务日程已公布》得知,2019年高级会计师考试科目如下:

    2019-01-18 15:28

    考研数学详细规划教给你

    相信同学们都有这样的感受,很多大三的小伙伴都提过这样一个灵魂拷问:大三考研刚刚开始备考,数学该怎么复习?很多人会简单的说先看教材然后做题什么的,今天帮帮就给大家详细讲讲,考研数学怎么开始复习。

    2019-01-18 15:19

    数学后期复习误区你要避开

    在考研复习的后期,也是到了考研的冲刺阶段,在这个阶段,要学习的东西很多,尤其是数学,知识点也很多,需要大家抓紧时间。那么在后期复习备考数学怎么复习呢?以下是数学复习的5大误区和冲刺复习的备考原则,一起看看吧。

    2019-01-18 15:17