《数据结构》课程考试大纲

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

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

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

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

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

二、考试内容及要求

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

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

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

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

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

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

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

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

9、内部排序：讨论比较各种内部排序方法，插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时间复杂度。在每类排序方法中，从简单方法入手，重点掌握性能较高效方法(插入排序类中的希尔排序、交换排序类中的快速排序、选择排序类中的堆排序等)。

10、外部排序： 实现外部排序的基本方法;为减少平衡归并排序中所需进行的外存读/写次数可采取的措施：利用败者树实现多路归并，通过置换-选择排序产生初始归并段，并对所得长度不等的归并段构造最佳归并树。

“数据结构”要求学生掌握基本概念、重要数据结构、基本算法，掌握各种数据结构的逻辑结构、存储结构和实现算法。根据当前计算机的应用发展举例说明数据结构的描述及应用的实现算法。

三、考试方式

采用笔试(闭卷)方式考试，考试时长100分钟。

四、试卷结构及题型

题型：填空题(10%)、单选题(10%)、判断题(10%)、简答题(20%)、程序填空题(20%)、 程序设计题(30%)。