《数据结构》课程教学大纲 - dlpueducn.doc

《《数据结构》课程教学大纲 - dlpueducn.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函数的构造及解决冲突的几种方法。教学重点和难点重点

6、掌握折半查找算法、二叉排序树、平衡二叉树、Hash函数构造方法及解决冲突的方法，难点是独立调试程序。教学内容一、静态查找表1.顺序表的查找2.索引顺序表的查找二、动态查找表1.二叉排序树2.平衡二叉树3.B-树三、哈希表1.什么是哈希表2.哈希函数的构造方法3.处理冲突的方法4.哈希表的查找及其分析四、查找算法的分析及应用第九章内部排序教学目的和要求要求学生掌握各种排序算法。教学重点和难点重点掌握希尔排序、快速排序、堆排序算法，难点是独立调试排序程序。教学内容一、排序的基本概念二、插入排序1.直接插入排序2.希尔排序三、快速排序四、

7、选择排序1.简单选择排序2.堆排序五、归并排序六、基数排序七、各种内部排序算法的比较