厦门理工学院2019年922数据结构研究生考试初试大纲

kyadmin

一、考试科目名称：

　　数据结构

　　二、招生系部和专业：

　　电气工程与自动化学院 电气工程方向

　　考试要求：

　　要求考生能比较全面的理解与掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度及空间复杂度的分析;能够根据数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

　　考试题型及比例：

　　分析运算题+算法设计(100%)

　　基本内容及范围：

　　第一章 引论

　　一、考核知识点

　　数据结构,数据类型,抽象数据类型基本概念;算法分析基本概念;算法复杂度基本概念;常见基本算法的时间复杂度分析;时间复杂度的几种表示法;

　　二、考核要求

　　1、了解数据、数据结构、抽象数据类型以及算法等概念的确切含义;

　　2、熟悉数据逻辑结构、存贮结构等概念;

　　3、掌握算法复杂度分析的基本概念及分析方法;

　　第二章 线性表

　　一、考核知识点

　　线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现;链表;用线性表表示一元多项式及实现稀疏多项式的相加等运算。

　　二、考核要求

　　1、了解线性表的概念

　　2、掌握顺序表上各种运算的实现方法

　　3、掌握各种链表的存储结构及运算。

　　第三章 栈和队列

　　一、考核知识点

　　栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现;栈和队列的应用、递归算法的设计。

　　二、考核要求

　　1、了解栈与队列的概念

　　2、掌握顺序栈、顺序队列，链栈、队列的各种运算的实现方法

　　3、掌握栈与递归的概念。

　　第四章 串

　　一、考核知识点

　　串的逻辑结构定义、串的基本运算及其实现;串的匹配算法。

　　二、考核要求

　　1、了解串的概念

　　2、掌握串的存贮和基本运算方法。

第五章 数组和广义表

　　一、考核知识点

　　数组的逻辑结构定义和存储方法;特殊矩阵和稀疏矩阵的压缩存储方法;广义表的逻辑结构和存储结构以及广义表运算的递归算法。

　　二、考核要求

　　1、了解数组的逻辑结构定义和存储方法

　　第六章 树和二叉树

　　一、考核知识点

　　树的基本概念;二叉树的定义、性质、存储表示;二叉树的遍历;线索二叉树;森林和二叉树的相互转换;树的应用;哈夫曼树及哈夫曼编码。

　　二、考核要求

　　1、了解树和二叉树的概念

　　2、掌握树与二叉树的转换

　　3、掌握树、森林、二叉树遍历的方法及二叉树遍历的实现算法，线索化二叉树及其运算，哈夫曼树及哈夫曼编码等概念。

　　第七章 图

　　一、考核知识点

　　图的基本概念、存储表示(邻接矩阵、邻接表、十字链表，邻接多重表);图的遍历、图的连通性问题;拓扑排序、关键路径;最短路径。

　　二、考核要求

　　1、了解图的概念

　　2、掌握图的存贮表示法，图的遍历及算法，生成树和最小生成树的概念

　　3、掌握最短路径，拓扑排序和关键路径等图的应用方法。

　　第九章 查找

　　一、考核知识点

　　查找表是集合类型的数据结构，其操作借助静态查找表、动态查找表、哈希表实现;

　　二、考核要求

　　1、掌握查找的概念

　　2、掌握线性表的查找(顺序查找，二分法查找，分块查找)，树表的查找(二叉排序树、平衡二叉树)，散列表的查找及相应处理算法。

　　第十章 排序

　　一、考核知识点

　　内部排序介绍插入排序、快速排序(交换排序)、选择排序、归并排序;排序的基本思想和算法分析。

　　外部排序介绍外存储器(磁带、磁盘)简介;多路平衡归并、置换选择排序、最佳归并树及磁带归并排序。

　　参考教材：

　　1、严蔚敏等 著《数据结构(C语言版)》清华大学出版社

　　说明：

　　1、考试基本内容：一般包括基础理论、实际知识、综合分析和论证等几个方面的内容。

　　2、难易程度：根据大学本科的教学大纲和本学科、专业的基本要求，一般应使大学本科毕业生中优秀学生在规定的三个小时内答完全部考题，略有一些时间进行检查和思考。排序从易到难。