数据结构部分（40%）：.doc

《数据结构部分（40%）：.doc》由会员分享，可在线阅读，更多相关《数据结构部分（40%）：.doc（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、华中科技大学博士研究生入学考试软件基础考试大纲第一部分：考试说明考试范围：数据结构与数据库系统基础。考试形式与试卷结构：（一）答卷形式：闭卷，笔试；所列题目均为必答题。（二）答题时间：180 分钟。（三）各部分考察比例：1） 数据结构部分：40%2） 数据库部分：60%（四）题型比例填空题：约 30%简答或程序分析题：约 30%程序、算法设计或综述性题目：40%第二部分：考察要点A. 数据结构部分一、 基本概念：1. 熟悉数据、数据元素等名词术语的基本概念。了解抽象数据类型的定义、表示和实现方法， 熟悉类 C语言的书写 规范。2. 了解计算语句频度和估算时间算法复杂度的方法二、 线性表、栈、队

2、列1. 理解线性表的逻辑结构，掌握线性表在顺序存储及链表结构结构上实现基本操作的算法。2. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。3. 掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法。4. 了解递归算法执行过程中栈的状态变化过程。5. 了解递归算法到非递归算法的机械转化过程。三、 串1. 掌握串的七种基本操作的定义，并能利用这些基本操作实现串的其他各种操作的方法。2. 了解串的定长顺序存储结构上实现串的各种操作的方法。3. 了解串的堆存储结构以及在其上实现串操作的基本方法。4. 了解串匹配的 KMP 算法。5. 了解串操作的应用方法和特点。

3、四、 数组与广义表1. 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2. 了解特殊矩阵进行压缩存储时的下标变换公式。3. 了解稀疏矩阵的两种压缩存储方法的特点和适用范围。4. 了解广义表的结构特点及其存储表示方法。五、 树和二叉树1 熟练掌握二叉树的结构特性，了解相应的证明方法。2 熟悉二叉树的各种存储结构的特点及适用范围。3 熟悉遍历二叉树的基本概念、性质与实现方法。 4 了解树的存储结构及其特点，理解树和森林与二叉树的转换方法。5 熟悉最优二叉树和哈夫曼编码。六、 图1. 理解图的各种存储结构及其构造算法。2. 掌握图的两种搜索路径的遍历：遍历的逻辑定义、深

4、度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。七、 查找与排序1. 掌握顺序表和有序表的查找方法。2. 了解静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系。3. 掌握二叉排序树的构造和查找方法。4. 了解二叉平衡树的维护平衡方法。5. 了解哈希表的构造方法，理解哈希表与其他结构的表的实质性的差别。6. 了解描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。7. 理解排序的定义和各种排序方法的特点。8. 了解各种方法的排序过程及其依据的原则。9. 了解各种排序方法的时间复杂度的分析方法。10. 了解“表排序”和“地址排序

5、”的过程及其适用场合。11. 理解外部排序的两个阶段和第二阶段归并的过程。12. 了解外部排序过程中所需进行外存读/写次数计算方法。B. 数据库部分一、 绪论1、 了解数据管理技术的发展过程2、 掌握数据库管理系统的概念和功能3、 掌握数据库系统的特点4、 掌握数据库的三级模式结构5、 掌握数据库的两级映像功能及数据独立性6、 掌握概念模型与数据模型的区别7、 掌握数据模型的组成要素和典型的数据模型二、 关系数据库1、 掌握关系模型的组成2、 掌握关系的完整性约束3、 掌握关系的基本术语和形式化定义4、 掌握关系代数三、 SQL 语言1、 掌握数据定义语言 2、 重点掌握数据查询语言3、 掌握

6、数据更新语言4、 掌握视图的定义与使用5、 掌握数据控制语言四、 关系数据库理论1、 掌握函数依赖概念2、 掌握部分函数依赖和传递函数依赖的概念3、 理解规范化程度不高的范式可能存在的问题4、 掌握 1NF、2NF、3NF、BCNF、4NF 等范式的定义五、 关系数据库设计1、 掌握数据库设计的步骤及各阶段的任务2、 熟练掌握概念结构设计方法和 ER 图设计方法3、 熟练掌握将 ER 图转换成关系模式的方法4、 了解数据库的物理设计、数据库实施与维护六、 数据库安全保护1、 理解数据库安全的定义、安全性的一般控制方法2、 掌握完整性控制3、 掌握并发控制与封锁4、 掌握共享锁和排他锁的特点5、 掌握三级封锁协议6、 了解数据库的恢复