海南海大源欢迎您!
知识创造价值  诚信赢得尊重
66185800  66298600
海大源欢迎您!
海南专升本考前培训网
针对海南省专升本考试
海大源欢迎您!
考取的学员中86%以上来自海大源
知识创造价值 诚信赢得尊重
针对海南省专升本考试
通知公告
  
    
海南热带海洋学院计算机专业数据结构复习方法
来源: | 作者:hdzsbcom | 发布时间: 2019-08-12 | 1409 次浏览 | 分享到:

我们认为学习数据结构这门课程至少要经历三个过程,方可真正掌握这门课程,得到一个满意的成绩。这个过程简单来说就是6个字:“活学”、“死记”、“活用”。(海大源提供)

  首先,是一个学“活”的过程,就是要求我们对每一个算法,能够在脑海中建立起相应的模型,而不是死板的算法。比如树的遍历非递归算法,在入栈与出栈的过程中,我们就要在脑海中形成访问树的每个结点的过程,真正掌握住这个算法,这样,全书复习下来,脑海中就有了整个数据结构的模型概念,对任何一个陌生的算法,将不会感到生疏和害怕。

  有些同学到了此处就觉得数据结构已经学好,可以万事大吉了,其实这还远远不够,如果参加考试,往往会拿不到高分,甚至还会纳闷,为何自己数据结构学得这样好,成绩却不尽如人意呢?所以需要有第二个过程,就是一个“死记”的过程,这个过程要求记住书中的算法。功利一点就是要背诵考试大纲中所要求的算法。这一过程也许有些枯燥,但却是最重要的过程,比如说背会了树的后序遍历非递归,遇到了像求某个结点的所有祖先,两个结点的共同祖先这样的题,不用想,直接套用。在考场上,遇到考题,不用思考,直接从脑海中找匹配的算法,直接引用。达到这样的境界,考高分就轻松很多了。(海大源提供)

  有了第二个过程的辛苦,一般就能得到一个比较高的分数了,如果还想提高,就要进行第三个过程——“活用”的过程。这一个过程中要求我们在第二步的基础上,多进行思考,看看哪些算法有共性,比如说,树的前序非递归遍历算法和图的深度优先遍历算法是不是类似啊,有些什么不同,有些什么相同,为什么会相同;森林转化为二叉树和图的生成树的算法也是这样,等等。总结出各样共性和特性就能正确有效地记忆算法,同时,遇到难题不至于慌乱,能够从容下手解题。(海大源提供)

  对于总结共性的问题,这里举一个小例子,比如树的遍历,不管是递归还是非递归,也不管是线索树还是头结点有父母信息的树,它的遍历其实就是一个寻找到要访问的第一个结点,然后再寻找它的后继结点的过程,我们归纳到此处,就可以试着总结一下三种遍历的后继结点是哪个,有几种情况:

  对于前序遍历,它的后继如下:

  1)若有左孩子,则后继是左孩子;

  (2)若无左孩子,有右孩子,则后继是右孩子;

  3)若既无左孩子,又无右孩子,则是一片叶子。对(3)再讨论:

  a)若是其父母的左孩子,且父母有右孩子,则后继是父母的右孩子;

  b)若是其父母的左孩子,且父母无右孩子;

 c)若是其父母的右孩子。

  (b)和(c)都表示这是某个结点的左子树前序遍历的最后一个结点,则需要找第一个有右子树的“左祖先”(“左祖先”,即第一个使得当前结点在这个祖先的左子树上的结点),然后后继就是这个祖先的右孩子。

   对于中序遍历,它的后继如下:

  1)若有右孩子,后继是右孩子的最左下结点;

  2)若无右孩子,且是父母的左孩子,则后继就是父母;

  3)若无右孩子,且是父母的右孩子,则一直上溯到第一个“左祖先”(定义如前),后继就是这个祖先。若无这样的祖先,说明已经遍历完毕。

   对于后序遍历,它的后继如下:

  1)若是父母的右孩子,则后继是父母;

  2)若是父母的左孩子,且父母无右子树,则后继是父母;

  3)若是父母的左孩子,父母有右子树,则后继是父母右子树的最先访问到的结点(指向父母的右子树后,一直往左,若不行的话,往右一步,一直到叶子)。

  总结完了,想一想,我们还能得到哪些启示?经常有一类型题目,要求求某个结点的直接前驱。其实求前序遍历的前驱和求后序遍历的后继是一样的,只不过把左换成右而已,前序遍历的求后继和后序遍历的求前驱、中序遍历的求前驱和中序遍历求后继都有这样的对称关系。因此,总结出共性的东西,许多题目就可以迎刃而解了。看到这里的读者,你现在能够在脑海中,非常轻松地像上面那样,把这个例子中的情况都条理清楚地分析总结出来吗?如果现在还不行,到考试之前,你必须掌握到这种程度,才能得到一个自己满意的分数。

如果踏踏实实经过以上三个过程的复习,对数据结构的掌握就可以到达比较高的水平了;参加研究生入学考试,获得一个比较满意的成绩也就很有希望了。当然,达到这一步并不容易,大量的练习是真正掌握的必由之路。因此,我们建议大家能够下功夫把本书中的题目完整地做一遍。能够真正掌握本书中的所有题目,不仅仅意味着学会了书中这几百道题目,更意味着对数据结构这门课程有了深刻的理解,以及对问题的分析能力也有很大的提高,这样在考场上即使遇到未曾见过的题目,也就可以从容应对了。   

  最后总结:专升本计算机专业数据结构这门课要特别注意哈夫满树、最小生成树和非常典型的一些图,这几个章节的内容每年都会以大题的形式出现,而且分值还不低。其中树有很多结论和定义,会在选择和填空题中考到,要熟记!(海大源提供)

方 加

便 我

沟 微

通 信

光 荣 榜
报考说明
  
最新文章
网站导航