昆明理工大学硕士研究生入学考试《数据结构》考试大纲.doc

昆明理工大学硕士研究生入学考试数据结构考试大纲适用专业：071101系统理论、071102 系统分析与集成第一部分 考试形式和试卷结构一、试卷满分及考试时间试卷满分为150分，考试时间为180分钟二、答题方式答题方式为闭卷、笔试三、试卷的内容结构数据结构基本概念：5顺序与链式线性表：1015栈与队列：10数组与广义表：510串与模式匹配：5树与二叉树：1520图：1520查找与排序：1520四、试卷的题型结构判断题：20分，占13选择题：30分，占20简单题：60分，占40算法分析与设计题：40分，占27第二部分 考察的知识及范围一、数据结构的基本概念考核知识点：逻辑结构、存储结构、运算集合及算法。考核要求：1.理解数据的含义。2.理解逻辑结构、存储结构、运算集合及它们之间的关系。3.掌握算法的五个特点。4.掌握算法时间和空间复杂度的大O表示法。二、顺序表考核知识点：顺序表、栈、队列。考核要求：1.掌握顺序表及相应的算法。2.掌握队列的实现方法及队列的各种运算。3.掌握栈的各种运算。4.了解栈和队列在软件算法中的应用。三、链表、串、动态存储管理考核知识点：单向和双向链表、循环链表、用链表实现栈和队列、串的表示与模式匹配算法。考核要求：1.掌握单向、双向、循环链表的表示和相关算法。2.掌握用链表实现的栈和队列的相关运算。3.掌握串的顺序表示和链表表示及相关的运算。四、树型结构考核知识点：树、二叉树的概念、表示、存储及相关的运算。考核要求：1.掌握与树、二叉树相关的概念术语及它们之间的对应关系。2.掌握与树、二叉树的链式存储。3.掌握线索二叉树及相关的运算。4.掌握树、二叉树的遍历算法。五、树型结构的应用考核知识点：二叉排序树、平衡二叉树、霍夫曼树。考核要求：1.掌握二叉排序树的插入、删除、搜索算法。2.掌握最佳二叉排序树的构造算法。3.掌握霍夫曼树的构造算法。六、图、多维数组、稀疏矩阵及广义表考核知识点：图的相关概念、运算，多维数组的元素地址计算、稀疏矩阵的压缩存储表示、广义表的概念、存储方法。考核要求：1.掌握无向图、有向图的相关概念、术语、邻接矩阵表示和邻接表表示。2.掌握图的最小生成树构造、最短路径查找算法及有向图拓扑排序算法。3.掌握有向图关键路径查找算法。4.掌握多维数组元素地址计算方法。5.掌握稀疏矩阵的三元组、带辅助行向量的二元组、伪地址、十字链存储表示。6.掌握广义表的相关概念、术语及存储表示（包括带表头结点的表示）。七、文件结构考核知识点：顺序文件、散列文件、索引顺序文件及倒排文件的相关运算。考核要求：1.掌握文件上的基本操作的含义。2.掌握顺序文件的分块插值检索、3.掌握散列的相关概念、术语。4.掌握B树和B树两种索引结构及插入删除运算。5.掌握倒排序文件的作用及其检索运算。八、排序与线性表的检索考核知识点：常用的内排序算法及常用的线性表检索算法。考核要求：1.掌握直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序等排序算法。2.掌握以上各种排序算法是否稳定，各种排序时间和空间。3.掌握顺序检索、二分法检索、分快检索