2015年华中科技大学考博：软件基础考试大纲
第一部分：考试说明
考试范围：数据结构与数据库系统基础。
考试形式与试卷结构：
(一) 答卷形式：闭卷，笔试;所列题目均为必答题。
(二) 答题时间：180分钟。
(三) 各部分考察比例：
1) 数据结构部分：40%
2) 数据库部分：60%
(四) 题型比例
填空题：约30%
简答或程序分析题：约30%
程序、算法设计或综述性题目：40%
第二部分：考察要点
A. 数据结构部分
一、 基本概念：
1. 熟悉数据、数据元素等名词术语的基本概念。了解抽象数
据类型的定义、表示和实现方法，熟悉类C语言的书写规范。
2. 了解计算语句频度和估算时间算法复杂度的方法
二、 线性表、栈、队列
1. 理解线性表的逻辑结构，掌握线性表在顺序存储及链表结构结构上实现基本操作的算法。
2. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
3. 掌握栈类型的两种实现方法，即两种存储结构表示时的基
本操作实现算法。
4. 了解递归算法执行过程中栈的状态变化过程。
5. 了解递归算法到非递归算法的机械转化过程。
三、 串
1. 掌握串的七种基本操作的定义，并能利用这些基本操作实现串的其他各种操作的方法。
2. 了解串的定长顺序存储结构上实现串的各种操作的方法。
3. 了解串的堆存储结构以及在其上实现串操作的基本方法。
4. 了解串匹配的KMP算法。
5. 了解串操作的应用方法和特点。
四、 数组与广义表
1. 了解数组的两种存储表示方法，并掌握数组在以行为主的
存储结构中的地址计算方法。
2. 了解特殊矩阵进行压缩存储时的下标变换公式。
3. 了解稀疏矩阵的两种压缩存储方法的特点和适用范围。
4. 了解广义表的结构特点及其存储表示方法。
五、 树和二叉树
1. 熟练掌握二叉树的结构特性，了解相应的证明方法。
2. 熟悉二叉树的各种存储结构的特点及适用范围。
3. 熟悉遍历二叉树的基本概念、性质与实现方法。
4. 了解树的存储结构及其特点，理解树和森林与二叉树的转
换方法。
5. 熟悉最优二叉树和哈夫曼编码。
六、 图
1. 理解图的各种存储结构及其构造算法。
2. 掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先
搜索的两种形式(递归和非递归)和广度优先搜索的算法。
七、 查找与排序
1. 掌握顺序表和有序表的查找方法。
2. 了解静态查找树的构造方法和查找算法，理解静态查找树和
折半查找的关系。
3. 掌握二叉排序树的构造和查找方法。
4. 了解二叉平衡树的维护平衡方法。
5. 了解哈希表的构造方法，理解哈希表与其他结构的表的实质
性的差别。
6.了解描述查找过程的判定树的构造方法，以及按定义计算各
种查找方法在等概率情况下查找成功时的平均查找长度。
7. 理解排序的定义和各种排序方法的特点。
8. 了解各种方法的排序过程及其依据的原则。
9. 了解各种排序方法的时间复杂度的分析方法。
10. 了解“表排序”和“地址排序”的过程及其适用场合。
11. 理解外部排序的两个阶段和第二阶段——归并的过程。
12. 了解外部排序过程中所需进行外存读/写次数计算方法。