计算机数据结构复习:重要知识点解析

本站小编 海文教育/2015-05-26

  从计算机统考大纲数据结构部分及其相关知识点可以看出:数据结构占了45分,和计算机组成原理部分同一个比重,这足以体现计算机专业研究生选拔对数据结构课程的重视程度。针对这样的情况,相关专家为我们的考生们精心准备了一些数据结构复习的建议。

  统考大纲对数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法,掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算 法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析求解,具备采用C、C++或JAVA语言设计程序与实现算法 的能力。

  当然,考生也不必因此而专门复习一遍C或C++程序设计,毕竟复习时间有限,而且数据结构要求的重点在于算法设计的能力,而不是编写代码的能力,因此,只要能用类似伪代码的形式把思路表达清楚就行,不用强求写出一个没有任何语法错误的程序。

  下面我们来解析一下知识点:

  线性表这一章里面的知识点不多,但要做到深刻理解,能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点,诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。

  栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的,是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点,进栈出栈序 列的问题常出现在选择题中。其次,是栈和队列的顺序和链式存储结构,这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作,特别是循环队 列判满和判空的2种判断方法。再次,是特殊矩阵的压缩存储,这个考点复习的重点可以放在二维矩阵与一维数组相互转换时,下标的计算方法,比如与对角线平行 的若干行上数据非零的矩阵存放在一维数组后,各个数据点相应的下标的计算。这一章可能的大题点,在于利用堆栈或队列的特性,将它们作为基础的数据结构,支 持实际问题求解算法的设计,例如用栈解决递归问题,用队列解决图的遍历问题等等。

  树和二叉树:这一章中我们从顺序式的数据结构,转向层次式的数据结构,要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉 树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树),重点要熟练掌握的,是森林、树以及二叉树的前中后三种遍历方 式,要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点,复习时要特别关注。一些常见的选择题考点包括:满二叉树、完全二叉树节点数的计 算,由树、二叉树的示意图给出相应的遍历序列,依据二叉树的遍历序列还原二叉树,线索化的实质,计算采用不同的方法线索化后二叉树剩余空指针域的个数,平 衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括:二叉树的遍历算法,遍历基础上针对二叉树的一些统计和操作 (比如结点数统计、左右子树对换等等),判断某棵二叉树是否二叉排序树,以上这些都要求能用递归的和非递归的算法解决,特别要重视非递归的算法,线索化后 二叉树的遍历算法,如查找某结点线索化后的前驱或后继结点的算法以及给出Huffman编码等等。

  图:在这一章中需要识记的是图以及基于图的各种定义,存储方式。要熟练掌握图的深度遍历和广度遍历算法,这是用图来解决应用问题时常用的算法基 础。需要掌握基于图的多个算法,能够以手工计算的方式在一个给定的图上执行特定的算法求解问题。常见的应用问题直接给出或经过抽象,会成为下列问题:最小 生成树求解(PRIM算法和KRUSKAL算法,两种方法思想都很简单,但要注意不要混淆这两种方法),拓扑排序问题(这里会用到数组实现的链表,可以注 意一下),关键路径问题(数据结构的较大难点,要把概念理解透,能做出表格找出关键路径),最短路径问题(有重要的应用背景,也是贪心法不多的能给出最优 解的典型问题之一)。

  查找:这一章,需要识记关键字、主关键字、次关键字的含义;静态查找与动态查找的含义及区别;平均查找长度ASL的概念念及在各种查找算法中的 计算方法和计算结果,特别是一些典型结构的ASL值,B-树的概念和基本操作冲突解决方法的选择和冲突处理过程的描述,B+树的概念(新增考点),特别要 注意B-树和B+树概念的对比,以及Hash表相关的概念。要熟练掌握顺序表、链表、二叉树上的查找方法,特别要注意顺序查找、二分查找的适用条件(比如 链表上用二分查找就不合适)和算法复杂度。

  排序:最新的大纲将去年的内部排序范围扩展为排序,排序既是重点,又是难点。排序算法众多,今年大纲还加上了外部排序,总共10种,各种不同算 法还有相应的一些概念定义需要记住。选择题常见的问题包括:给定数列要求给出某种特定排序方法运行一轮后的排序结果,或者给出初始数列和一轮排序结果要求 选择采用的排序算法,给定时间、空间复杂度要求以及数列特征要求选择合适的排序算法等等。如果排序这一考点出现在综合应用题中则常与数组结合来考查。

  数据结构的复习要紧扣参考书,把书认真看几遍,深入理解大纲相关的知识点。

  本文由万学教育供稿。


相关话题/计算机

  • 领限时大额优惠券,享本站正版考研考试资料!
    大额优惠券
    优惠券领取后72小时内有效,10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材,产品类型包含电子书、题库、全套资料以及视频,无论您是考研复习、考证刷题,还是考前冲刺等,不同类型的产品可满足您学习上的不同需求。 ...
    本站小编 Free壹佰分学习网 2022-09-19
  • 2016计算机考研:二叉树重要知识点
      二叉树是数据结构中的重点内容,在这两年的考试中也将二叉树作为重点内容来考查。二叉树这部分内容要求大家掌握二叉树的定义、性质、存储结构、 遍历、线索化、森林和二叉树的转换等内容。算法的重点是二叉树的遍历及其应用,这也是二叉树这部分的重点和难点。遍历是二叉树各种操作的基础,可以在遍历 过程中对结点进行 ...
    本站小编 海文教育 2015-05-26
  • 2016考研专业:计算机专业特点及复习重点
      计算机学科专业基础综合考试包括数据结构、计算机组成原理、操作系统与计算机网络四大科目,内容繁多,考查面广。正所谓良好的开端是成功的一半,文都教育考研命题组老师总结给处于复习基础阶段的考生要特别注意依据以上四门学科的特点、复习的重点和关键。以此着手,严格依据最新考试大纲的规定各个击破,可为复习全程 ...
    本站小编 海文教育 2015-05-26
  • 2016考研专业:计算机专业考研备考要点
      计算机专业基础为全国统考科目,由数据结构、计算机组成原理、操作系统、计算机网络四部分组成,该科目涉及范围广、内容多,需要投入大量精力。  资料选择工欲善其事,必先利其器  教育部考试中心的《计算机学科专业基础综合考试大纲》规定了考试的范围、要求、形式、试卷结构等,这本薄薄的小册子是 ...
    本站小编 海文教育 2015-05-26
  • 2016考研专业:计算机专业考研复习规划
      时值四月,考研备战的征程已经开始。对报考计算机专业的广大考生而言,除了政治、英语、数学三门公共课之外,对最终成绩举足轻重的计算机统考专 业课的复习同样是先下手为强。基础阶段复习,顾名思义,以夯实基础知识、掌握基本解题方法为重。这一阶段的复习需着重注意以下几方面的问题:   一。阶段复 ...
    本站小编 海文教育 2015-05-26
  • 2015北京大学计算机技术硕士复试
      北京大学计算机技术硕士  复试形式:上机+面试(差额复试)  一、上机  程序设计导引及在线实践。  二、面试  面试很重要(基础一定得扎实,最好对要报考的方向有一定的了解)  调剂:可以调剂深圳(分数达到深圳的复试线)或软院(分数达到软院分数线)  北京林业大学计算机技术专硕  一、外语听力及口语  英 ...
    本站小编 跨考教育 2015-05-26
  • 安徽大学2014计算机考研真题回忆版
    安徽大学2014计算机考研真题回忆版 (仅知识点回忆) (数据结构与操作系统) 第一部分、数据结构 一、小题目 1、数据结构有哪些存储方法? 2、判断单链表为空的条件? 3、在单链表中插入一个结点的操作 4、链表和顺序表存放的区别,顺序表中插入或删除需要移动多少个元素。 5、有关循环队列的操作(忘记什么题了, ...
    本站小编 免费考研网 2015-05-14
  • 河海大学2014年计算机838初试试题
    河海大学2014年计算机838初试试题 说明:阴影部分为试卷上的原题,还有几个题目的实在是没有回忆出来 一、 选择题(本题共15小题,每题2分,共30分) 1. 【知识点:数组压缩存储】 A[N,N]是对称矩阵,将下面三角(包括对角线)以行序存储到一维数组T[N(N+1)/2] 中,则对任一上三角元素a[i][j]对应T[k]的下标k ...
    本站小编 免费考研网 2015-04-30
  • 2014年同等学力申硕计算机科学与技术真题
    2014年同等学力申硕计算机科学与技术真题 ...
    本站小编 中国教育在线 2015-04-26
  • 2013年同等学力申硕计算机科学真题
    2014年同等学力申硕考试在即,中国教育在线整理了2013年同等学力申硕计算机科学真题,供广大考生复习参考! ...
    本站小编 中国教育在线 2015-04-25
  • 同等学力申硕热门专业介绍——计算机专业
    计算机科学与技术学科可分为理论计算机科学、计算机软件、计算机系统结构。计算机应用技术等领域以及与其他学科交叉的研究领域,如人工智能、应用数学等。计算机应用技术专业是一应用十分广泛的专业,它以计算机基本理论为基础,突出计算机和网络的实际应用。  热门院校:清华大学、北京大学、北京航空航天大学、西安交通 ...
    本站小编 中国教育在线 2015-04-25