2023年湖南工学院专升本《数据结构》课程考试大纲

　　课程名称：数据结构 (Data Structure)

　　适用专业：计算机相关专业

　　使用教材：严蔚敏，数据结构(C语言版)，清华大学出版社

　　一、该课程的性质、目的及任务

　　“数据结构”是一门专业基础课程，目的是培养学生的数据抽象能力，学会分析程序所处理的数据结构及其特性，为程序处理的数据选择合适的逻辑结构、存储结构及相应算法，掌握算法的时间和空间复杂度的分析技术。

　　二、考试内容及要求

　　1、绪论：熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系;了解抽象数据类型的定义、表示和实现方法;熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式;理解算法五个要素的确切含义;掌握计算语句频度和估算算法时间复杂度的方法。

　　2、线性表：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法;在线性表的两类存储结构(顺序存 储和链式存储)上实现基本操作;一元多项式的抽象数据类型定义、表示及加法的实现。

　　3、栈和队列：栈和队列的结构特性;在两种存储结构上如何实现栈和队列的基本操作，栈和队列在程序设计中的应用，利用栈去模拟递归程序的运行。

　　4、串： 串的数据类型定义;串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构;串的各种基本操作的实现及应用;串的模式匹配算法。

　　5、数组和广义表： 数组的类型定义和表示方法;特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现;广义表的逻辑结构和存储结构、m元多项式的广义表表示以及广义表的操作的递归算法举例 。

　　6、树和二叉树： 二叉树的定义、性质和存储结构;二叉树的遍历和线索化以及遍历算法的各种描述形式;树和森林的定义、存储结构、树和森林与二叉树的转换、遍历;树的多种应用;平衡二叉树、平衡二叉排序树的 定义、性质及其应用。

　　7、图： 图的定义和术语;图的四种存储结构：数组表示法、邻接表、十字链表和邻接多重表;图的两种遍历策略：深度优先搜索和广度优先搜索;图的连通性：连通分量和最小生成树;拓扑排序和关键路径;两类求最短路径问题的算法。

　　8、查找：讨论查找表(包括静态查找表和动态查找表)的各种实现方法：顺序表、有序表、树表和哈希表;关于衡量查找表的主要操作