研究生入学数据结构考试大纲.doc
文本预览下载声明
武汉工程大学
《数据结构》研究生入学考试大纲
一、“数据结构”课程的目的和要求
《数据结构》在计算机科学中是一门综合性的核心专业基础课，而且正逐渐发展成为众多理工专业的热门选修课。数据结构课程在整个课程体系中处于承上启下的核心地位，它一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法，一方面为进一步学习其它专业课奠定坚实的理论与实践基础。课程的主要任务是学习数据的逻辑结构，存储结构以及相关的算法设计。本课程的目的是使学生学会分析待加工处理数据的特性，以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。在教给学生数据结构选择和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和形式化思维方法，增强分析问题和解决问题的能力，更重要的是培养专业兴趣、树立创新意识。
数据结构基础知识
（一）基本内容：
1.1数据结构的兴起和发展。
1.2数据结构的研究对象。
1.3数据结构的基本概念。
1.4算法以及算法分析。
（二）基本要求：
（1）了解数据结构的兴起和发展。
（2）掌握数据结构的基本概念。
（3）掌握数据的逻辑结构，存储结构和算法的相互联系和实质。
（4）掌握算法以及算法分析。
（5）了解数据结构的主要应用领域及发展方向。
（三）重点及难点：
重点：数据结构的定义，数据的逻辑结构、存储结构的类型，算法的分析方法。
难点：算法的概念、特性和算法的分析。
第二章 线性表
（一）基本内容：
2.1线性表的逻辑结构。
2.2线性表的顺序存储结构及实现。
2.3线性表的链接存储结构及实现。
2.4线性表的其他存储方法。
2.4.1循环链表。
2.4.2双链表。
2.4.3静态链表。
2.5线性表的应用举例。
（二）基本要求：
（1）理解线性表的逻辑结构。
（2）掌握线性表的顺序和链接存储结构及各自的特征。
（3）熟练掌握在顺序和链接存储结构上的典型算法实现，并能够尽量提高算法性能。
（4）合理运用线性表来解决实际问题。
（三）重点及难点：
重点：数据结构的定义，数据的逻辑结构、存储结构的类型，算法的分析方法。
难点：算法的概念、特性和算法的分析。
第三章 栈和队列
（一）基本内容：
3.1栈的特征、顺序栈和链栈的实现。
3.2栈的基本应用。
3.3队列的特征、顺序队和链队列的实现。
3.4队列的基本应用。
3.5递归算法的运行过程，递归算法的特征与设计。
（二）基本要求：
（1）掌握栈和队列与线性表的关系。
（2）深入理解栈和队列的结构特性和典型操作。
（3）掌握栈和队列在编程中的应用。
（4）掌握递归算法的特征与设计方法。
（三）重点及难点：
重点：栈和队列的结构特性和典型操作。
难点：循环队列的设置和操作的实现，栈与队列的编程应用。
第四章 字符串
（一）基本内容：
4.1字符串的概念与特征；与线性表的区别和联系；字符串的基本操作。
4.2字符串的存储结构以及基本操作的实现。
4.3模式匹配算法及改进。
（二）基本要求：
（1）了解字符串的概念与特征；与线性表的区别和联系；字符串的基本操作。
（2）掌握字符串的存储结构以及基本操作的实现。
（3）掌握模式匹配算法及改进。
（三）重点及难点：
重点：字符串的基本操作在存储结构上的实现。
难点：模式匹配的KMP算法。
第五章 数组和广义表
（一）基本内容：
5.1多维数组的逻辑结构和存储方法。
5.2特殊矩阵的逻辑结构，特殊矩阵的逻辑结构到存储结构的映射函数。
5.3稀疏矩阵的特点，利用三元组对及特殊矩阵的压缩及典型操作算法设计。
5.4广义表的基本操作、广义表的存储结构。
（二）基本要求：
（1）掌握多维数组的行序优先与列序优先存储方法。
（2）掌握特殊矩阵的特点和压缩存储。
（3）掌握稀疏矩阵的特点和压缩存储。
（4）掌握广义表的基本操作、广义表的存储结构。
（5）了解广义表的基本操作实现。
（三）重点及难点：
重点：多维数组的逻辑结构和存储结构，特殊矩阵的结构特性和压缩存储方法，稀疏矩阵的压缩存储，广义表的概念与存储。
难点：矩阵的压缩存储以及地址变换，广义表的基本操作实现。
第六章 树和二叉树
（一）基本内容：
6.1树的基本概念和特征。
6.2二叉树的概念和性质、二叉树的顺序存储结构和链式存储结构、二叉树的遍历及应用、线索二叉树基本概念和构造。
6.3树的存储结构、森林与二叉树的相互转换、树和森林的遍历。
6.4 Huffman 树和Huffman编码。
（二）基本要求：
（1）掌握树的逻辑结构与存储结构。
（2）熟练掌握二叉树的基本性质、特征和存储结构、二叉树的遍历及应用。
（3）掌握线索二叉树的基本概念和构造。
（4）掌握树的存储结构、森林与二叉树的相互转换、树和森林的遍历。
（5）掌握Huffman 树和Huff
显示全部