复旦大学在职工程硕士 《数据结构》考试大纲

《复旦大学在职工程硕士 《数据结构》考试大纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、复旦大学在职工程硕士《数据结构》考试大纲一、考试的基本要求用计算机解决一个新问题，就要将反映问题的数据存入计算机，并要设计能解决问题的算法。数据结构学科就是研究计算机如何存储各种数据及数据之间的关系，以及对数据作基本处理的算法。要求考生比较系统地理解数据结构的基本概念和基本理论，掌握常用数据结构及其基本算法，具有综合运用数据结构知识解决问题的能力。二、考试方法和考试时间考试采用闭卷、笔试形式，考试时间为180分钟。三、对编程语言的要求试题中所有的算法，要求用C或C++语言描述。四、考试内容和考试要求1、基本概念考试内容数据结构的基本概念；渐近算法分析方法

2、。考试要求1)数据结构包含数据元素集合和数据元素之间关系的集合。2)理解算法与数据结构之间的关系。3)掌握渐近算法分析方法：最佳、最差和平均情况，大O表示法。2、线性表和字符串考试内容线性表的特点，线性表的顺序实现和链式实现，线性表的应用；字符串基本操作的实现算法，字符串匹配算法，及字符串的简单应用。考试要求1）理解线性表的结构和特点，掌握线性表上基本操作的实现算法。2）掌握顺序存储线性表的结构，基本操作的实现算法。3）掌握链接存储线性表的结构。单链表、双向链表和循环链表的存储结构和特点，基本操作的实现算法。4）理解字符串的存储结构，字符串基本操作的实现

3、算法。5）掌握字符串简单匹配算法；理解字符串KMP匹配算法。6）具有用用线性表、字符串解决实际问题的能力。31、栈和队列考试内容栈和队列的基本运算及其应用。考试要求1)理解栈的定义和结构的特点，掌握其存储方式(顺序存储与链接存储)和基本操作的实现算法。2)理解队列的结构和特点，掌握其存储方式(顺序存储与链接存储)和基本操作的实现算法。3)具有用栈和队列结构解决实际问题的能力。2、递归考试内容递归的基本概念，递归的简单应用。考试要求1)理解递归的基本概念和实现原理，掌握用递归的思想描述问题和构造算法的方法。2)掌握汉诺塔、迷宫等问题的递归解法。3)掌握用栈

4、实现递归问题的非递归解法。3、树和二叉树考试内容树和二叉树。考试要求1)理解树的结构和定义，掌握树的主要概念。2)掌握二叉树的结构，具有运用二叉树解决实际问题的能力。3)掌握二叉树的遍历方法的实现原理，能将二叉树的遍历方法应用于求解二叉树的叶子结点个数、二叉树计数等问题，遍历的非递归实现方法。4)掌握线索化二叉树的结构和基本操作。5)理解树的存储结构，掌握树的遍历等方法的实现。6)理解霍夫曼编码的基本原理，掌握基于霍夫曼树生成霍夫曼编码的方法。7)掌握堆结构的定义，理解堆的性质、建堆、堆的向下调整、向上调整算法。4、集合和搜索考试内容集合；等价类；静态搜

5、索结构；二叉搜索树；AVL树。考试要求31)理解集合的基本概念，掌握有序链表表示的集合，用树表示的集合基本算法。2)掌握顺序存储线性表的顺序搜索、有序顺序存储线性表的二分搜索。3)掌握链接存储线性表的搜索。4)理解二叉搜索树的定义和特点，掌握二叉搜索树插入和删除的算法。5)理解AVL树的定义和特点，掌握AVL树上插入新结点的调整操作的实现原理。1、图考试内容图；最小生成树；最短路径；活动网络。考试要求1)掌握图的基本概念，图的邻接矩阵存储方式和邻接表存储方式。2)掌握图的深度优先搜索和广度优先搜索遍历算法。3)掌握Kluskal和Prim生成最小生成树的

6、算法。4)掌握Dijkstra求单源最短路径的方法。5)掌握AOV活动网络的拓扑排序算法，求AOE活动网络关键路径的算法。2、排序考试内容插入排序；交换排序；选择排序；归并排序；基数排序。考试要求理解各种排序方法的算法实现，掌握各种排序算法的时间复杂性，各种排序算法的特性。3、索引结构与散列考试内容静态索引结构、动态索引结构，散列。考试要求1)理解线性索引结构、倒排表、静态搜索树的结构和特点。2)理解B树的结构，掌握B树的搜索、插入、删除操作的实现算法。3)理解散列的实现原理，掌握实现散列的关键技术。3