《数据结构》考试大纲参考模板范本.doc

1、数据结构考试大纲第一章 绪论教学目的和要求要求掌握数据结构的基本内容、逻辑结构的二元组表示及算法描述和算法分析。教学重点和难点重点掌握数据结构的二元组表示。难点是逻辑结构与物理结构的关系，为后面学习各种具体的数据结构打下基础。教学内容一、什么是数据结构 二、基本术语三、算法描述和算法分析第二章 线性表教学目的和要求系统地掌握线性表的逻辑表示及其顺序存储、链式存储的实现以及各种基本操作。教学重点和难点重点掌握不同形式链表的结点类型定义及其区别，以及不同形式链表中的各种操作，如：插入、删除。难点在于对各种操作的具体实现。教学内容一、线性表的定义和基本操作二、线性表的顺序存储结构 三、线性表的链式存

2、储结构 1. 线性链表2. 循环链表3. 双向链表四、一元多项式的表示和操作第三章 栈和队列教学目的和要求 系统地掌握栈和队列的存储结构和各种操作的实现。教学重点和难点重点掌握栈和队列的操作差异：“先进后出”和“先进先出”。教学内容一、栈 1. 抽象数据类型栈的定义2. 栈的表示和实现 二、栈的应用 三、栈与递归 四、队列1. 抽象数据类型队列的定义2. 链队列队列的链式表示和实现3. 循环队列队列的顺序表示和实现 第四章 串教学目的和要求掌握串的静态存储结构、动态存储结构、模式匹配。教学重点和难点静态存储结构下的几种常用操作，及动态存储结构的表示，模式匹配算法。教学内容一、串类型的定义 二、

3、串的存储结构及其运算 1. 定长顺序存储结构2. 堆分配存储结构3. 串的块链存储结构三、串的模式匹配四、串操作应用举例第五章 数组和广义表教学目的和要求掌握数组的顺序存储及稀疏矩阵的几种存储方法；掌握广义表的定义、操作和存储结构。 教学重点和难点掌握数组的顺序存储、稀疏矩阵的几种存储方法、广义表的定义、操作。 教学内容一、数组的定义和运算 二、数组的顺序存储结构 三、矩阵的压缩存储 四、广义表的定义 五、广义表的存储结构第六章 树和二叉树教学目的和要求掌握树的一般表示、二叉树、二叉树的性质、几种特殊形态的二叉树、二叉树的遍历算法以及树与森林间的转换和赫夫曼树的构造算法。 教学重点和难点重点掌

4、握二叉树的遍历及算法、二叉树与树、森林的转换、赫夫曼树的构造与编码，难点是独立编写程序。教学内容一、树的基本概念二、二叉树 1. 二叉树的定义2. 二叉树的性质3. 二叉树的存储结构三、遍历二叉树和线索二叉树 1. 二叉树的遍历方法与算法实现2. 线索二叉树四、树和森林 1. 树的存储结构2. 森林与二叉树的转换3. 树和森林的遍历五、赫夫曼树及其应用1. 最优二叉树2. 赫夫曼编码第七章 图教学目的和要求掌握图的存储结构、图的遍历算法、生成最小生成树的两种算法、拓扑排序、关键路径以及最短路径算法。教学重点和难点要求学生重点掌握图的存储结构、图的遍历、生成最小生成树的两种算法、关键路径和最短路

5、径的算法，难点是独立编写程序。教学内容一、图的基本概念二、图的存储结构及基本操作1. 数组表示法2. 邻接表三、图的遍历1. 深度优先搜索2. 广度优先搜索四、图的连通性问题1. 无向图的连通分量和生成树2. 最小生成树五、有向无环图及其应用1. 拓扑徘序2. 关键路径六、最短路径第八章 查找教学目的和要求要求学生掌握常用的查找算法，掌握Hash函数的构造及解决冲突的几种方法。 教学重点和难点重点掌握折半查找算法、二叉排序树、平衡二叉树、Hash函数构造方法及解决冲突的方法，难点是独立调试程序。教学内容一、静态查找表 1. 顺序表的查找2. 索引顺序表的查找二、动态查找表 1. 二叉排序树2. 平衡二叉树3. B-树三、哈希表 1. 什么是哈希表 2. 哈希函数的构造方法3. 处理冲突的方法4. 哈希表的查找及其分析四、查找算法的分析及应用第九章 内部排序教学目的和要求要求学生掌握各种排序算法。 教学重点和难点重点掌握希尔排序、快速排序、堆排序算法，难点是独立调试排序程序。教学内容一、排序的基本概念 二、插入排序 1. 直接插入排序2. 希尔排序三、快速排序 四、选择排序 1. 简单选择排序2. 堆排序五、归并排序 六、基数排序 七、各种内部排序算法的比较4 / 4