|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
初试《数据结构》科目考试大纲
一、考查目标
考查学生对数据结构及算法分析相关基础知识及技能的掌握水
平，并对学生利用有关基础知识和技能分析研究计算机加工的数据结
构特性，进一步为实际应用涉及的数据选择及设计适当的逻辑结构、
存储结构及其相应的算法能力进行考核。
二、考试形式与试卷结构
（一）试卷满分及考试时间
满分为 150 分，考试时间为 3 小时。
（二）答题方式
答题方式为闭卷、笔试。
（三）试卷内容结构
内容结构为各部分知识点在试卷中所占的比例。
（四）试卷题型结构
选择题 10 分、简答题 20 分、解答题 80 分、算法设计题 40 分，
合计 150 分。
三、考查内容及要求
（一）数据结构概述
1、基本概念及术语
数据结构、逻辑结构、物理结构、抽象数据类型的概念；数据结
构的分类、两种物理结构的特点。
2、ADT 的表示与实现
ADT 的定义、作用及类 C 语言实现方法。
3、算法和算法分析
算法的概念、特性和评判标准、算法时间复杂度的概念、简单的
算法时间复杂度分析。
（二）线性表
1、线性表的类型定义
线性表的抽象数据类型定义、线性结构的特点。
2、线性表的顺序表示和实现
顺序表的含义、特点和相关算法。
3、线性表的链式表示和实现
链表的含义、特点和相关算法。
4、一元多项式表示与相加
一元多项式表示与相加的方法、顺序结构和链式结构的区别和选
择。
（三）栈与队列
1、栈
栈结构的抽象数据类型定义、特点、存储结构和相关算法。
2、栈的应用举例
栈的应用及相关算法。
3、队列
队列结构的抽象数据类型定义、特点、存储结构和相关算法。
（四）串
1、串类型的定义、表示和实现
串的定义、串的三种主要表示和实现方式。
2、串的模式匹配
串的常见模式匹配算法。
（五）数组与广义表
1、数组的定义
数组概念、特点。
2、数组的顺序表示和实现
数组顺序存储结构表示和实现。
3、数组的压缩存储
特殊矩阵的压缩存储、稀疏矩阵的压缩存储的实现方法。
4、广义表的定义和实现
广义表的定义及运算、广义表的存储结构。
（六）树和二叉树
1、树的定义和基本术语
树的定义、常用术语。
2、二叉树
二叉树的定义、二叉树的性质、存储结构。
3、数组的压缩存储
特殊矩阵的压缩存储、稀疏矩阵的压缩存储的实现方法。
4、遍历二叉树和线索二叉树
二叉树遍历及线索化的概念、方法和算法。
5、树和森林
树的存储结构，树、森林、二叉树间相互转换方法、树和森林遍
历方法。
6、赫夫曼树及其应用
赫夫曼树和赫夫曼编码构造方法。
（七）图
1、图的定义和术语
图的定义和术语。
2、图的存储结构
图的邻接矩阵表示法、邻接表表示法、十字链表表示法。
3、图的遍历
图的深度优先及广度优先遍历方法和算法。
4、图的连通性问题
连通子图、生成树、最小生成树的定义和构造方法。
5、拓扑排序
拓扑排序方法、算法及应用。
6、最短路径
最短路径问题求解方法、算法及应用。
7、关键路径
关键路径问题求解方法、算法及应用。
（八）查找
1、静态查找表
查找的概念、顺序查找和折半查找的方法和算法。
2、动态查找表
二叉查找树和二叉平衡概念及作用、二叉查找树和二叉平衡树相
关算法。
3、哈希表
哈希表的概念、冲突的概念、常见哈希函数构造方法、哈希表的
处理冲突的常用方法。
（九）排序
1、排序的概念
排序的有关概念、排序的类型。
2、排序方法及算法
掌握插入排序、快速排序、选择排序、归并排序、基数排序的方
法、算法及相关算法时间、空间复杂度分析过程。
四、考试用具说明
考试使用黑色笔作答,考试时需要携带计算器、直尺、笔。
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
