福建2022年专升本数据结构考试大纲

　　数据结构( 100 分)

　　一、考试要求

　　1 、能分析数据的内在逻辑关系。

　　2 、掌握常用数据结构在计算机中的表示方法。

　　3 、理解数据表示和数据处理之间的关系，理解算法效率的分析方法。

　　4 、能利用常见的数据结构，进行算法设计。

　　二、考试内容

　　第 1 章 引论

　　1 、了解数据结构的基本概念。

　　2 、了解数据的逻辑结构、存储结构、算法的概念。

　　3 、理解数据类型、抽象数据类型的概念。

　　4 、理解时间复杂度、空间复杂度的概念。

　　第 2 章 表

　　1 、理解 ADT 表的概念及基本运算。

　　2 、掌握表的顺序存储结构及其运算的实现。

　　3 、掌握表的链接存储结构及其运算的实现。

　　4 、理解单链表、循环链表、双向链表的特点。

　　第 3 章 栈

　　1 、掌握栈的定义和基本运算。

　　2 、掌握栈的顺序实现及其运算的实现。

　　3 、掌握栈和队列的链接实现及其运算的实现。

　　4 、掌握栈的应用。

　　第 4 章 队列

　　1 、掌握队列的定义和基本运算。

　　2 、掌握队列的顺序实现(循环队列)及其运算的实现。

　　3 、掌握队列的链接实现及其运算的实现。

　　4 、掌握队列的应用。

　　第 5 章 递归

　　• 理解递归的概念。

　　• 了解分治与递归的关系。

　　• 了解用栈模拟递归技术。

　　第 6 章 排序与选择

　　• 理解排序的基本概念(关键字、内外排序、稳定性、时间效率、空间效率)

　　• 掌握选择排序的方法(简单选择排序、堆排序)

　　• 掌握插入排序的方法(直接插入排序)

　　• 掌握交换排序的方法(冒泡排序、快速排序)

　　• 了解合并排序的方法。

　　• 理解各种排序方法的优缺点。

　　第 7 章 树

　　1 、掌握树的表示法，包括父亲结点数组表示法、儿子链表表示法、左儿子右兄弟表示法。

　　2 、理解二叉树的定义和术语、性质。

　　3 、掌握二叉树的存储结构，包括顺序存储实现和指针实现。

　　4 、掌握二叉树的遍历算法及其应用。

　　5 、了解线索树的概念。

　　第 8 章 集合

　　1 、了解以集合为基础的抽象数据类型。

　　2 、了解集合上的基本运算。

　　3 、了解集合的实现(位向量实现、链表实现)。

　　第 9 章 符号表

　　• 理解抽象数据类型符号表的概念。

　　• 掌握符号表的数组实现。

　　• 掌握开散列表和闭散列表的实现。

　　• 理解散列函数构造方法以及处理冲突的办法。

　　• 掌握线性再散列技术。

　　第 10 章 字典

　　• 理解抽象数据类型字典及其运算。

　　• 掌握二叉搜索树及其实现。

　　第 11 章 优先队列

　　• 理解抽象数据类型优先队列及其基本运算。

　　• 理解堆的概念及其实现。

　　• 掌握哈夫曼树及其应用。

　　第 12 章 图

　　• 解图的概念、术语。

　　2 、掌握图的存储结构(邻接矩阵、邻接表)

　　3 、掌握图的遍历方法(深度优先遍历、广度优先遍历)

　　4 、掌握图的最小生成树的算法( prim 算法、 kruskal 算法)。

　　5 、掌握图的单源最短路径的 dijkstra 算法。

　　• 了解所有顶点对之间的最短路径 floyd 算法。

　　三、考题类型

　　• 选择题(概念、存储表示、算法描述)： 24 %

　　• 填空题(概念、存储表示、算法描述)： 16 %

　　• 应用题(综合)： 40 %

　　• 算法设计题： 20 %

　　参考用书：

　　《数据结构与算法》，王晓东编，高等教育出版社

　　感谢您阅读福建2022年专升本数据结构考试大纲，本文出自：诚为径统招专升本网，转载需带上本文链接地址：https://tzzsb.cwjedu.com/ksjc/33175