东南大学软件工程硕士(单证)入学考试
《数据结构》考试大纲
一、考试目的和要求
本课程考试的目的主要是考查考生对《数据结构》基础知识,基本理论和基本技能的掌握程度以及综合运用所学知识分析和解决问题的能力。要求考生掌握常用基本数据结构(链表、栈、队列、串、数组、树、图等)的概念和逻辑结构及其不同的实现方法,并能针对具体问题应用高级语言设计和编写算法。
二、考试的基本内容
1、数据结构的基本概念:顺序存储结构和链式存储结构、线性表、栈、队列、串、广义表、树、图等相关概念;算法的基本概念:时间复杂度和空间复杂度、算法时间复杂度的简单分析方法。
2、线性表:顺序表示、链式表示和相应的算法实现。
3、栈、队列:存储结构、基本操作及其算法实现。
4、树:二叉树的性质、存储结构、基本操作及其算法实现,二叉排序树、哈夫曼树的概念及其应用。
5、图:图的存储结构,图的遍历、连通性、生成树、最短路径、拓扑排序、关键路径中所涉及的基本算法。
6、查找:顺序表的查找、有序表的查找、索引顺序表的查找、二叉排序树和平衡二叉树、哈希表的构造及冲突处理方法。
7、内部排序:插入排序、选择排序、冒泡排序、快速排序、堆排序、归并排序、基数排序等排序算法思想和具体排序过程以及各种排序算法的性能比较。
三、主要参考书目
1、《数据结构》(第二版),严蔚敏、吴伟民,清华大学出版社
2、《数据结构》(第二版),殷仁昆等,清华大学出版社