《数据结构》课程整体教学设计

1、数据结构课程整体教学设计一、教学目的数据结构是计算机专业一门重要的专业基础课。通过本课程的学习，使得学生从数据逻辑结 构、存储结构和基本运算算法设计三个层面掌握基本的数据组织和数据处理方法，能够从问题出发设 计面向数据结构的求解算法，并能够对算法进行时间复杂度与空间复杂度分析。为后续课程学习打下 基础。二、教学要求通过讲授和上机实验， 使学生了解数据结构的原理和特点。掌握线性表、栈和队列、串、递归、 数组和广义表、树和二叉树、图、查找、内排序、外排序和文件等基本数据结构及其相关算法的设计。 具备较高水准的采用数据结构方法求解实际问题的能力。三、课程知识点知识单元知识点名称知识点内容知识点类型备

2、注数据结构概 述数据结构的基 本概念认识数据结构的定义、包括数据逻辑结 构、存储结构和运算的 3个层次。一般知识点算法的基本概 念认识算法的定义和 5个基本特性。重要知识点算法描述认识用咼级语言如C/C+描述算法的基本方法。一般知识点自我 学习算法分析掌握算法的时间复杂度和空间复杂度分 析方法。重要知识点数据结构+算法=程序认识从数据结构角度求解问题的基本步 骤。重要知识点线性表线性表及其逻 辑结构认识线性表的定义和线性表的基本运算。一般知识点线性表的顺序 存储结构一顺 序表掌握顺序表的存储结构特点和顺序表基 本运算的实现。重要知识点线性表的链式 存储结构一单 链表掌握单链表的存储结构特点、单

3、链表的插入和删除节点操作、单链表的建表方法、 以及单链表基本运算的实现。重要知识点线性表的链式 存储结构一双 链表掌握双链表的存储结构特点、双链表的插入和删除节点操作、双链表的建表方法、 以及双链表基本运算的实现。重要知识点线性表的链式 存储结构一循 环链表掌握循环链表的存储结构特点、 循环链表 的插入和删除节点操作、 循环链表的建表 方法、以及循环链表基本运算的实现。重要知识点线性表的应用掌握从求解问题描述、数据组织到运算算 法设计完整过程。难度知识点有序表掌握有序表和线性表的联系和差别， 有序 表的存储结构及其基本运算算法设计、 有 序表的归并算法。重要知识点栈栈的基本概念了解栈的定义、栈

4、的逻辑结构特性和栈的 基本运算。一般知识点栈的顺序存储 结构-顺序栈掌握顺序栈的存储结构特点和顺序栈基 本运算的实现。重要知识点栈的链式存储 结构-链栈掌握链栈的存储结构特点和链栈基本运 算的实现。重要知识点栈的应用了解栈在表达式求值中的应用和栈在求迷宫问题中的应用难度知识点队列队列的基本概 念了解队列的定义、队列的逻辑结构特性和 队列的基本运算。一般知识点队列的顺序存 储结构-顺序队掌握顺序队的存储结构特点和顺序队基 本运算的实现。重要知识点队列的链式存 储结构-链队掌握链队的存储结构特点和链队基本运 算的实现。重要知识点队列的应用了解队列在求迷宫问题中的应用难度知识点串串的基本概念了解串的

5、定义、串的逻辑结构特性和串的 基本运算。一般知识点串的顺序存储 结构-顺序串掌握顺序串的存储结构特点和顺序串基 本运算的实现。一般知识点串的链式存储 结构-链串掌握链串的存储结构特点和链串基本运 算的实现。一般知识点串的模式匹配掌握Brute-Force算法和KMP算法。难度知识点递归递归的基本概 念了解递归的定义、何时使用递归和递归模 型的表示方法。重要知识点递归的执行了解递归的执行过程。一般知识点递归算法的设 计掌握递归算法设计步骤、递归数据结构的 递归算法设计和递归求解方法的递归算 法设计。难度知识点数组数组的基本概 念了解数组的定义和数组的存储结构。一般知识点特殊矩阵的压 缩存储了解对

6、称矩阵、上下三角矩阵和对角矩阵 的压缩存储。重要知识点稀疏矩阵了解稀疏矩阵的特点、稀疏矩阵的三元组 表示和十字链表表示。一般知识点树树的基本概念了解树的定义、树的逻辑表示方法和树的 基本术语。一般知识点树的性质了解树的4个性质及其应用。一般知识点树的基本运算掌握树的先根遍历、后根遍历和层次遍历 过程。一般知识点树的存储结构掌握树的双亲存储结构、孩子链存储结构一般知识点和孩子兄弟链存储结构以及特点。二叉树二叉树的基本 概念了解二叉树、满二叉树和完全二叉树的定 义、二叉树的逻辑表示方法和二叉树的基 本术语。一般知识点二叉树树的性质了解二叉树树的5个性质及其应用。重要知识点二叉树与树、森 林之间的转

7、换了解森林、树转换为二叉树以及二叉树还 原为森林、树的过程。一般知识点二叉树存储结 构掌握二叉树的顺序存储结构和二叉树的 链式存储结构。重要知识点二叉树的基本 运算及其实现掌握二叉树的基本运算及其实现过程。重要知识点二叉树的遍历掌握二叉树的先序遍历、中序遍历、后序 遍历和层次遍历算法设计，了解先序遍 历、中序遍历和后序遍历非递归算法设 计。重要知识点二叉树遍历应 用掌握二叉树的4种遍历在二叉树算法设计 中的应用。难度知识点二叉树的构造掌握由先序遍历、中序遍历序列构造二叉 树和由后序遍历、中序遍历序列构造二叉 树的过程。一般知识点线索二叉树了解线索二叉树的概念、线索二叉树的构 造和遍历过程。一般

8、知识点哈夫曼树掌握哈夫曼树的概念、 构造哈夫曼树和产 生哈夫曼编码的过程。一般知识点图图的基本概念了解图的定义和图的基本术语。一般知识点图的存储结构掌握图的邻接矩阵存储方法和邻接表表 存储方法。重要知识点图的遍历掌握图深度优先搜索遍历和广度优先搜 索遍历算法。重要知识点图遍历算法的应用掌握图的两种遍历算法在图算法设计中 的应用。难度知识点生成树和最小 生成树了解生成树和最小生成树的概念，掌握构造最小生成树的普里姆算法和克鲁斯卡 尔算法。重要知识点最短路径了解最短路径的概念，掌握构造最短路径 的狄克斯特拉算法和弗洛伊德算法。重要知识点拓扑排序了解拓扑排序的概念和拓扑排序过程。一般知识点AOE网与

9、关键 路径了解AOE网与关键路径的概念、求解关 键路径的过程。一般知识点查找查找的基本概 念查找表和平均查找长度的定义。一般知识点线性表的查找掌握顺序查找、折半查找和分块查找算法 设计和算法分析。重要知识点树表的查找掌握二叉排序树的算法设计，了解平衡二叉树、B-和B+树的组织和查找过程。重要知识点哈布表查找掌握哈希表的基本概念、哈希函数构造方 法、哈希冲突解决方法和哈希查找过程。重要知识点内排序排序的基本概 念了解排序算法的稳定性、排序算法的分 类。一般知识点插入排序掌握直接插入排序算法的思路、排序算法和算法分析，折半插入排序算法的思路、 排序算法和算法分析，希尔排序算法的思 路、排序算法和算

10、法分析。重要知识点交换排序掌握冒泡排序算法的思路、排序算法和算法分析，快速排序算法的思路、排序算法 和算法分析。重要知识点选择排序掌握直接选择排序算法的思路、排序算法和算法分析，堆排序算法的思路、排序算 法和算法分析。重要知识点归并排序掌握归并排序算法的思路，二路归并算法和算法分析。重要知识点基数排序掌握基数排序算法的思路、排序算法和算法分析。重要知识点各种内排序方 法的比较和选 择掌握各种内排序方法时间和空间因素的 比较和分析。难度知识点外排序外排序的基本 概念了解外排序概念和外排序的一般过程。一般知识点磁盘排序掌握磁盘排序中生成初始归并段、多路平衡归并和构造最佳归并树的过程。重要知识点磁带

11、排序了解磁带排序的特点和磁带的多路平衡 归并排序过程。一般知识点自我 学习四、课程能力点能力单元能力点名称能力点要求能力点类型备注面向数据结构 的算法设计数据结构算法 设计流程掌握从数据逻辑结构到存储结构的 映射关系，算法的时间复杂度和空间 复杂度分析，使学生能够从数据结构 角度出发，掌握从逻辑结构t存储结 构t基本运算算法设计的流程，并通过设计合理的存储结构来设计出好 算法的过程。思维能力点线性表线性表算法设 计掌握线性表的顺序存储结构和链式 存储结构中线性表基本运算算法设 计方法。设计能力点线性表应用掌握线性表的逻辑结构T存储结构T运算算法设计的主线，利用线性表 求解实际应用问题。设计能力

12、点栈和队列栈算法设计掌握栈的顺序存储结构和链式存储 结构中栈基本运算算法设计方法。设计能力点队列算法设计掌握队列的顺序存储结构和链式存 储结构中队列基本运算算法设计方 法。设计能力点栈的应用掌握栈在实际求解问题中的应用方 法。设计能力点队列的应用掌握队列在实际求解问题中的应用 方法。设计能力点递归递归算法设计递归算法设计的一般步骤，包括基于 递归数据结构的递归算法设计方法 和基于递归求解方法的递归算法设 计方法。思维能力点二叉树二叉树结构掌握二叉树、满二叉树和完全二叉树 的性质和结点计算。思维能力点二叉树遍历算 法设计掌握二叉树4种遍历算法设计设计能力点二叉树遍历算 法的应用掌握基于二叉树遍历

13、的二叉树递归 算法设计设计能力点图图遍历算法设计掌握基于两种图遍历的图算法设计设计能力点图的应用掌握求最小生成树的 Prim和Kruskal 算法和求最短路径的Dijkstra和 Flody算法。设计能力点查找查找算法设计掌握顺序查找、折半查找、二叉排序 树和哈布表查找算法。思维能力点查找的应用基于不同的数据结构选择合适的查 找算法求解问题。设计能力点内排序内排序算法设 计掌握直接插入排序、折半插入排序、 希尔排序、冒泡排序、快速排序、简 单选择排序、堆排序、二路归并排序 和基数排序算法。思维能力点内排序的应用基于不冋的要求选择合适的内排序 算法求解问题。设计能力点五、授课课时安排知识单元授课

14、课时涵盖知识点情况授课目标重难点要求备注1绪论4数据结构的基本概念；算法的基目标：数据结构的基本概本概念；算法描述；算法分析； 数据结构+算法=程序念，数据逻辑结构和存储结 构的映射关系，数据类型和 数据结构的区别和联系，利 用抽象数据类型表述求解问 题的方法，算法的特性和采 用C/C+语言描述算法的方 法，算法设计目标和分析方 法，包括时间复杂度和空间复 杂度分析，从数据结构的角 度设计好算法的过程。重点和难点：算法的时间和 空间复杂度分析，特别是递归 算法的时间和空间复杂度分 析，如何设计好的算法。2、线性表10线性表及其逻辑结构；线性表的 顺序存储结构一顺序表；线性表 的链式存储结构一单

15、链表；线性 表的链式存储结构 双链表；线性表的链式存储结构一循环链 表；线性表的应用；有序表。目标：线性表的逻辑结构特 点和线性表抽象数据类型的 描述方法，线性表的两类存 储结构设计方法以及各自的 优缺点，顺序表算法设计方 法，单链表、双链表和循环 链表算法设计方法。重点：顺序表、单链表、双 链表和循环链表算法设计方 法，有序表的特点和有序表 的归并算法设计方法。难点：利用线性表求解复杂问 题。3、栈和队列8栈的基本概念；栈的顺序存储结 构-顺序栈；栈的链式存储结构 - 链栈；栈的应用；队列的基本概 念；队列的顺序存储结构 -顺序 队；队列的链式存储结构-链队； 队列的应用。目标：栈的逻辑结构

16、特性和 栈抽象数据类型的描述方法， 栈的先进后出特点，栈基 本运算在两类存储结构下的 实现算法，栈在实际求解问 题中的应用方法，队列的逻 辑结构特性和队列抽象数据 类型的描述方法，队列的先 进后出特点，队列基本运算 在两类存储结构下的实现算 法，队列在实际求解问题中 的应用方法。重点：栈算法设计，队列 算法设计。难点：栈和队列在求解复杂问 题中的应用。4、串4串的基本概念；串的顺序存储结 构-顺序串；串的链式存储结构 - 链串；串的模式匹配。目标：串的逻辑结构特性和 串抽象数据类型的描述方法， 串的两类存储结构设计方 法以及各自的优缺点，顺序 串算法设计方法，链串算法 设计方法，串的模式匹配算

17、 法设计方法。重点：顺序串运算算法设 计，链串运算算法设计。 难点：KMP算法。5、递归2递归的基本概念；递归的执行； 递归算法的设计。目标：掌握递归和递归模型 的概念，递归算法的执行过 程，递归算法设计的一般步 骤。重点：基于递归数据结构的 递归算法设计方法，基于递 归求解方法的递归算法设计 方法难点：利用递归思想求解复杂 的应用问题。6、数组和稀 疏矩阵4数组的基本概念；特殊矩阵的压 缩存储；稀疏矩阵。目标：数组的逻辑结构特性 和数组抽象数据类型的描述 方法，数组的顺序存储结构 及其特点，对称矩阵、上三 角矩阵、下二角矩阵和二对角 矩阵的压缩存储，稀疏矩阵 的两种压缩存储方法。重点：各种特

18、殊矩阵的压缩存 储方法。7、树和二叉 树12树的基本概念；树的性质；树的 基本运算；树的存储结构；二叉 树的基本概念；二叉树树的性 质；二叉树与树、森林之间的转 换；二叉树存储结构；二叉树的 基本运算及其实现；二叉树的遍 历；二叉树遍历应用；二叉树的 构造；线索二叉树；哈夫曼树。目标：树的定义及其逻辑结 构特性，树的逻辑结构表示 方法和树的性质，树的遍历 方法和树的存储结构，二叉 树的定义及其性质，二叉树 与树、森林之间的转换，二 叉树的两种存储结构和二叉 树的基本运算算法设计。二 叉树的遍历过程、算法设计及 其应用。二叉树的构造过 程，线索二叉树的特点及其 构造过程，哈夫曼树和哈夫 曼编码的

19、构造过程。重点：二叉树性质和二叉树 结点计算，二叉树的遍历过程、算法设计及其应用。 难点：灵活利用二叉树的遍历 思路进行较复杂二叉树算法 设计。&图10图的基本概念；图的存储结构； 图的遍历；图遍历算法的应用； 生成树和取小生成树；取短路 径；拓扑排序；AOE网与关键 路径。目标：图的定义及其逻辑结 构特性，图抽象数据类型的描 述方法，图的基本术语及其 含义，图的邻接矩阵和邻接 表两种主要的存储结构及其 特点，图的深度优先和广度 优先遍历算法，图遍历算法 的应用，生成树和最小生成 树的定义和求最小生成树的Prim和Kruskal算法，最短 路径的概念和求最短路径的 Dijkstra和F

20、lody算法，拓扑 排序过程，关键路径的定义 及其构造过程。重点：图的邻接矩阵和邻接 表两种主要的存储结构及其 特点，图的深度优先和广度 优先遍历算法，Prim和 Kruskal 算法， Dijkstra 和 Flody算法。难点：图遍历算法的应用。9、查找8查找的基本概念；线性表的查 找；树表的查找；哈希表查找。目标：掌握查找的概念， 线性表的顺序查找和折半查 找算法，索引存储结构和分块 查找方法，二叉排序树的定 义、查找和插入算法、删除过 程，平衡二叉树的特点及其 调整方法，B-树的定义和基 本操作过程，B+的定义，哈 希表的定义及其特点，哈希 函数构造方法和解决冲突的 方法，各种查找方法

21、的性能 分析。重点：各种查找算法的实现。 难点：各种查找方法的性能分 析。10、内排序8排序的基本概念；插入排序；交 换排序；选择排序；归并排序； 基数排序；各种内排序方法的比 较和选择。目标：排序的定义和相关概 念，插入排序算法，包括直 接插入排序、折半插入排序和 希尔排序，交换排序算法， 包括冒泡排序和快速排序， 选择排序算法，包括简单选择 排序和堆排序，归并排序算 法，包括二路归并排序，基 数排序算法，包括最低位优先 和最高位优先排序，各种内 排序方法的性能分析和比较。 重点：各种排序算法的实现。 难点：各种内排序方法的性能 分析和比较。11、外排序2外排序的基本概念；磁盘排序； 磁带排

22、序。目标：外排序的基本步骤， 磁盘的特性和磁盘排序的 基本步骤，生成初始归并段 的方法，多路平衡归并过程 及败者树在归并过程中的应 用，最佳归并树的构造过 程。了解磁带排序的概念和 磁带多路平衡归并和多阶段 归并排序方法。重点：磁盘排序的基本步 骤，最佳归并树的构造过 程。难点：多路平衡归并过程及败 者树在归并过程中的应用。六、其他课时安排课时 类型内容对应能力点要求课 时备注上机 实验 题上机实验项目1线性表基本运算算法设计。线性表算法 设计设计顺序表各种基本运 算的算法，设计单链表 各种基本运算的算法。3上机实验项目 2栈基本 运算算法设计。栈算法设计设计顺序栈各种基本运 算的算法，设计链

23、栈各 种基本运算的算法。3上机实验项目 3用栈求 解迷宫问题栈的应用熟练掌握栈的特点和应 用。3上机实验项目 4 队列基 本运算算法设计。队列算法设 计设计顺序队各种基本运 算的算法，设计链队各 种基本运算的算法。3上机实验项目 5用队列 求解迷宫问题队列的应用熟练掌握队列的特点和 应用。3上机实验项目 6求解n 皇后问题。递归算法设 计掌握递归算法设计方 法。3上机实验项目 7二叉树4种遍历算法设计二叉树遍历 算法设计掌握二叉树4种遍历算 法的特点和实现过程。3上机实验项目 8图遍历 算法设计图遍历算法 设计掌握图的DFS和BFS遍 历算法设计。3上机实验项目 9图中带 条件的路径查找图遍历

24、算法 设计掌握图的DFS遍历算法 设计。3上机实验项目10线性表 的查找算法设计查找算法设 计掌握顺序查找和折半查 找算法设计。3上机实验项目11树表的查找算法设计查找算法设 计掌握二叉排序树算法设 计。3上机头验项目12哈希表 的查找算法设计查找算法设 计掌握哈希表查找算法设 计。3上机实验项目13插入排 序算法设计内排序算法 设计掌握直接插入排序、折 半插入排序、希尔排序 算法设计。3上机实验项目14交换排 序算法设计内排序算法 设计掌握冒泡排序、快速排 序算法设计。3上机实验项目15选择排 序算法设计内排序算法 设计掌握简单选择排序和堆 排序算法设计。3上机实验项目16归并序 算法设计内排序算法 设计掌握二路归并排序算法 设计。3综合 实验 题上机实验项目1线性表 应用1 :求集合（用单 链表表示）的并、交和差 运算，求两个多项式相线性表应用熟练掌握线性表的各种 存储结构和求解问题的 算法设计。6加运算， 链表综合算法 设计。上机实验项目 2用二叉 树表示家谱并实现相关算 法二叉树遍历 算法的应用掌握基于二叉树遍历的 二叉树递归算法设计。6上机实验项目 3 GIS中 取短路径规划。图的应用掌握求图