电子科技大学“软件基础（数据结构部分）”2007年工程硕士入学考试大纲

资料发布小组

考试科目：软件基础（数据结构部分）
考试书目 作者 出版社 出版时间
《数据机构（第二版）》 严蔚敏等 清华大学出版社
大纲内容
第一章、绪论
1.基本概念和术语：数据、数据元素、数据对象、数据结构及其形式化描述ds＝（ｄ，ｒ）、数据类型、四种基本数据结构；
2.算法描述；
3.算法的基本特性及“好”算法的特征；
4.简单时间复杂度的分析。

第二章、线性表
1.线性表的逻辑结构及基本操作；
2.顺序存储结构及其特点；
3.单链表、循环链表、双向链表及其各自的特点。

第三章、栈和队列
1.栈的特点及基本操作；
2.栈的应用（读写递归算法时注意事项）；
3.队列的特点及基本操作；
4.循环队列：队空、队满的判定。

第五章、数组和广义表
1.数组及其操作；数组元素的存放方式及存储地址的计算；
2.数组元素的存放方式及存储地址的计算；
3.广义表的定义、性质及操作。

第六章、树和二叉树
1.树和二叉树的基本概念；
2.二叉树的性质；
3.二叉树的存储结构；
4.二叉树的遍历；
5.树、森林和二叉树之间的转换；
6.哈夫曼树的构造。

第七章、图
1.图的基本术语；
2.图的存储结构：邻接矩阵、邻接表；
3.一定存储结构下图的遍历；
4.图的典型应用：最小生成树、拓扑排序。

第九章、查找
1.基本术语；
2.顺序表查找：顺序、折半、分块；
3.二叉排序树及其构造；
4.hash表的构造。

第十章、内部排序
1.基本概念：排序；排序方法的稳定性；
2.排序方法的基本思想；
3.会模拟排序过程；
4.能够读懂排序算法。