2024年长沙师范学院专升本《数据结构》考试大纲

　　掌握图的基本概念;了解图的相关术语;掌握图的存储结构;掌握图的遍历方法;了解图的连通性问题;掌握有向无环图及其应用;掌握最短路径的算法思想。

　　【重点、难点】

　　图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。

　　【知识范围】

　　7.1 图的定义和术语

　　7.2 图的存储结构

　　7.2.1 数组表示法

　　7.2.2 邻接表

　　7.2.3 十字链表

　　7.2.4 邻接多重表

　　7.3 图的遍历

　　7.3.1 深度优先搜索

　　7.3.2 广度优先搜索

　　7.4 图的连通性问题

　　7.5 有向无环图及其应用

　　7.5.1 拓扑排序

　　7.5.2 关键路径

　　7.6 最短路径

　　7.6.1 从某个源点到其余各顶点的最短路径

　　7.6.2 每一对顶点之间的最短路径

　　第八章 动态存储管理

　　【要求】

　　了解计算机存储管理问题;掌握边界标识法;掌握伙伴系统;了解无用单元收集;了解存储紧缩。

　　【重点、难点】

　　重点：可利用空间表及分配方法、边界标识法。

　　难点：边界标识法，伙伴系统。

　　【知识范围】

　　8.1 可利用空间表及分配方法

　　8.2 边界标识法

　　8.2.1 可利用空间表的结构

　　8.2.2 分配算法

　　8.2.3 回收算法

　　8.3 伙伴系统

　　8.3.1 可利用空间表的结构

　　8.3.2 分配算法

　　8.3.3 回收算法

　　8.4 无用单元收集

　　8.5 存储紧缩

　　第九章 查找

　　【要求】

　　掌握静态查找表和动态查找表的定义及二者区别;掌握顺序表的查找和有序表的查找;了解二叉排序树的定义;掌握二叉排序树的构造过程;了解平衡二叉树、B树的定义;掌握哈希表的定义及构造哈希函数和解决冲突的方法。

　　【重点、难点】

　　本章重点在于理解查找表的结构特点及其各种表示方法的特点和适用场合。

　　【知识范围】

　　9.1 静态查找表

　　9.1.1 顺序表的查找

　　9.1.2 有序表的查找

　　9.1.3 静态树表的查找

　　9.1.4 索引顺序表的查找

　　9.2 动态查找表

　　9.2.1 二叉排序树和平衡二叉树

　　9.2.2 B-树和B+树

　　9.2.3 键树

　　9.3 哈希表

　　9.3.1 什么是哈希表

　　9.3.2 哈希函数的构造方法

　　9.3.3 处理冲突的方法

　　9.3.4 哈希表的查找及其分析

　　第十章 内部排序

　　【要求】

　　掌握插入排序的应用;掌握快速排序的应用;掌握选择排序的应用;了解归并排序和基数排序;掌握各种排序方法的优缺点及应用场合。

　　【重点、难点】

　　希尔排序、快速排序、堆排序和归并排序等高效方法是本章的学习重点和难点。

　　【知识范围】

　　10.1 插入排序

　　10.1.1 直接插入排序

　　10.1.2 其他插入排序

　　10.1.3 希尔排序

　　10.2 快速排序

　　10.3 选择排序

　　10.3.1 简单选择排序

　　10.3.2 树形选择排序

　　10.3.3 堆排序

　　10.4 归并排序

　　10.5 基数排序

　　10.6 各种内部排序方法的比较讨论

　　第十一章 外部排序

　　【要求】

　　了解外部排序的概念;掌握外部排序与内部排序的区别;掌握外部排序的方法;了解多路平衡归并的实现;了解置换-选择排序;了解最佳归并树。

　　【重点、难点】

　　本章重点在于了解各种文件的结构特点及其适用场合。

　　【知识范围】

　　11.1 外存信息的存取

　　11.2 外部排序的方法

　　11.3 多路平衡归并的实现

　　11.4 置换-选择排序

　　11.5 最佳归并树

　　三、考试形式及分数比例

　　1.考核形式 闭卷考试，笔试。试卷满分200分，考试时间150分钟。

　　2.考试内容比例 数据的逻辑结构和存储结构、抽象数据类型以及时间及空间复杂度 、线性表、栈和队列、约占20%，串、数组约占15%，广义表、树和二叉树、图约占35%，动态存储管理、查找约占15%, 内部排序、外部排序约占15%。

　　四、教材

　　[1] 李春葆.《数据结构教程》第6版，清华大学出版社，北京，2022

　　[2] 严蔚敏，吴伟民.《数据结构》(C语言版)，清华大学出版社，北京，2018.

　　诚为径25/26届专升本英语VIP协议班上线，开启备考之旅！

　　专升本全科协议班上新，助力24专升本备考!

　　如果有专升本报考问题咨询，欢迎扫码关注微信公众号诚为径专升本考试网，有专业老师免费解答。

　　感谢您阅读2024年长沙师范学院专升本《数据结构》考试大纲，本文出自：诚为径统招专升本网，转载需带上本文链接地址：https://tzzsb.cwjedu.com/ksjc/61398/p2