2020年赣南师范大学数据结构基础考试大纲

　　一、考试形式

　　笔试。

　　二、考试科目

　　《数据结构基础》。

　　三、试卷满分及考试时间

　　试卷满分：100分

　　考试时间：2小时

　　四、考试题型

　　选择题、综合应用题、算法设计题

　　五、不同性质考试内容所占比重

　　选择题（30%）、综合应用题（50%）、算法设计题（20%）

　　六、参考书目

　　李春葆.数据结构教程(第4版).清华大学出版社

　　七、考试大纲

　　第1章绪论

　　本章重点：数据结构的相关基本概念，算法的概念以及评价标准。

　　考核要求：

　　1、掌握数据结构的基本概念和术语；

　　2、掌握抽象数据类型的表示与实现；

　　3、理解算法的概念和算法的相关分析。

　　第2章线性表

　　本章重点：线性表的定义和特点，线性表的顺序存储结构、线性表的链式存储结构。

　　考核要求：

　　1、掌握线性表的类型定义；

　　2、掌握线性表的逻辑结构和相关基本概念；

　　3、掌握顺序表的定义和数据元素的存储位置的计算；

　　4、掌握线性链表的定义及其存储结构；

　　5、掌握单循环链表的相关定义和运算操作；

　　6、理解双向链表的相关定义和双向循环链表的相关定义。

　　第3章栈和队列

　　本章重点：栈和队列的逻辑概念和特点，栈和队列的存储结构及其基本操作，循环队列。

　　考核要求：

　　1、掌握栈的相关定义和表示；

　　2、掌握顺序栈的存储结构和基本操作；

　　3、掌握链栈的定义和基本操作；

　　4、了解栈的应用；

　　5、掌握的队列的定义和抽象类型；

　　6、理解队列的表示和实现。

　　第4章字符串

　　本章重点：串的定义、存储结构和基本操作。

　　考核要求：

　　1、掌握串的相关定义及其表示和实现；

　　2、掌握串的基本操作；

　　3、了解串的模式匹配。

　　第5章数组和广义表*

　　本章重量：数组的定义、基本运算和存储结构，特殊矩阵的压缩存储，广义表的定义、存储结构及运算。

　　考核要求：

　　1、掌握数组的基本概念；

　　2、掌握数组的存储结构、随机存取方法；

　　3、了解特殊矩阵的压缩存储

　　4、掌握稀疏矩阵的三元组表示

　　5、了解稀疏矩阵的十字链表表示

　　6、了解广义表的定义、广义表的存储结构及基本运算

　　第6章二叉树和树

　　本章重点：二叉树的概念，二叉树的性质，二叉树的周游，哈夫曼树及其应用。

　　考核要求：

　　1、掌握树的定义和基本概念；

　　2、掌握二叉树的定义及其相关概念；

　　3、掌握二叉树的周游和线索二叉树的操作和周游；

　　4、掌握树和树林的存储结构和周游；

　　5、掌握树林与二叉树的转换；

　　6、理解哈夫曼树及其应用。

　　第7章图

　　本章重点：图的基本概念及存储结构，图的遍历操作，最小生成树，拓朴排序、关键路径。

　　考核要求：

　　1、掌握图的基本概念和存储结构；

　　2、掌握图的周游；

　　3、掌握图的最小生成树的性质及构造方法；

　　4、了解Dijkstra算法和Floyd算法；

　　5、掌握拓朴排序的方法和求关键路径的方法。

　　第8章查找

　　本章重点：折半查找、二叉排序树、散列表及查找算法。

　　考核要求：

　　1、掌握查找的基本概念；

　　2、顺序查找和折半查找；

　　3、掌握哈希表的相关概念；

　　4、掌握处理冲突的方法；

　　5、掌握哈希表的查找及其分析；

　　6、掌握最佳二叉排序的构造方法；熟练掌握二叉排序树的检索、插入和删除；

　　7、了解调整平衡的模式；

　　8、了解Ｂ树和Ｂ＋树。

　　第9章内排序

　　本章重点：排序的基本概念，快速排序、堆排序、归并排序、希尔排序、基数排序的方法。

　　考核要求：

　　1、掌握排序的定义和分类；

　　2、掌握插入排序和折半插入排序的思想；

　　3、掌握希尔排序的思想和方法实现；

　　4、熟练掌握冒泡排序和快速排序的思想和算法实现；

　　5、熟练掌握选择排序，堆排序的思想和算法实现；

　　6、了解归并排序的思想。