华中科技大学博士研究生入学考试

《数据结构及算法分析》考试大纲

第一部分考试说明

一、考试性质

《数据结构》和《算法分析》是计算机专业的专业基础课。《数据结构及算法分析》是华中科技大学计算机软件与理论专业博士研究生入学考试的一个综合考试科目。

它的评价标准是，高等学校本学科优秀毕业生能达到的及格或及格以上水平，以保证被录取者具有基本的计算机专业理论基础，以利于计算机软件与理论专业各导师择优选拔。

考试对象为参加博士研究生入学考试的应届或非应届硕士毕业生和具有同等学力的在职人员。

二、考试的学科范围

1.数据结构

各种基本类型的数据结构的概念、特征、操作、存储表示和基本应用；各类查找表的查找方法，基本的内排序和外排序方法；文件在外存储器中的表示方法；相关算法的C/C++描述与分析。

2.算法分析

算法的基本概念,分治策略，贪心策略，动态规划，基本检索与周游方法。

三、评价目标

1.数据结构

在考察数据结构的基本概念、基本方法和相关算法的基础上，注重考察综合应用的能力，即分析和解决实际问题的能力。

2.算法分析

掌握一定的算法分析能力,掌握算法设计的基本观点和基本方法, 能正确地选用常用的非数值计算算法, 能站在算法设计策略的高度上设计算法。

具体要求见第二部分“考查要点”。

四、考试形式与试卷结构

1.答卷方式：闭卷，笔试。

2.答题时间：180分钟。

3.考查内容及其考查比例

基本概念、基本方法约占40%～50%；综合应用、算法设计(程序设计)与分析约占60%～50%。

4.试卷结构与考试题型

(1)单项选择题,多项选择题: 约20%

(2)填空题，简答题，应用题:约35%

(3)算法设计题, 算法分析题: 约35%

(4)其它题型:约10%

第二部分 考查要点

一、数据结构(约60%)

1.数据结构和算法C/C++描述。

数据结构、存储结构的概念；数据类型与抽象数据类型；数据结构和算法C++描述。

2.线性表：线性表的定义和基本操作；线性表的抽象数据类型；线性表的顺序存储结构，应用举例；线性表的链式存储结构(单链表,双链表,循环链表),应用举例。

3.栈：栈的定义和基本操作；栈的抽象数据类型；顺序栈，链式栈；栈和递归,算术表达式求值,其它应用。

4.队列：队列的定义和基本操作；队列的抽象数据类型；顺序队列，链式队列；双端队列 ；应用举例。

5.数组和广义表

(1)数组：数组的定义和基本操作；数组的顺序存储结构，数组应用举例；特殊矩阵和稀疏矩阵矩阵的压缩存储。

(2)广义表：广义表的定义和基本操作，广义表的抽象数据类型，广义表的存储结构，广义表运算的实现举例。

6.字符串：字符串的定义和基本操作，字符串的存储结构，字符串操作的实现举例，字符串和模式匹配。

7.树和二叉树

(1)树的基本概念和基本操作,树的抽象数据类型。

(2)二叉树的基本概念和性质，几种特殊二叉树,二叉树的存储结构, 遍历二叉树, 线索二叉树,树和森林。

(3)遍历二叉树：前序遍历,中序遍历, 后序遍历, 层次遍历。

(4)二叉树其它操作实现举例。

(5)线索二叉树的概念和存储结构, 二叉树的线索化, 线索二叉树的遍历。

(6)树的存储结构,树与二叉树之间的转换, 森林与二叉树之间的转换，树和森林的遍历。

(7)带权路径长度, 哈夫曼树(Huffman)和哈夫曼算法, 哈夫曼编码树。

(8)二叉排序树的概念和基本操作,二叉排序树的建立,二叉排序树其它操作

实现举例。

8.图

(1)图的基本概念和基本操作，图的抽象数据类型。

(2)图的存储结构：数组表示法(邻接矩阵)；邻接表，逆邻接表；邻接多重表。

(3)图的遍历：深度优先搜索法, 宽度优先搜索法, 求图的连通分量。

(4)生成树和最小生成树的概念；克鲁斯卡尔(Kruskal)算法,普里姆(Prim)算法。

(5)最短路径，拓扑排序，关键路径。

9.查找

(1)查找的概念。

(2)顺序表的查找：顺序查找,折半查找, 分块查找。

(3)树表的查找: 二叉排序树, 平衡二叉树。

(4)哈希(Hash)表的查找: 哈希表的概念, 哈希函数的构造方法,哈希表的建立和查找, 冲突的处理方法。

10.排序

(1)排序的概念

(2)交换排序：冒泡排序, 快速排序。

(3)插入排序：直接插入排序,2路插入排序，折半插入排序, 希尔排序。

(4)选择排序：直接选择排序,锦标赛排序,堆排序。

(5)归并排序，(6)基数排序

11.文件:文件的基本概念和基本操作；文件的物理结构：顺序文件,索引文件与索引顺序文件, 直接存取文件，链接文件和多重链表文件，倒排文件。

12.外排序：外排序的基本过程,初始归并段的生成,多路平衡归并排序, 最佳归并树。

二、算法分析(约40%)

1.基础知识

算法的定义,它所涉及的内容及在计算机科学中的地位和作用；算法分析的基本概念，基本步骤及其数学工具；基本的数据结构，用SPARKS语言写算法；集合的基本运算----查找和合并；递归程序和消去递归的十三条规则。

2.分治法

分治法的一般方法, 二分检索, 找最大和最小元素, 归并分类, 快速分类,

选择问题, 斯特拉森矩阵乘法。

3.贪心方法

一般方法及背包问题, 带有限期的作业排序, 最优归并模式, 最小生成树, 单源点最短路径。

4.动态规划

一般方法, 多段图, 每对结点之间的最短距离, 最优二分检索树, 0/1背包问题, 可靠性设计, 货郎担问题, 流水线调度问题。

5.周游与检索

基本概念与一般方法, 代码优化, 双连通分图和深度优先检索。