3371数据结构及算法分析.doc

华中科技大学博士研究生入学考试 《数据结构及算法分析》考试大纲 第一部分 考试说明 一、考试性质 《数据结构》和《算法分析》是计算机专业的专业基础课。《数据结构及算法分析》是华中科技大学计算机软件与理论专业博士研究生入学考试的一个综合考试科目。 它的评价标准是，高等学校本学科优秀毕业生能达到的及格或及格以上水平，以保证被录取者具有基本的计算机专业理论基础，以利于计算机软件与理论专业各导师择优选拔。 考试对象为参加博士研究生入学考试的应届或非应届硕士毕业生和具有同等学力的在职人员。 二、考试的学科范围 1.数据结构 各种基本类型的数据结构的概念、特征、操作、存储表示和基本应用；各类查找表的查找方法，基本的内排序和外排序方法；文件在外存储器中的表示方法；相关算法的C/C++描述与分析。 2.算法分析 算法的基本概念,分治策略，贪心策略，动态规划，基本检索与周游方法。 三、评价目标 1.数据结构 在考察数据结构的基本概念、基本方法和相关算法的基础上，注重考察综合应用的能力，即分析和解决实际问题的能力。 2.算法分析 掌握一定的算法分析能力, 掌握算法设计的基本观点和基本方法, 能正确地选用常用的非数值计算算法, 能站在算法设计策略的高度上设计算法。 具体要求见第二部分“考查要点”。 四、考试形式与试卷结构 1.答卷方式：闭卷，笔试。 2.答题时间：180分钟。 3.考查内容及其考查比例 基本概念、基本方法约占40%～50%；综合应用、算法设计(程序设计)与分析约占60%～50%。 4.试卷结构与考试题型 (1)单项选择题,多项选择题: 约20% (2)填空题，简答题，应用题: 约35% (3)算法设计题, 算法分析题: 约35% (4)其它题型: 约10% 五、参考书目 1.严蔚敏等，数据结构(C语言版)，清华大学出版社 2.余祥宣 崔国华 邹海明，计算机算法基础(前五章)，华中理工大学出版 社,2000 3.Horowitz,S Sahni,Fundamentals of Computer Algorithms.New York: Computer Science Press,1978 第二部分 考查要点 一、数据结构(约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)最短路径，拓扑排序，关键