云南财经大学2020年硕士研究生
《数据结构》入学考试大纲
本大纲适用于《数据结构》科目的入学考试,考试形式为:闭卷笔试,考试时间为:180分钟,考试参考书目为:严蔚敏主编《数据结构》(C语言),
清华大学出版社
《数据结构》是计算机专业的核心课程,是从事计算机软件开发和应用的人员必备的专业基础。数据结构的研究不仅涉及计算机硬件(编码理论、存储装置和存取方法)的研究范围,而且和计算机软件的研究有着密切的关系,在计算机科学中,它不仅是程序设计的基础,而且是设计和实现操作系统、数据库系统和大型应用系统的重要基础。因此《数据结构》的考试目的在于测试学生掌握数据组织、存储和处理的常用方法及基于各类常见数据结构的算法设计与分析的能力。
第一章 绪论
介绍数据结构的基本概念和术语算法的描述和算法分析的方法及数据结构在计算机科学中的地位
一、要求:了解数据结构在计算机科学中的地位,掌握数据的逻辑、物理结构、抽象数据类型概念和算法分析的基本方法。
二、考核知识点:
1. 数据、数据元素、数据项和抽象数据类型的概念
2. 数据结构的逻辑结构、存储结构的联系与区别
3. 算法设计的要求和算法效率的度量和算法的特征。
第二章 线性表
介绍线性表的逻辑、物理结构的特点,介绍线性表的常见操作及应用。
一、要求:了解线性表的基本概念和类型定义,掌握线性表的逻辑、物理结构的特点,线性表(顺序表、链表)的常见操作。应用顺序存储的线性表和单链表进行算法设计及其程序实现。
二、考核知识点:
1. 线性表的基本概念和类型定义
2. 线性表的逻辑、物理结构的特点
3. 线性表(顺序表、链表)的常见操作及实现
第三章 栈和队列
介绍栈和队列两种特殊的线性表及它们在软件开发中的具体应用。
一、要求:掌握栈和队列的定义,掌握顺序和链接存储的栈和队列操作的算法设计及其程序实现,了解栈和队的各种应用。
二、考核知识点:
1. 栈的定义及基本操作、
2. 栈的顺序存储结构、
3. 栈和队列的各种应用
4. 队列的定义及基本操作
5. 队列的顺序存储结构(循环队列)。
第四章 串
介绍作为非数值处理的主要对象串的概念、存储及串的常见操作
串的概念及表示。
一、要求:
了解空串、子串和掌握、串的概念及表示、串的操作算法设计、串的匹配算法设计
二、考核知识点:
1. 串的概念及表示
2. 串的操作算法设计
3. 串的匹配算法设计
第五章 数组和广义表
介绍数组和广义表作为线性表的扩展,讨论数组和广义表的逻辑结构和存储方式。
一、要求:了解数组的定义和运算、表示和特殊矩阵的存储和广义表的递归操作
二、考核知识点
1. :数组的定义和运算
2. 数组的顺序存储结构
3. 矩阵的压缩存储
4. 广义表的定义
5. 广义表的存储结构
第六章 树与二叉树
介绍树及二叉树的存储结构及各种操作、线索二叉树的线索化过程、树、森林与二叉树的转换和树作为一种非线性结构的应用。
一、要求::掌握树的定义、性质、存储结构和线索化二叉树;对二叉树的遍历算法及其实现,哈夫曼树的构造方法和编码方法能熟练应用;了解树、森林和二叉树的转换及遍历。
二、考核知识点:
1. 树及二叉树的定义、性质、存储结构
2. 二叉树的遍历算法及其实现
3. 线索化二叉树
4. 哈夫曼树的构造方法和编码方法
5. 树、森林和二叉树的转换及遍历
第七章 图
介绍图的存储结构及各种操作;图作为一种较树更复杂的非线性结构的应用。
一、要求:掌握图的定义和术语;对图的存储结构及深度和广度搜索算法思想及其实现能熟练应用;掌握最短路径算法、图的拓朴排序及关键路径算法。
二、考核知识点:
1. 图的相关术语
2. 图的存储结构
3. 深度和广度搜索算法思想及其实现
4. 最短路径算法
5. 图的拓朴排序及关键路径算法
第九章 查找
介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能分析
一、要求:掌握散列表的造表方法;了解散列函数和处理冲突的方法。对静态查找表的查找算法及其实现,二叉排序树的插入和查找算法及其实现能熟练应用。
二、考核知识点:
1. 对静态查找表的查找算法及其实现
2. 二叉排序树的插入和查找算法及其实现
3. 散列表的造表方法;散列函数和处理冲突的方法
第十章 内部排序
介绍常用的内部排序方法的基本思想、排序过程、算法实现、时间复杂度和空间复杂度性能的分析以及各种排序方法的比较和选择。
一、要求:掌握简单的排序方法的基本思想及排序过程能熟练应用;掌握各种排序的特点、
二、考核知识点:
1. 基本概念
2. 插入排序、交换排序、选择排序
3. 归并排序、基数排序
4. 内部排序方法的比较和选择
第十二章 文件
介绍文件在外存储器中的组织及各种操作的实现。
一、要求:了解文件在外存储器中的不同组织方法及特点。
二、考核知识点:文件的相关概念及组织方式