考研网,考研考生的精神家园。祝大家考研成功 梦想成真!
注册 | 登陆 | 注销 | 会员中心 | 网站公告 |
您现在的位置: 教育频道-新都网 >> 考研 >> 考研专业课 >> 计算机学科专业基础综合 >> 正文

考研计算机数据结构复习重点解析:图的应用

作者:佚名    文章来源:文都教育    点击数:    更新时间:2010/12/24

    图是数据结构科目中难度最大的重点章节,在这两年的考试中也作为重点来考查。图这部分内容概念多、算法多、难度大。这就需要大家深刻理解每个知识点,多做练习,抓住规律,才能很好地解答这部分试题。图这部分要求大家掌握图的定义、特点、存储结构、遍历、图的基本应用等内容。图这部分的重点和难点是图的基本应用,这在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]表示弧<Vi, Vj>上的权值。若<Vi, Vj>不存在则置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]<D[k]则修改D[k]为D[k]=D[j]+edges[j][k]
    重复操作(2)(3)共n-1次。由此求得从Vs到图上其余各顶点的最短路径。
    2.Floyd算法
    Floyd算法的核心思想是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
    建议大家重点掌握这两种最短路径算法,并多做习题来巩固。《计算机学科专业基础综合辅导讲义同步练习》中一道娱乐中心选址问题就是应用Floyd算法来求解的。
    三、 拓扑排序
    1.拓扑排序基本概念
    AOV网是一种可以形象地反映出整个工程中各个活动之间前后关系的有向图。在AOV网中,若不存在回路,则所有活动可排成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,那么该序列为拓扑序列。
    2.拓扑排序特点:
    (1)拓扑序列不是唯一的。
    (2)AOV网不一定都有拓扑序列。在AOV网中如果出现了有向环,则意味着某项活动应以自己作为先决条件,这是不对的,工程将无法进行。
    大家要注意拓扑排序的应用,例如:利用拓扑排序判断一个图中是否存在回路。
    四、 关键路径
    若在带权的有向图中,以顶点表示事件,有向边表示活动,边上的权值表示完成该活动的开销(如该活动所需的时间),则称此带权的有向图为AOE网。
    AOE网中,从开始顶点到结束顶点之间路径长度中的最大路径为关键路径。由于AOE网中某些子工程(活动)可以同时进行,要保证每个子工程都能完成,完成该工程的最少时间就是该工程AOE网的关键路径长度。
    这部分要求大家能够求解关键路径,同步练习和《计算机学科专业基础综合考试全真模拟试题集》都配有相应的练习题。
    目前已进入备考的最后冲刺阶段,建议大家在做模拟题时,选择与真题题型一致、题目难度和真题难度高度相近的模拟题,并严格按照考试时间来做模拟题。

(责任编辑:admin)


查看更多关于考研专业课的文章
快速导航
培训信息
特别说明
    由于各方面情况的不断调整与变化,新都教育所提供的招生和考试信息仅供参考,敬请考生以权威部门公布的正式信息为准。
版权声明
    凡本网注明“来源:新都教育”的所有作品,版权均属于新都网,未经本网授权不得转载、摘编或利用其它方式使用上述作品。已经本网授权使用作品的,应在授权范围内使用,并注明“来源:新都教育”。违反上述声明者,本网将追究其相关法律责任。
  凡本网注明“来源:XXXXX(非新都教育)”的作品,均转载自其它媒体,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。
  如作品内容、版权等存在问题,请在两周内同本网联系,联系邮箱:newdu2004@tom.com
  本网欢迎原创作品投稿,投稿邮箱:newdu2004@tom.com
  • 考研栏目导航
  • 招考资讯
    考试新闻
    招生简章
    考试大纲
    考研政策
    分数线及成绩
    录取调剂
    院校信息
    专业介绍
    综合新闻
    公告通知
    考研政治
    政治指导
    马克思主义基本原理概论
    毛泽东思想和社会主义理论
    中国近现代史纲要
    思想道德修养与法律基础
    形势与政策以及当代世界经济与政治
    历年真题
    模拟试题
    专项训练
    考研英语
    英语指导
    英语知识运用
    阅读理解
    写作
    历年真题
    模拟试题
    专项训练
    考研数学
    数学指导
    高等数学
    线性代数
    概率论与数理统计
    历年真题
    模拟试题
    专项训练
    考研专业课
    综合指导
    计算机学科专业基础综合
    植物生理学与生物化学
    动物生理学与生物化学
    教育学专业基础综合
    心理学专业基础综合
    管理类联考综合能力
    法硕联考专业基础
    法硕联考综合
    历史学基础
    西医综合
    中医综合
    化学
    日语
    俄语
    其它专业课
    历年真题
    模拟试题
    专项训练
    考研复试
    综合辅导
    综合辅导
    真题解读
    专家访谈
    专家解读
    备考经验
    经验技巧
    考研故事
    综合辅导
    考研网,考研门户网站,提供考研院校信息,考研论坛,报考指南,招生简章,复习资料,专业试卷,考研题库,考研政治,考研英语,考研数学,考研分数,考研调剂,考研经验,考研心情等考研信息。
    Copyright © 2004-2009 Newdu.com All Rights Reserved 京ICP备09058993号
    本站为非经营性网站,收藏资料纯属个人爱好,若有问题请联系管理员:newdu2004@tom.com