考试大纲与应试指导 第 页（共 5 页） 1 2018 年 研究生入学考试 数据结构 考试大纲 【考查目标】 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够设计简单的算法，并对其进行基本的时间复杂度与空间复杂度的分析。 3.能够选择合适的数据结构和 算 法进行问题求解，具备采用 C 或 C+或 JAVA 语言设计与实现算法的能力。 (一 ) 绪论 什么是数据结构 ； 基本概念和术语，数据结构分类； 抽象数据类型的表示和实现；逻辑结构、存储结构异同； 算法和算法分析包括：算法、算法设计的要求、算法效率的度量、算法的存储空间需求 （二 ） 线性表 线性表的类型定义 ，掌握基本概念。 线性表的顺序表示和实现 线性表的链式表示和实现 线性链表、循环链表、双向链表 (三 ) 栈和队列 栈和队列 的基本概念和基本操作 栈 抽象数据类型栈的定义 栈的表示和实现 栈的应用举例 队列 抽象数据类型队列的定义 链队列 队列的链式表示和实现 循环队列 队列的顺序表示和实现顺序表示和实现 （四） 串 串类型的定义 串的表示和实现 定长顺序存储表示 堆分配存储表示 考试大纲与应试指导 第 页（共 5 页） 2 串的块链存储表示 （五） 数组和广义表 数组的定义 数组的顺序表示和实现 矩阵的压缩存储 特殊矩阵 稀疏矩阵及三元组表示 广义表的定义及其存储结构 （六） 树和二叉树 掌握数和二叉树的基本概念和基本操作 树的定义和基本术语 二叉树 二叉树的定义 二叉树的性质 二叉树的存储结构 遍历二叉树 树和森林 树的存储结构 森林与二叉树的转换 树和森林的遍历 赫夫曼树及其应用 （七） 图 图的定义和术语 图的存储结构 数组表示法 邻接表 十字链表 邻接多重表 图的遍历 深度优先搜索 广度优先搜索 图的连通性问题 无向图的连通分量和生成树 最小生成树 有向无环图及其应用 拓扑排序 关键路径 最短路径 （八） 查找 考试大纲与应试指导 第 页（共 5 页） 3 静态查找表 顺序表的查找 有序表的查找 索引顺序表的查找 动态查找表 二叉排序表和平衡二叉树 B_树和 B+树 哈希表 （九） 内部排序 了解、掌握各种排序方法的大致思路 插入排序 直接插入排序 希尔排序 交换排序 冒泡排序 快速排序 选择排序 简单选择排序 堆排序 归并排序 基数排序 参考书： 1 严蔚敏 .数据结构（ C 语言版），清华大学出版社 . 2 严蔚敏 .数据结构题集（ C 语言版），清华大学出版社 3 王红梅 .数据结构（ C版）， .清华大学出版社 4 叶核亚 数据结构（ java 版），电子工业出版社 考试大纲与应试指导 第 页（共 5 页） 4 2018 年 研究生入学考试 C 语言 考试大纲 C语言程序设计的考试内容 一、 C 语言程序的结构 1 程序的构成， main 函数和其他函数。 2 头文件、数据说明、函数的开始和结束标志以及程序中的注释。 3 源程序的书写格式。 4 C 语言的风格。 二、 数据类型及其运算 1 数据类型（基本类型、构造类型、指针类型、无值类型）及其定义方法。 2 运算符的种类、运算优先级和结合性。 3 不同类型数据间的转换与运算。 4 表达式类型（赋值表达式、算术表达式、关系表达式、逻辑表达式、条件表达式、逗号表达式）和求值规则。 三、 基本语句 1 表达式语句、空语句、复合语句。 2 输入输出函数的调用，正确输入数据并能正确设计输出格式。 四、 选择结构程序设计 1 用 if 语句实现选择结构。 2 用 switch 语句实现多分支选择结构。 3 选择结构的嵌套。 五、 循环结构程序设计 1 for 循环结构 。 2 while 和 do-while 循环结构。 3 continue 语句和 break 语句。 4 循环的嵌套。 六、 数组的定义和引用 1 一维数组和二维数组的定义、初始化和数组元素的引用。 2 字符串和字符数组。 考试大纲与应试指导 第 页（共 5 页） 5 七、 函数 1 库函数的正确调用。 2 函数的定义方法。 3 函数的类型和返回值。 4 形式参数与实在参数，参数值的传递。 5 函数的正确调用，嵌套调用，递归调用。 6 局部变量和全局变量。 7 变量的存储类别 (自动、静态、寄存器、外部 )，变量的作用域和生存期。 八、 编译预处理 （一般了解） 九、 指针 1 地址与指针变量的概念，地址运算符与间址运算符。 2 一维、二维数组和字符串的地址以及指向变量、数组、字符串、函数、结构体的指针变量的定义。通过指针引用以上各类型数据。 3 用指针作函数参数。 4 返回地址值的函数。 5 指针数组，指向指针的指针。 十、 结构体 （其余内容一般了解） 1 结构体类型数据的定义和成员的引用。 2 结构体应用。 3 了解共用体。 十一、 位运算 （ 其余内容 一般了解） 1 掌握逻辑运算法则。 2 熟练 进行 ： 与、或、非、异或 的 逻辑运算。 十二、 文件操作 （ 其余内容 一般了解） 1 文件的打开关闭，并能在指定路径下创建一个 可读写的 新文件 2 了解文本文件、二进制文件及读写操作 参考教材：谭浩强， C 程序设计（ 第二版以上版本，含第二版 ），清华大学出版社