《数据结构》考试大纲

(满分 100 分，时限 90 分钟)

一、选用教材

李刚、刘万辉，数据结构(C 语言版)，高等教育出版社，2017 年。

二、考试范围和内容

第一章 绪论及C语言介绍

识记：

(1)数据、数据元素、数据项的基本概念;

(2)算法的概念、性质和目标。

领会：

(1)数据结构的三种逻辑结构和两种存储结构表示方法;

(2)数据结构和抽象数据类型的概念。

运用：

(1)算法的时间复杂度和空间复杂度分析。

第二章 线性表的结构分析与应用

识记：

(1)线性表的定义和抽象数据类型。

领会：

(1)顺序表的定义和存储结构;

(2) 单链表上实现的建表、查找、插入和删除等基本算法;

(3) 顺序表、单链表的优缺点。

运用：

(1)线性表的顺序表示和实现。线性表的链式表示和实现;

(2) 单链表、循环单链表、双向链表的存储结构和操作实现;

(3) 顺序表上的插入、删除等操作及其平均时间性能分析。

第三章 栈和队列的结构分析与应用

识记：

(1)栈的定义和特点。栈顶和栈底相关术语;

(2)队列的概念和特点。队首和队尾相关术语。

领会：

(1)顺序堆栈的存储结构和操作实现;

(2) 链式栈的存储结构和操作实现;

(3) 顺序队列的存储结构、顺序循环队列的表示和实现;

(4) 链式队列的存储结构和实现。

运用：

(1)栈和队列的应用。

第四章 字符串的结构分析与应用

识记：

(1)串的定义、空串、空格串、子串、主串、串相等。

领会：

(1)串的基本操作。

运用：

(1)模式匹配的原理及其 Brute-Force 算法

第五章 二维数组及广义表的结构分析与应用

识记：

(1)数组的定义;

(2)广义表的定义。

领会：

(1)特殊矩阵和稀疏矩阵的概念及其压缩存储;

(2)广义表的存储结构与操作实现。

运用：

(1)数组的实现机制。计算数组元素的地址计算公式。

第六章 树和二叉树的结构分析与应用

识记：

(1)树的定义、相关术语、表示方法和存储结构;

(2)二叉树的路径、路径长度、带权路径长度、哈夫曼树的概念。

领会：

(1)二叉树的存储结构——顺序表示法和链表表示法;

(2)二叉树的操作实现。

运用：

(1)二叉树、完全二叉树、满二叉树的定义和性质;

(2) 二叉树的三种遍历方法及相应的递归算法;

(3) 哈夫曼树的构造，哈夫曼编码方法;

(4) 树与二叉树的转换、树的遍历。

第七章 图的结构分析与应用

识记：

(1)图的定义和常用术语;

(2) 生成树和最小生成树的概念;

(3) 最短路径及相关概念;

(4) AOE 网、关键路径、关键活动的概念。

领会：

(1)邻接矩阵存储结构下图操作的实现;

(2)图的深度和广度优先遍历算法。

运用：

(1)图的邻接矩阵存储结构和邻接表存储结构;

(2) 构造最小生成树的普里姆算法和克鲁斯卡尔算法;

(3) 求最短路径的狄克斯特拉算法。

第八章 查找的分析与应用

识记：

(1)查找的基本概念、分类、平均查找长度。

领会：

(1)顺序查找、二分查找、分块查找的基本思想与实现方法;

(2)二叉排序树的查找、插入和删除算法。

运用：

(1)散列表的基本概念、构造方法和冲突解决方法;

(2) 散列表的查找算法;

(3) 各种查找算法的性能分析及比较。

第九章 排序的分析与应用

识记：

(1)排序的概念、分类;

(2)排序算法好坏的评判标准、排序方法的稳定性。

领会：

(1)直接选择排序的基本思想;

(2) 直接插入排序的基本思想;

(3) 冒泡排序的基本思想;

(4) 希尔排序的基本思想;

(5) 快速排序的基本思想。

运用：

(1)直接插入排序、冒泡排序、直接选择排序算法的实现;

(2) 各种内部排序方法的比较;

(3) 各种排序算法的性能分析和评价。

三、考核方式

1. 采取笔试，闭卷的形式进行考核。

2. 题型结构：选择题、填空题、判断题、程序分析填空题、算法设计题、综合应用题等。

3. 试题难易度：难度适中。基础题、中等难度题和难题比例分别大致控制在50%、30%、20%。