《2022年计算机考研大纲解析之数据结构 .pdf》由会员分享，可在线阅读，更多相关《2022年计算机考研大纲解析之数据结构 .pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2012 计算机考研大纲解析之数据结构2012 年计算机 统考 大纲 已经公布，我们第一时间来解析一下计算机 统考大纲 数据结构部分及其相关知识点：数据结构占了45 分，和 计算机 组成原理部分同一个比重，这足以体现计算机 专业研究生选拔对数据结构课程的要求之重。一、 大纲 变化2012 年计算机 统考的数据结构部分大纲 都是变动在第六部分的排序方面，具体如下：2011年大纲2012年大纲变动六、内部排序六、排序将内部排序范围扩展为排序( 一)排序的基本概念( 一)排序的基本概念无变化( 二)插入排序( 二)插入排序无变化1.直接插入排序2.直接插入排序无变化2.折半插入排序3.折半插入排序无
2、变化( 三)起泡排序 (bubblesort)( 三)起泡排序 (bubblesort)无变化( 四)简单选择排序( 四)简单选择排序无变化( 五)希尔排序 (shellsort)( 五)希尔排序 (shellsort)无变化( 六)快速排序( 六)快速排序无变化( 七)堆排序( 七)堆排序无变化( 八 )二 路 归 并 排 序 (mergesort)( 八 )二 路 归 并 排 序 (mergesort)无变化( 九)基数排序( 九)基数排序无变化( 十) 外部排序新增加( 十 )各种内部排序算法的比较( 十一 )各种排序算法的比较将内部排序范围扩展为排序( 十一 )内部排序算法的应用( 十
3、二 )排序算法的应用将内部排序范围扩展为排序二、重难点解析和复习建议2012 年的统考 大纲 对数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法， 掌握数据的逻辑结构、存储结构以及基本操作的实现；能够对算法进行基本的时间复杂度和空间复杂度的分析；能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C+或 JAVA 语言设计程序与实现算法的能力。当然，考生也不必因此而专门复习一遍C 或 C+程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此， 只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的
4、程序。下面我们来解析一下知识点。线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、 删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 复杂的链表上的操作也是可以出现在综合应用题当中的。栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的， 是栈与队列FILO和 FIFO 的特点。比如针对栈FILO 的特点，进栈出栈序列
5、的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2 种判断方法。 再次， 是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。树和二叉树。这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种
6、性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、 二叉树的应用 (二叉排序树、 平衡二叉树和Huffman 树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包括：满二叉树、完全二叉树节点数的计算，由树、 二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树， 线索化的实质， 计算采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定义、 性质、 建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括：二叉树的遍历算法，遍
7、历基础上针对二叉树的一些统计和操作(比如结点数统计、左右子树对换等等)，判断某棵二叉树是否二叉排序树，以上这些都要求能用递归的和非递归的算法解决， 特别要重视非递归的算法，线索化后二叉树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出Huffman 编码等等。图。在这一章中需要识记的是图以及基于图的各种定义，存储方式。 要熟练掌握图的深度遍历和广度遍历算法，这是用图来解决应用问题时常用的算法基础。需要掌握基于图的多个算法， 能够以手工计算的方式在一个给定的图上执行特定的算法求解问题。常见的应用问题直接给出或经过抽象，会成为下列问题：最小生成树求解(PRIM 算法和 KRUSKAL
8、算法，两种方法思想都很简单，但要注意不要混淆这两种方法)，拓扑排序问题(这里会用到数组实现的链表，可以注意一下)，关键路径问题(数据结构的较大难点，要把概念理解透，能做出表格找出关键路径)，最短路径问题(有重要的应用背景，也是贪心法不多的能给出最优解的典型问题之一 )。查找。这一章，需要识记关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL 的概念念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL 值， B-树的概念和基本操作冲突解决方法的选择和冲突处理过程的描述， B+树的概念 (新增考点 )，特别要注意B-树和 B+ 树概念的对比，以及H
9、ash表相关的概念。要熟练掌握顺序表、链表、二叉树上的查找方法，特别要注意顺序查找、二分查找的适用条件 (比如链表上用二分查找就不合适)和算法复杂度。排序。 2012 最新的 大纲 将去年的内部排序范围扩展为排序，排序既是重点，又是难点。排序算法众多，今年大纲 还加上了外部排序，总共10 种，各种不同算法还有相应的一些概念定义需要记住。 选择题常见的问题包括：给定数列要求给出某种特定排序方法运行一轮后的排序结果， 或者给出初始数列和一轮排序结果要求选择采用的排序算法，给定时间、 空间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 复杂度要求以及数列特征要求选择合适的排序算法等等。如果排序这一考点出现在综合应用题中则常与数组结合来考查。参考书建议大家用清华严蔚民版的，有助于建立知识体系，并且讲的比较通透。数据结构的复习要紧扣参考书，把书认真看几遍，深入理解大纲 相关的知识点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -