内容发布更新时间 : 2024/11/15 18:42:22星期一 下面是文章的全部内容请认真阅读。

2018年研究生入学考试自命题科目考试大纲

考试科目代码：836 考试科目名称:数据结构与高级语言程序设计 考试内容范围: （一）数据结构部分： 一、数据结构和算法 1.要求考生理解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。 2.要求考生理解算法的五个特点。 3.要求考生掌握算法时间和空间复杂度的大O表示法。 二、线性表 1. 要求考生理解线性表的概念、逻辑结构。 2. 要求考生掌握线性表的顺序存储结构及其基本操作和特征。 3. 要求考生熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本操作。 4. 要求考生熟练掌握在顺序和链表存储结构上的典型算法实现，并能够尽量提高算法性能。 三、栈和队列 1. 要求考生掌握栈的特征、顺序栈和链栈的设置和操作实现。 2. 要求考生掌握队列的特征、顺序(循环队列)和链队列的设置和操作实现。 3. 要求考生了深入理解栈和队列的结构特性和典型操作。 四、串 1. 要求考生了解串的基本概念及顺序和链式存储结构。 2. 要求考生了解串的各种基本运算。 五、数组和广义表 1. 要求考生掌握数组的顺序存储结构及多维数组的元素地址计算。 2. 要求考生理解稀疏数组的概念和压缩存储的方法。 3. 要求考生理解广义表的基本概念、术语，了解广义表的存储结构。 六、树和二叉树 1. 要求考生理解树的基本概念和特征。 2. 要求考生熟练掌握二叉树的概念和性质、二叉树的顺序存储结构和链式存储结构、二叉树的先序、中序和后序的遍历和应用。熟练掌握二叉树的相关（递归、非递归）算法的实现。 3. 要求考生熟练掌握树的存储结构、树和森林与二叉树间的转换，掌握树和森林的遍历。 4. 要求考生熟练掌握哈夫曼树的概念、哈夫曼树的构造过程及哈夫曼编码。 七、图 1. 要求考生理解无向图、有向图的相关概念、术语，掌握图的邻接矩阵和邻接表的存储结构。 2. 要求考生熟练掌握图的深度优先和广度优先遍历算法及其应用。熟练掌握图的多种经典算法及其算法实现。 3. 要求考生理解图的连通性的概念。 4. 要求考生掌握求最小生成树（Prim算法和Kruskal算法）的求解过程。 5. 要求考生理解有向无环图的概念，掌握拓扑排序和关键路径的求解过程。 6. 要求考生了解带权最短路径的概念，掌握求最短路径的求解过程。 八、查找 1. 要求考生理解查找的概念及其效率的评价方法。 2. 要求考生理解静态查找表的概念，熟练掌握顺序、折半和分块查找算法。 3. 要求考生理解动态查找表和二叉排序树的概念和查找与操作。 4. 要求考生了解平衡二叉树的概念与操作。 5. 要求考生理解哈希表的概念，熟练掌握哈希函数的构造和处理冲突的基本方法。 九、内部排序 1.要求考生掌握插入类排序的排序算法、排序特点和排序过程：直接插入排序、希尔排序。 2.要求考生掌握交换类排序的排序算法、排序特点和排序过程：冒泡排序、快速排序。