计算机专业考研备考知识点汇总(计算机专业考研备考知识点总结)

进入备考冲刺期，知识点的复习和强化是这个阶段必须要做的事情。为了帮助您更好的积累计算机专业考研知识点，我们为您准备了相关内容，以备考计算机专业考研知识点。

1.队列和栈结构的概念理解

栈是一张线性表，将插入和删除操作限制在表的一端。栈的末尾称为栈顶。当表中没有元素时，栈为空。堆栈按照后进先出的原则进行修改。通常栈有两种存储结构：顺序栈和链式栈。

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

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

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

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

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

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

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

5、原地反转单链表，voidReverse(Listl)；使用三个指针分别表示前驱节点、当前节点和后继节点。每次将当前节点的Next指向前驱节点，然后向后遍历，直到链表末尾。

3、二叉树遍历

遍历的过程是将具有非线性结构的二叉树中的节点排列成线性序列的过程。

二叉树的遍历方法可以分为两类。一种是“广度优先”方法，从根节点开始，从上到下、从左到右逐层遍历；另一种是“深度优先”方法。 ”，即一棵子树遍历一棵子树。

4.最短路径算法及加权图的应用

Dijkstra 算法找到来自单个源的最短路径。算法思路：

令S 为已确定最短距离的顶点集合（视为一组红点），V-S 为尚未确定最短距离的顶点集合（视为一组蓝点） ）。

1、初始化：初始化时，只知道源点s的最短距离（SD(s)=0），所以红色点集S={s}，蓝色点集为空。

2. 重复以下工作，按照路径长度递增的顺序生成每个顶点的最短路径。在当前蓝色点集中选择一个最短距离最小的蓝色点来扩展红色点集，以保证算法按照路径长度递增的顺序为每个顶点生成最短路径。小路。

当蓝色点集中只剩下最短距离为 的蓝色点，或者所有蓝色点都已扩展到红色点集中时，找到从s 到所有顶点的最短路径。

注：如果从源点到蓝点的路径不存在，则可以认为到蓝点的最短路径是一条无限长的虚拟路径。 从源点s到终点v的最短路径称为v的最短路径；从s到v的最短路径的长度称为v的最短距离，记为SD(v)。

5.堆排序

大根堆的定义：完全二叉树。任何非叶节点都大于或等于其子节点，这意味着根节点是最大的。显然，大根堆的任何子树也是大根堆。

堆排序的基本思想：记录区域分为两部分：无序区域和有序区域；使用无序区中的数字构建一个大的根堆，并将得到的根（最大的数字）与无序区中的最后一个数字交换。即根放在有序区域的前面；重复此过程，直到有序区域扩展到整个记录区域。

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

1. 建立一个大的根堆。

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

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

4. 比较根、左子树的根和右子树的根。如果根最大，则无需进一步调整。树已经是一个大根堆了；如果左子树的根最大，则与根交换，然后递归调整。左子树；如果右子树的根最大，则与根交换，然后递归调整右子树的数量。

5. 当递归调整到达叶子时，树就变成了一个大根堆。

6.各种排序算法的特点及比较

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

冒泡排序算法的思想：将待排序的元素视为垂直排列的“冒泡”。较小的元素更轻并且向上漂浮。在冒泡排序算法中，我们必须多次处理这个“冒泡”序列。

所谓一次性处理，就是从下到上检查顺序，时刻关注相邻两个元素的顺序是否正确。如果发现两个相邻元素的顺序错误，即“亮”的元素在下面，则交换它们的位置。

选择排序算法思想：选择排序的基本思想是将待排序的记录序列处理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] 的任何计算都已排序。

归并排序算法思想：分而治之（divide-conquer）。

每个递归过程包括三个步骤： 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]调整为堆。

7. 二叉树及其遍历

从整体二叉树结构来看，二叉树可以分为三个部分：根节点、左子树和右子树。只要遍历完这三部分，二叉树就遍历完了。假设D代表根节点，L代表左子树，R代表右子树，则DLR有六种组合，分别是DLR、DRL、LDR、LRD、RDL和RLD。

如果限制为先左后右，那么就只有三种：DLR、LDR、LRD，分别称为前（前）序法（第一根序法）、中序法（中根）序法、对称法）和后序法（最后序法）。根序法）。三种遍历的递归算法如下：2019考研冲刺班

1. 预订方式（DLR）

如果二叉树为空，则不进行操作，否则：访问根节点-按顺序遍历左子树-按顺序遍历右子树。

2. 中间顺序法（LDR）

如果二叉树为空，则不进行操作，否则：中序遍历左子树——访问根节点——中序遍历右子树。

3. 后序法（LRD）

如果二叉树为空，则不进行操作，否则：后序遍历左子树——后序遍历右子树——访问根节点。

8、完全二叉树相关节点数的计算

完全二叉树的定义：深度为k、有n 个节点的二叉树，当且仅当其每个节点对应于深度为k 的满二叉树中编号为1 到n 的节点时，称为完全二叉树。二叉树。

完全二叉树的叶子数为(n+1)/2 向下舍入。

9、森林和二叉树之间的转换以及转换过程中节点之间的关系

将树转换为二叉树的方法是：

1. 在树中所有相邻兄弟之间添加一条连接线。

2、对于树中的每个节点，只保留它与第一个子节点之间的连接，删除它与其他子节点之间的连接。

3、以树的根节点为轴，将整棵树顺时针旋转一定角度，使结构具有层次感。

将森林转换为二叉树的方法如下：

1. 将森林中的每棵树转换为对应的二叉树。

2、第一棵二叉树不动。从第二棵二叉树开始，后一个二叉树的根节点作为前一个二叉树根节点的右子节点。当所有的二叉树连接在一起时，得到的二叉树就是由森林转换而来的二叉树。

树和森林都可以转换为二叉树。两者的区别在于：树转换成的二叉树的根节点必须没有右孩子，而森林转换成的二叉树的根节点有右孩子。将二叉树恢复为树或森林，如下所示：

1. 如果某个节点是其父节点的左子节点，则将该节点的右子节点、右子节点的右子节点、与该节点的父节点用线连接起来。

2、删除原二叉树中父节点与右子节点的所有连接。 3. 组织步骤1和2中获得的树木或森林，使结构具有层次结构。

10.了解无向连通图的特点

无向图的每条边在计算顶点（与两条边关联的两个顶点）度数的过程中必须参与计算两次，因此所有顶点的度数之和为偶数。

具有n 个顶点且边数大于或等于n-1 的无向连通图。

在无向连通图中，所有顶点的度都可能大于1。

11.理解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是关键码。

以上是对计算机专业考研准备的一些知识点的总结。您可以积累它们作为准备材料。考研最后冲刺，一定要保持状态，积极备考。

  相关文章:

  第1篇    高中物理力的合成与分解技巧(物理高中力的合成与分解)    作者：admin

   三、力(常见的力、力的合成与分解)(1)常见的力1.重力G=mg(方向竖直向下，g=9.8m/s2≈10m/s2，作用点在重心，适用于地球表面附近)2.胡克定律F=kx{方向沿恢复形变方向，k：劲度系数(N/m)，x：形变量(m)｝3.滑动摩擦力F=μFN{与物体相对运动方向相反，μ：摩擦因数，FN：正压力(N)｝4.静摩擦力0≤f静≤fm(与物体相对

  第2篇    金属及其化合物知识点总结(高中化学金属及其化合物)    作者：admin

   金属及其化合物一、金属活动性Na＞Mg＞Al＞Fe。二、金属一般比较活泼，容易与O2反应而生成氧化物，可以与酸溶液反应而生成H2，特别活泼的如Na等可以与H2O发生反应置换出H2，特殊金属如Al可以与碱溶

  第3篇    清华大学2018年自主招生人数(清华大学2018自主招生试题数学)    作者：admin

   6月10日，清华大学2018年自主招生考试全面启动，2018年清华大学自主招生、领军计划依然在全国设置多个考点，考生可就近选择。自主招生测试为初试和复试。一、笔试时间初试时间为6月10日上午9:00-12:00，共3个小时。二、笔试模式初试采用笔试形式，理科类：数学、物理、化学；文科类：数学、语文、历史。清华理科笔试都是选择，共75题，数学35道题，

  第4篇    高考语文基础知识训练试题第十三套答案(高考语文基础知识训练试题第十三套卷)    作者：admin

   1.下列划线字的读音全部相同的一项是（）A．行旅行头行将就木行贿受贿B．给予给水自给自足不给面子C．测量掂量丈量土地量入为出D．应该应届得心应手理应如此2.下列各组词语中，字形全都正确的一组是（）A．脉搏扶直贫困晶莹寥若辰星B．焕发一幅对联关键性格不合C．提纲情有可原厮打连年歉收D．幅射绿草如茵松弛旁征博引3.依次填

  第5篇    甲烷的氧化反应现象(甲烷氧化的化学方程式)    作者：admin

   甲烷的氧化反应最基本的就是燃烧，高考网为大家整理了《2016高考化学知识点：甲烷的氧化反应》，供大家参考，更多关于甲烷的氧化反应知识点详解请关注高考网。2016高考化学知识点：甲烷的氧化反应甲烷氧化反应最基本的就是燃烧：甲烷完全燃烧：CH4+2O2=CO2+2H2O甲烷不完全燃烧：2CH4+3O2=2CO+4H2O甲烷