2011考研专业课:计算机复习_跨考网
图是数据结构科目中难度最大的重点章节,在这两年的考试中也作为重点来考查。图这部分内容概念多、算法多、难度大。这就需要大家深刻理解每个知识点,多做练习,抓住规律,才能很好地解答这部分试题。图这部分要求大家掌握图的定义、特点、存储结构、遍历、图的基本应用等内容。图这部分的重点和难点是图的基本应用,这在09年和10年的考试中有所体现。图的基本应用包括:最小生成树、最短路径、拓扑排序、关键路径等。09年考试中重点考查了最短路径的判断与证明。跨考网考研命题组建议大家把图的基本应用作为重点来复习。
下面介绍一下图的基本应用:
一、最小生成树
1.最小生成树的基本概念
最小生成树:边的权值总和最小的生成树。最小生成树有很多重要的应用。
2.最小生成树的性质 最小生成树性质:设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。若(u,v)是G中一条“一个端点在U中(例如:u∈U),另一个端点不在U中的边(例如:v∈V-U),且(u,v)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)。
3.构造最小生成树的算法
目前已有不少构造最小生成树的算法,建议大家重点复习两种常用的构造最小生成树的算法:普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。
二、 最短路径
最短路径问题是与日常生活密切相关的问题,例如:路线选择、计算机网络路由选择等,同时也是考试重点之一。
最短路径算法:
1.Dijkstra算法
Dijkstra算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。
定义G=(V,E),定义集合S存放已经找到最短路径的顶点,集合T存放当前还未找到最短路径的顶点,即有T=V-S :
Dijkstra算法描述如下:
(1)假设用带权的邻接矩阵edges来表示带权有向图,edges[i][j]表示弧上的权值。若不存在则置edges[i][j]=∞(计算机上用一个允许的最大值代替)。S为已经找到的从Vs出发的最短路径的终点集合,它初始化为空集。那么,从Vs出发到图上其余各顶点(终点)Vi可能达到的最短路径长度的初值为:D[i]=deges[s][i] Vi∈V
(2)选择Vj,使得D[j]=Min{D[i]|Vi∈V-S},Vj就是当前求得的一条从Vs出发的最短路径的终点。令S=S∪{Vj}
(3)修改从Vs出发到集合V-S上任一顶点Vk可达的最短路径长度。如果D[j]+edges[j][k]
重复操作(2)(3)共n-1次。由此求得从Vs到图上其余各顶点的最短路径。
2.Floyd算法
Floyd算法的核心思想是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
建议大家重点掌握这两种最短路径算法,并多做习题来巩固。
三、 拓扑排序
1.拓扑排序基本概念
AOV网是一种可以形象地反映出整个工程中各个活动之间前后关系的有向图。在AOV网中,若不存在回路,则所有活动可排成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,那么该序列为拓扑序列。
2.拓扑排序特点:
(1)拓扑序列不是唯一的。
(2)AOV网不一定都有拓扑序列。在AOV网中如果出现了有向环,则意味着某项活动应以自己作为先决条件,这是不对的,工程将无法进行。
大家要注意拓扑排序的应用,例如:利用拓扑排序判断一个图中是否存在回路。
四、 关键路径
若在带权的有向图中,以顶点表示事件,有向边表示活动,边上的权值表示完成该活动的开销(如该活动所需的时间),则称此带权的有向图为AOE网。
AOE网中,从开始顶点到结束顶点之间路径长度中的最大路径为关键路径。由于AOE网中某些子工程(活动)可以同时进行,要保证每个子工程都能完成,完成该工程的最少时间就是该工程AOE网的关键路径长度。
目前已进入备考的最后冲刺阶段,建议大家在做模拟题时,选择与真题题型一致、题目难度和真题难度高度相近的模拟题,并严格按照考试时间来做模拟题。
2022考研初复试已经接近尾声,考研学子全面进入2023届备考,跨考为23考研的考生准备了10大课包全程准备、全年复习备考计划、目标院校专业辅导、全真复试模拟练习和全程针对性指导;2023考研的小伙伴针也已经开始择校和复习了,跨考考研畅学5.0版本全新升级,无论你在校在家都可以更自如的完成你的考研复习,暑假集训营带来了院校专业初步选择,明确方向;考研备考全年规划,核心知识点入门;个性化制定备考方案,助你赢在起跑线,早出发一点离成功就更近一点!
考研院校专业选择和考研复习计划 | |||
2023备考学习 | 2023线上线下随时学习 | 34所自划线院校考研复试分数线汇总 | |
2022考研复试最全信息整理 | 全国各招生院校考研复试分数线汇总 | ||
2023全日制封闭训练 | 全国各招生院校考研调剂信息汇总 | ||
2023考研先知 | 考研考试科目有哪些? | 如何正确看待考研分数线? | |
不同院校相同专业如何选择更适合自己的 | 从就业说考研如何择专业? | ||
手把手教你如何选专业? | 高校研究生教育各学科门类排行榜 |
相关推荐
跨考考研课程
班型 | 定向班型 | 开班时间 | 高定班 | 标准班 | 课程介绍 | 咨询 |
秋季集训 | 冲刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+专业课1对1+专业课定向辅导+协议加强课程(高定班)+专属规划答疑(高定班)+精细化答疑+复试资源(高定班)+复试课包(高定班)+复试指导(高定班)+复试班主任1v1服务(高定班)+复试面授密训(高定班)+复试1v1(高定班) | |
2023集训畅学 | 非定向(政英班/数政英班) | 每月20日 | 22800起(协议班) | 13800起 | 先行阶在线课程+基础阶在线课程+强化阶在线课程+真题阶在线课程+冲刺阶在线课程+专业课针对性一对一课程+班主任全程督学服务+全程规划体系+全程测试体系+全程精细化答疑+择校择专业能力定位体系+全年关键环节指导体系+初试加强课+初试专属服务+复试全科标准班服务 |