石河子大学825数据结构考试大纲.doc

1石河子大学信息科学与技术学院学院硕士研究生入学数据结构考试大纲本数据结构考试大纲适用于石河子大学研究生院农业信息化技术及应用专业的硕士研究生入学考试。数据结构是计算机各专业的专业基础课。它的评价标准是高等学校计算机科学与技术各专业本科毕业生能达到的及格或及格以上水平,以保证被录取者具有基本的专业理论基础及程序设计能力,以利于计算机科学与技术各专业的导师择优选拔硕士研究生。一、考试基本要求1、了解数据结构及其分类、数据结构与算法的密切关系。2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。3、掌握设计算法的步骤和算法分析方法。4、掌握数据结构在排序和查找等常用算法中的应用。5、初步掌握文件组织方法和索引技术。二、考试方式与时间硕士研究生入学数据结构考试为笔试，考试时间为 180 分钟。三、考试主要内容和要求（一）算法与数据结构1.考试内容（1）数据结构的基本概念，数据的逻辑结构、存储结构；（2）算法的定义、算法的基本特性以及算法分析的基本概念。（3）算法效率的度量：时-空复杂度分析2.考试要求建立有关数据结构最基本的概念，包括数据的逻辑结构、存储结构和算法，算法分析的基本概念与基本方法，以及算法效率的分析。（二）线性表1.考试内容（1）线性表的定义以及基本操作。（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。（3）在以上两种存储结构上对线性表实施的最主要的操作的算法设计。2.考试要求掌握线性表的基本概念以及两种存储结构的构造原理，掌握在各种存储结构下对线性表进行的基本操作的算法设计。（三）栈和队列1.考试内容（1）堆栈与队列的基本概念、基本操作。（2）堆栈与队列的顺序存储结构与链式存储结构的构造原理。（3）在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设2计。2.考试要求掌握堆栈和队列的基本概念与特征，掌握在两种存储结构下如何对堆栈和队列进行插入和删除等操作，以及利用堆栈与队列解决实际问题的基本方法。（四）串1.考试内容（1）串的基本概念、串的基本操作和存储结构。（2）串的模式匹配算法和改进的 KMP 算法2.考试要求充分了解串的基本概念、掌握串的存储结构和相关的操作算法。（五）数组和广义表1.考试内容（1）数组的概念、多维数组的实现（2）对称矩阵和稀疏矩阵的压缩存储（3）广义表的基本概念2.考试要求掌握数组、广义表和稀疏矩阵的基本概念，物理结构和基本操作的实现。（六）树和二叉树1.考试内容（1）树的定义和性质（2）二叉树的概念、性质和实现（3）遍历二叉树和线索二叉树（4）树和森林（5）赫夫曼树及其应用（6）树的计数2.考试要求充分了解树型结构的逻辑特征，掌握各种存储结构的构造原理，能够熟练地利用常用的三种遍历方法，掌握利用二叉树的遍历操作解决实际问题的方法，掌握二叉排序树的建立以及在二叉排序树中查找一个结点存在与否的过程。（七）图1.考试内容（1）图的定义，基本概念，图的分类，常用名词术语。（2）图的邻接矩阵存储方法、邻接表存储方法的构造原理。（3）图的遍历操作。（4）最小生成树，最短路径，AOV 网与拓扑排序。2.考试要求充分了解图的逻辑结构的特点，掌握常用的两种存储方法，掌握最小生成树(Prim 算法和 Kruskal 算法)、最短路径、拓扑排序的具体求解过程。（八）查找1.考试内容（1）查找的概念,关键字比较次数,平均查找长度。3（2）顺序表的查找:顺序查找,折半查找,分块查找。（3）树表的查找:二叉排序树,平衡二叉树。（4）哈希(Hash)表的查找:哈希表的概念,哈希函数构造方法,哈希表的建立和查找,冲突处理方法。2.考试要求充分了解各种顺序查找方法；了解各种查找算法之间时空效率的差异；从结构与操作上了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及在散列文件中查找一个记录存在与否的过程。（九）内部排序1.考试内容（1）排序的基本概念，排序方法的分类。（2）插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆积排序法、归并排序、基数排序。（3）各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度简单分析。2.考试要求掌握数组、广义表和稀疏矩阵的基本概念，物理结构和基本操作的实现。四、试卷题型及比例1. 试题包括基本概念、基本知识、基本方法约占 40%50%；综合应用、算法和程序设计与算法分析约占 60%50%。2. 题型（大约比例）：选择填空题占 30%、综合应用题 40%、算法分析设计题占30%。3. 试卷满分为：150 分。