友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
《数据结构（C语言版）》硕士研究生入学考试大纲
名称： 数据结构（C语言版）
科目代码：
专业类别： ■学术型 □专业学位
适用专业： 光学工程
一、课程总体要求
考生应认真把握该课程的考试、学习要求、考核知识点和有关考核的具体问题。
※ 要求数据结构算法设计题编程全部采用C语言。
1、基本理论知识
（l）什么是数据结构、基本概念和基本术语、数据结构的发展简史及它在计算机科学中所处的地位，算法的描述和算法分析。
（2）什么是线性表、在线性表上常进行的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。
（3）栈和队列的定义、表示方法和实现。
（4）串的定义及其基本操作。
（5）数组的定义、运算和存储、稀疏矩阵的压缩存储、广义表的定义和操作。
（6）树的定义、基本术语和存储结构、二叉树的定义和性质，二叉树的存储结构及其各种操作，哈夫曼树。
（7）图的定义和术语、图的存储结构及其各种操作。
（8）各种查找方法的算法、适用范围及时间复杂度的分析。
（9）内部排序、基数排序和比较排序，各种基本排序方法的算法和时间复杂度。
2、基本技能
（1）能阅读用类C语言编写的算法。
（2）能分析算法所完成的功能、运行结果和时间复杂度。
（3）能根据要求用类C语言编写算法。
二、考核知识点
第一章 绪论
1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。
2.实现关系的两种方法（顺序和链式）及相应的存储结构。
3.算法、算法的特性、如何用类C语言来描述算法。
4.评价算法好坏的主要标准、“0（f（n））"的形式定义、了解算法的渐近时间复杂度、语句的频度、最坏情况时间复杂度和平均时间复杂度的概念。
第二章 线性表
1.线性表的定义和操作。
2.顺序存储线性表的实现和运算。
3.链式存储线性表（静态链表和动态链表），带有附加表头结点和不带附加表头结点的单链表、循环链表和双向链 表的实现和查找对插入、删除等基本操作
4.链表应用举例一一一元多项式的表示及相加的算法。
第三章 栈和队列
1.栈和队列的定义及其存储结构、循环队列。
2.栈和队列的主要运算.
3.栈的应用举例一一表达式求值的过程。
第四章 串
1.串的定义、空串、空格串。
2.串的基本操作。
3.串的顺序存储结构及在顺序存储结构下基本操作的实现。
第五章 数组和广义表
1.数组的顺序存储结构。
2.二维数组的按行存储及按列存储和计算数组元素的地址计算公式。
3.矩阵的压缩存储、特殊矩阵的表示。
4.广义表的定义和操作（HEAD和TAIL）。
第六章 树和二叉树
1.树的定义和术语。
2.树的存储表示法——孩子表示法、双亲表示法、孩子兄弟表示法。
3.树和森林转换为二叉树的方法。
4.二叉树（完全；二叉树、满二叉树）的定义和性质（结论）、二叉树的存储结构——顺序表示法和二叉链表表示法。
5.二叉树遍历的递归算法。
6.树的路径长度、树的带权路径长度、Huffman树的构造方法。
第七章 图
1.图的定义。
2.图的基本术语。
（1）图及无向图、有向图、网、子图、连通图、强连通图。
（2）顶点的度、入度、出度。
（3）顶点间路径、路径长度、环
3.图的存储结构
（l）邻接矩阵
（2）邻接表（含逆邻接表）
4.遍历图
（l）深度优先插索遍历图的算法及其时间复杂度。
（2）广度优先插索遍历图的算法及其时间复杂度。
5.生成树
（1）生成树、最小生成树的概念。
（2）最小生成树的算法（Prim算法和Kruskai算法）及其时间复杂度。
6.最短路径
（l）求源点到其余各顶点间的最短路径
DijKstra算法的思想及其时间复杂度。
（2）求各顶点对间的最短路径。
Floyed算法的思想及其时间复杂度。
第九章 查找
1.查找的定义关键字、查找、平均查找长度。
2.静态查找表的查找算法及其效率（最坏和平均长度）。
（l）顺序查找
（2）折半查找
（3）分块查找（索引顺序表的查找）
3.动态查找表
（1）二叉排序树的查找算法及其效率。
（2）平衡二叉树（AVid树）的定义。
4.哈希表
（l）哈希法的特点。
（2）哈希函数和散列地址。
（3）构造哈希函数的几种方法。直接定址法、除留余数法、平方取中法、折叠法、数字分析法。
（4）处理冲突的方法。
冲突的处理，开放定址法和链地址法，开放定址法又分为线性探测再散列、二次探测再散列和伪随机探测再散列。
第十章 内部排序
1.排序的目的、分类和排序方法的稳定性的定义。
2.插入排序。
（1）直接插入排序的算法。
（2）折半插入排序的算法。
3.希尔排序的思想。
4.选择排序的思想。
5.堆排序的方法、堆的定义、初始堆的求取。
6.起泡排序的思想。
7.快速排序的算法、快速排序的最坏情况时间复杂度的分析。
8.归并排序的思想、影响归并排序稳定性的因素。
9.基数排序的思想及特点。
三、考试要求（包括考试时间、总分、考试方式、题型、分数比例等）
考试时间3小时，总分150分，考试方式为闭卷考试，试卷题型及分数比例为：
选择题和判断题共40分；简答题60分； 算法设计题：50分；
四、主要参考书目
1、《数据结构》（C语言版），严蔚敏、吴伟民，清华大学出版社，2007年；
2、《数据结构题集》（C语言版），严蔚敏、吴伟民， 清华大学出版社 2003年；
3、《C语言程序设计》（第二版），谭浩强， 清华大学出版社 2005年；
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
文章搜索
您现在的位置： 
