2017年硕士研究生入学考试自命题科目考试大纲

科目代码：852科目名称：数据结构

一.考试要求

数据结构主要考查学生对数据结构的基本概念、基本原理和基本方法的掌握；对数据的逻辑结构、存储结构及基本操作的掌握；运用数据结构基本原理和方法进行问题的分析与求解，设计与实现算法的能力。

二、考试内容

1．数据结构概述
数据结构的基本概念和术语，抽象数据类型的表示，算法时空复杂性的分析和度量方法。
2．线性表
线性表的概念，线性表的顺序表示和实现，线性表的链式表示和实现以及相应算法。
3．栈和队列
栈的定义、特点及栈的表示和实现，队列的定义、特点、队列的表示和实现，桟和队列的基本运算，桟和队列的应用。
4．串
串的基本概念、存储结构、基本运算，字符串的模式匹配算法。
5．数组和广义表
数组的逻辑结构定义和存储方法，特殊矩阵和稀疏矩阵的压缩存储，广义表的定义和存储结构。
6．树与二叉树
树、二叉树和森林的定义、基本术语和存储结构，树、二叉树以及森林的遍历，线索二叉树，森林与二叉树的转换，赫夫曼树和赫夫曼编码。
7．图
图的基本概念和图的存储表示，图的深度、广度优先搜索，图的连通性问题，有向无环图及其应用，最短路径。
8．查找
查找的基本概念，顺序查找、折半查找、分块查找，二叉排序树的表示、搜索、插入、删除算法及其性能分析方法，平衡二叉树的构造、性能分析方法，B-树、B+树的搜索和构造方法；散列法，包括散列函数的构造、解决冲突的方法。
9．排序
排序的基本概念，插入排序、交换排序、选择排序、归并排序、基数排序等排序方法及其性能分析方法。

三、考试形式

考试形式为闭卷、笔试，考试时间为3小时，满分150分。

题型包括：选择题、简答题、编写算法题、综合题等。

四、参考书目

1．《数据结构》（c语言版）．严蔚敏等编．清华大学出版社，2011。