《复旦大学在职工程硕士 《数据结构》考试大纲171.doc》由会员分享，可在线阅读，更多相关《复旦大学在职工程硕士 《数据结构》考试大纲171.doc（6页珍藏版）》请在金锄头文库上搜索。
1、复旦大学在职工程硕士 数据结构考试大纲171读万卷书，行万里路刘彝 复旦大学在职工程硕士 数据结构考试大纲一、考试的基本要求用计算机解决一个新问题，就要将反映问题的数据存入计算机，并要设计能解决问题的算法数据结构学科就是研究计算机如何存储各种数据及数据之间的关系，以及对数据作基本处理的算法要求考生比较系统地理解数据结构的基本概念和基本理论，掌握常用数据结构及其基本算法，具有综合运用数据结构知识解决问题的能力二、考试方法和考试时间考试采用闭卷、笔试形式，考试时间为180分钟三、对编程语言的要求试题中所有的算法，要求用C或C+语言描述四、考试内容和考试要求1、 基本概念考试内容数据结构的基本概念；
2、渐近算法分析方法考试要求1) 数据结构包含数据元素集合和数据元素之间关系的集合2) 理解算法与数据结构之间的关系3) 掌握渐近算法分析方法：最佳、最差和平均情况，大O表示法2、 线性表和字符串考试内容线性表的特点，线性表的顺序实现和链式实现，线性表的应用；字符串基本操作的实现算法，字符串匹配算法，及字符串的简单应用考试要求1） 理解线性表的结构和特点，掌握线性表上基本操作的实现算法2） 掌握顺序存储线性表的结构，基本操作的实现算法3） 掌握链接存储线性表的结构单链表、双向链表和循环链表的存储结构和特点，基本操作的实现算法4） 理解字符串的存储结构，字符串基本操作的实现算法5） 掌握字符串简单匹
3、配算法；理解字符串KMP匹配算法6） 具有用用线性表、字符串解决实际问题的能力3、 栈和队列考试内容栈和队列的基本运算及其应用考试要求1) 理解栈的定义和结构的特点，掌握其存储方式(顺序存储与链接存储)和基本操作的实现算法2) 理解队列的结构和特点，掌握其存储方式(顺序存储与链接存储)和基本操作的实现算法3) 具有用栈和队列结构解决实际问题的能力4、 递归考试内容递归的基本概念，递归的简单应用考试要求1) 理解递归的基本概念和实现原理，掌握用递归的思想描述问题和构造算法的方法2) 掌握汉诺塔、迷宫等问题的递归解法3) 掌握用栈实现递归问题的非递归解法5、 树和二叉树考试内容树和二叉树考试要求1
4、) 理解树的结构和定义，掌握树的主要概念2) 掌握二叉树的结构，具有运用二叉树解决实际问题的能力3) 掌握二叉树的遍历方法的实现原理，能将二叉树的遍历方法应用于求解二叉树的叶子结点个数、二叉树计数等问题，遍历的非递归实现方法4) 掌握线索化二叉树的结构和基本操作5) 理解树的存储结构，掌握树的遍历等方法的实现6) 理解霍夫曼编码的基本原理，掌握基于霍夫曼树生成霍夫曼编码的方法7) 掌握堆结构的定义，理解堆的性质、建堆、堆的向下调整、向上调整算法6、 集合和搜索考试内容集合；等价类；静态搜索结构；二叉搜索树；AVL树考试要求1) 理解集合的基本概念，掌握有序链表表示的集合，用树表示的集合基本算法
5、2) 掌握顺序存储线性表的顺序搜索、有序顺序存储线性表的二分搜索3) 掌握链接存储线性表的搜索4) 理解二叉搜索树的定义和特点，掌握二叉搜索树插入和删除的算法5) 理解AVL树的定义和特点，掌握AVL树上插入新结点的调整操作的实现原理7、 图考试内容图；最小生成树；最短路径；活动网络考试要求1) 掌握图的基本概念，图的邻接矩阵存储方式和邻接表存储方式2) 掌握图的深度优先搜索和广度优先搜索遍历算法3) 掌握Kluskal和Prim生成最小生成树的算法4) 掌握Dijkstra求单源最短路径的方法5) 掌握AOV活动网络的拓扑排序算法，求AOE活动网络关键路径的算法8、 排序考试内容插入排序；交换排序；选择排序；归并排序；基数排序考试要求理解各种排序方法的算法实现，掌握各种排序算法的时间复杂性，各种排序算法的特性9、 索引结构与散列考试内容静态索引结构、动态索引结构，散列考试要求1) 理解线性索引结构、倒排表、静态搜索树的结构和特点2) 理解B树的结构，掌握B树的搜索、插入、删除操作的实现算法3) 理解散列的实现原理，掌握实现散列的关键技术1读万卷书，行万里路刘彝
