七、图
【考试内容】
1、 图的定义及术语。
2、 图的存储结构(邻接矩阵、邻接表)。
3、 图的遍历(深度优先、广度优先)。
4、 图的最小生成树算法。
5、 单源点最短路径算法——Dijkstar算法。
6、 拓扑排序、关键路径。
【考试要求】
1、领会
(1)图的逻辑结构特征。
(2)图的常用术语及含义。
(3)图的存储结构及其特点。
(4)图的遍历方法。
(5)拓扑排序、关键路径的相关概念及算法思想。
2、简单应用
(1)图的两种存储结构、特点及适用范围。
(4)无向连通网求解最小生成树的算法(Prime算法和Krurskal算法)思想。
3、综合应用
(1)图的两种遍历算法,理解其执行过程。
(2)根据不同的遍历方法,应能得出其相应的结点访问次序。
(3)根据Dijkstar算法求解图的最短路径。
八、排序
【考试内容】
1、排序的基本概念
2、插入排序(直接插入排序、折半插入排序)
3、起泡排序
4、简单选择排序
5、希尔排序
6、快速排序
7、堆排序
8、二路归并排序
9、基数排序
10、各种内部排序算法的比较
11、内部排序算法的应用
【考试要求】
1、领会
(1)排序、关键码、稳定排序等术语的含义。
2、简单应用
(1)各种内部排序算法的算法思想。
3、综合应用
(1)各种内部排序算法的特点、应用范围、时空复杂度分析、比较应用等。
九、查找
【考试内容】
1、查找的基本概念
2、顺序查找法
3、折半查找法
4、二叉搜索树、AVL树
5、散列(Hash)表及其查找
6、查找算法的分析及应用
【考试要求】
1、 领会
(1)查找、平均查找长度等基本概念的含义。
(2)二叉搜索树、AVL树的概念;
(3)散列的含义。
2、 简单应用
(1)顺序查找、折半查找的算法思想、应用特点。
(2)二叉搜索树、AVL树的特点以及平均搜索长度的分析。
(3)常用的散列表的构造方法、冲突处理的方法。
3、 综合应用
(1)二叉搜索树的创建、插入、删除算法。
(2)AVL平衡化旋转的方法。
Ⅱ. 相关说明
本大纲在【考试要求】中,按照识记、领会、简单运用和综合运用等四个层次规定学生通过学习应该达到的能力层次要求。四个能力层次是递进等级关系,各能力层次的含义是:
1、【识记】能够了解有关的名词、概念、知识的含义,并能正确认识和表述、选择和判断。
2、【领会】在识记的基础上,能够比较全面地把握基本概念、基本事实、基本理论模型、基本方法,能把握有关概念、事实、理论模型、分析方法之间的区别和联系。并能根据考核的不同要求,做出正确的解释、说明和论述。
3、【简单运用】在领会的基础上,能够运用本课程中规定的少量的知识点,分析和解释有关的一般的应用问题。例如,简单的算法设计和时间性能分析。
4、【综合运用】指在简单运用的基础上,能够综合运用所学习过的多个知识点,分析和解决较复杂的应用问题,例如,设计较复杂的算法。
Ⅲ. 参考书
1、《数据结构》(C语言版),严蔚敏 吴伟民 编著,清华大学出版社,2007年版。
2、《数据结构题集》,严蔚敏 吴伟民 著,清华大学出版社,2007年版。
3、《数据结构(用面向对象方法与C++语言描述)》(第二版),殷人昆 主编,清华大学出版社,2007年版。
Ⅳ. 试卷结构
1、考试题型及比例分布
(1)单项选择题(约30%)
(3)简答及应用(约40%)
(4)算法设计(约30%)
其他可能出现的题型:填空题(约15%),判断题(约10%)。
2、考试内容及比例分布
(1)数据结构基本概念、算法及算法分析方法(约5%)
(2)线性表(约15%)
(3)栈和队列(约10%)
(4)串(约5%)
(5)数组与广义表(约5%)
(6)树和二叉树(约20%)
(7)图(约10%)
(8)排序(约15%)
(9)查找(约15%)
原标题:地理与信息工程学院2022硕士研招初试复试考试大纲
文章来源:https://xgxy.cug.edu.cn/info/1055/3809.htm
免责声明:本站所提供试题均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用,不涉及商业盈利目的。如涉及版权问题,请联系本站管理员予以更改或删除。
12-06
11-24
11-18
11-15
11-15
11-12