附件1
《数据结构》研究生入学考试大纲
2004.10
总体要求：
“ 熟练掌握C语言和类c语言； “ 止确理解本课程屮的术语；
“ 熟练掌握顺序表、链表、栈、队列、树、图等数据结构的特点和常用操作算法（包括时I'可 复
杂度的分析）；
“ 熟练掌握经典的查找算法（包括吋间复杂度的分析）、排序算法（包括时问复杂度和空间复杂
度的分析）；
“ 对典型的应用问题能熟练设计出数据结构并用算法加以描述和进行吋间复杂度的分析。
具体内容：
1、 绪论
■数据结构研究对彖及术语 抽象数据类型的表示与实现 ■算法与算法分析
2、 线性表
-线性表的逻辑结构 线性表的顺序存储结构 线性表的链式存储结构
■-元多项式的表示和相加
3、 栈和队列
■栈
4、 串
栈的应用 栈与递归过程 队列
■串及其操作 串的存储结构 串基本操作的实现
5、 数组和广义表
串操作应用举例
■数组的定义和运算 数组的顺序存储结构
■广义表的定义
矩阵的压缩存储
广义表的存储结构
6、 树和二叉树
■树的定义和基本操作 二叉树
■树和森林 赫夫曼树及其应用
7、 图
遍历二叉树和线索二叉树
■图的定义和术语 图的存储结构 图的遍历 图的连通性问题
■有向无环图及其应用 最短路径
8、 查找
-静态查找表 动态查找表 哈希表
9、内部排序
■插入排序交换排序 选择排序 归并排序 基数排序
各部分的重点、深度、广度：
/绪论：重点掌握数据、数据结构、逻辑结构、物理结构等概念和术语及简单算法的时间复 杂度的分析。
/线性表：重点掌握对顺序、链式存储的线性表的插入、删除等基本操作的算法。
/栈和队列：重点掌握栈和队列的特点，对它们在不同存储结构卜?的基本操作的算法，简单 递归算法的设计。
/串：重点掌握串的基本概念和动态存储结构。
/数组和广义表：重点掌握多维数组的顺序存储、矩阵的压缩存储和广义表的操作与存储结 构。 /树和二叉树：重点掌握二叉树的性质，存储结构和遍历算法，森林与二叉树的转换，赫夫 曼树及其应用。
/图：重点掌握图的存储结构，遍历算法及图的应用（如拓扑排序、关键路径、最短路径等）。 /查找：重点掌握折半查找算法，趙立二叉排序树、平衡二叉树的算法，B■树和B+树的特点 及应用、哈希表的构造方法。
/内部排序：重点掌握插序排序、交换排序、选择排序和归并排序的典型算法。
参考书：
⑴ 严蔚敏,吴伟民.数据结构（C语言版）.北京：清华大学出版社,1997
（2）严蔚敬，吴伟民.数据结构题集（C语言版）.北京：清华大学出版社，1999
数据结构研究生入学考试大纲.doc
