计算机考研核心课程(计算机考研知识点汇总)

2014考研机考：十大核心考点解析

核心测试点1：理解m阶B树的定义

m阶B树满足以下条件：

1、每个节点最多有m个子树。

2.除根节点外，其他分支至少有m/2个子树。

3、根节点至少有两棵子树（除非B树只有一个节点）。

4.所有叶子节点都在同一层。 B树的叶子节点可以视为外部节点，不包含任何信息。

5. 有j 个子节点的非叶节点恰好有j-1 个关键码，并且关键码按升序排列。节点包含的信息为：(p0,k1,p1,k2,p2,…,kj-1,pj-1)

其中ki为关键码，满足ki

核心测试点2：最短路径算法及加权图应用

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. 当递归调整到达叶子时，树就变成了一个大根堆。

核心测试点4：各种排序算法的特点及比较

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

冒泡排序算法的思想：将待排序的元素视为垂直排列的“冒泡”。较小的元素更轻并且向上漂浮。在冒泡排序算法中，我们必须多次处理这个“冒泡”序列。所谓一次性处理，就是从下到上检查顺序，时刻关注相邻两个元素的顺序是否正确。如果发现两个相邻元素的顺序错误，即“亮”的元素在下面，则交换它们的位置。

选择排序算法思想：选择排序的基本思想是将待排序的记录序列处理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.递归解决（征服）：通过递归调用快速排序算法，分别对L[p.q]和L[q+1.r]进行排序。 3、合并：由于两个分解后的子序列的排序是就地进行的，所以L[p.q]和L[q+1.r]排序后就不需要再执行了。 L[p.r] 的任何计算都已排序。

归并排序算法的思想：分而治之。每个递归过程包括三个步骤： 1. 将待排序的n 个元素的序列分解为两个子序列，每个子序列包含n/2 个元素。 2.治理：对每个子序列分别调用MergeSort来执行递归操作。 3. 合并，将两个已排序的子序列合并，生成排序结果。

希尔排序算法思想：算法首先将一组待排序的数字按照一定的增量d分为若干组，每组中记录的下标相差d。对每组中的所有元素进行排序，然后用较小的增量对其进行测量并在每组内排序。当增量减至1时，整个待排序数被分为一组，排序完成。

堆排序算法思想： 使用大根堆排序的基本思想： 1、首先将初始文件R[1.n]构建成一个大根堆，即初始无序区域。 2、然后将关键字最大（即堆顶）的记录R[1]与无序区最后一条记录R[n]交换，从而得到新的无序区R[1.n- 1]且有序区域R[n]满足R[1.n-1].keysR[n].key。 3. 由于交换后的新根R[1]可能违反堆性质，因此应将当前无序区R[1.n-1]调整为堆。

[1][2]下一页

  相关文章:

  第1篇    减法的四种算法(减法的四个运算定律)    作者：admin

   8月底，考研大纲即将公布。预注册将于9月进行，正式注册将于10月进行。考研初试离我们越来越近了。朋友们早出晚归，努力复习、收集各种材料。很多人的状态可以用“忙、累、慌、乱”来形容。是不是意味着复习越努力、收集的信息越多，考研成功的概率就越大呢？并非如此。考研，你要学

  第2篇    mpa管理类联考考什么(管理类mpa联考过国家线难吗)    作者：admin

   1.学校声誉虽然MPA的学习内容与各学校的基础课程非常相似，但附加课程却明显不同，具有很强的特色。课程的设置和重点与各学校的专业特长和教学领域有很大关系。例如，对外经济贸易学校有以海关为主的课程，农业院校有以农业或扶贫为主的课程等。考生在选择时应根据自己的喜好考虑学校的声

  第3篇    考研政治真题试卷pdf(考研政治真题试卷2022)    作者：admin

   摘要本文主要从五个角度论证研究生政考试卷的重要性和必要性。首先，研究生政治考试试卷是研究生政治考试的重要组成部分。掌握真题真题可以帮助你更好的应对考试。其次，通过分析真题，可以了解考研政治的考点和命题思路，有助于提高备考效果。第三，通过分析真题，可

  第4篇    云南大学2021年硕士研究生拟录取(2020年云南大学研究生)    作者：admin

   云南大学研究生2023录取摘要云南大学是云南省重点大学之一，以优良的学风和丰富的研究资源而闻名。随着时间的流逝，云南大学2023年研究生招生即将拉开帷幕。本文将从五个角度论证并详细介绍云南大学2023年研究生招生的重要性以及招生政策的变化。1.录取政策的变化云南大学的研究生招生政策将随着时间的推移进行调整，以更好地适应当今社会的需求。2023年招生

  第5篇    南京大学的新闻传播研究生好考吗(南京大学新闻传播专业考研)    作者：admin

   南京大学新闻传播硕士考研经验摘要本文旨在分享我作为南京大学新闻与传播专业研究生的经历。我将从多个角度来论证这一点，包括准备计划、复习方法和技巧、面试准备、学术研究和准备阶段的实践经验。本文总结了我在考研期间所学到的知识，希望对即将考