《数据结构》课程整体教学设计.docx
《《数据结构》课程整体教学设计.docx》由会员分享，可在线阅读，更多相关《《数据结构》课程整体教学设计.docx（30页珍藏版）》请在冰点文库上搜索。
《数据结构》课程整体教学设计
《数据结构》课程整体教学设计
一、教学目的
《数据结构》是计算机专业一门重要的专业基础课。
通过本课程的学习，使得学生从数据逻辑结构、存储结构和基本运算算法设计三个层面掌握基本的数据组织和数据处理方法，能够从问题出发设计面向数据结构的求解算法，并能够对算法进行时间复杂度与空间复杂度分析。
为后续课程学习打下基础。
二、教学要求
通过讲授和上机实验，使学生了解《数据结构》的原理和特点。
掌握线性表、栈和队列、串、递归、数组和广义表、树和二叉树、图、查找、内排序、外排序和文件等基本数据结构及其相关算法的设计。
具备较高水准的采用数据结构方法求解实际问题的能力。
三、课程知识点
知识单元
知识点名称
知识点内容
知识点类型
备注
数据结构概述
数据结构的基本概念
认识数据结构的定义、包括数据逻辑结构、存储结构和运算的3个层次。
一般知识点
算法的基本概念
认识算法的定义和5个基本特性。
重要知识点
算法描述
认识用咼级语言如C/C++描述算法的基
本方法。
一般知识点
自我学习
算法分析
掌握算法的时间复杂度和空间复杂度分析方法。
重要知识点
数据结构+算法
=程序
认识从数据结构角度求解问题的基本步骤。
重要知识点
线性表
线性表及其逻辑结构
认识线性表的定义和线性表的基本运算。
一般知识点
线性表的顺序存储结构一顺序表
掌握顺序表的存储结构特点和顺序表基本运算的实现。
重要知识点
线性表的链式存储结构一单链表
掌握单链表的存储结构特点、单链表的插
入和删除节点操作、单链表的建表方法、以及单链表基本运算的实现。
重要知识点
线性表的链式存储结构一双链表
掌握双链表的存储结构特点、双链表的插
入和删除节点操作、双链表的建表方法、以及双链表基本运算的实现。
重要知识点
线性表的链式存储结构一循环链表
掌握循环链表的存储结构特点、循环链表的插入和删除节点操作、循环链表的建表方法、以及循环链表基本运算的实现。
重要知识点
线性表的应用
掌握从求解问题描述、数据组织到运算算法设计完整过程。
难度知识点
有序表
掌握有序表和线性表的联系和差别，有序表的存储结构及其基本运算算法设计、有序表的归并算法。
重要知识点
栈
栈的基本概念
了解栈的定义、栈的逻辑结构特性和栈的基本运算。
一般知识点
栈的顺序存储结构-顺序栈
掌握顺序栈的存储结构特点和顺序栈基本运算的实现。
重要知识点
栈的链式存储结构-链栈
掌握链栈的存储结构特点和链栈基本运算的实现。
重要知识点
栈的应用
了解栈在表达式求值中的应用和栈
在求迷宫问题中的应用
难度知识点
队列
队列的基本概念
了解队列的定义、队列的逻辑结构特性和队列的基本运算。
一般知识点
队列的顺序存储结构-顺序队
掌握顺序队的存储结构特点和顺序队基本运算的实现。
重要知识点
队列的链式存储结构-链队
掌握链队的存储结构特点和链队基本运算的实现。
重要知识点
队列的应用
了解队列在求迷宫问题中的应用
难度知识点
串
串的基本概念
了解串的定义、串的逻辑结构特性和串的基本运算。
一般知识点
串的顺序存储结构-顺序串
掌握顺序串的存储结构特点和顺序串基本运算的实现。
一般知识点
串的链式存储结构-链串
掌握链串的存储结构特点和链串基本运算的实现。
一般知识点
串的模式匹配
掌握Brute-Force算法和KMP算法。
难度知识点
递归
递归的基本概念
了解递归的定义、何时使用递归和递归模型的表示方法。
重要知识点
递归的执行
了解递归的执行过程。
一般知识点
递归算法的设计
掌握递归算法设计步骤、递归数据结构的递归算法设计和递归求解方法的递归算法设计。
难度知识点
数组
数组的基本概念
了解数组的定义和数组的存储结构。
一般知识点
特殊矩阵的压缩存储
了解对称矩阵、上下三角矩阵和对角矩阵的压缩存储。
重要知识点
稀疏矩阵
了解稀疏矩阵的特点、稀疏矩阵的三元组表示和十字链表表示。
一般知识点
树
树的基本概念
了解树的定义、树的逻辑表示方法和树的基本术语。
一般知识点
树的性质
了解树的4个性质及其应用。
一般知识点
树的基本运算
掌握树的先根遍历、后根遍历和层次遍历过程。
一般知识点
树的存储结构
掌握树的双亲存储结构、孩子链存储结构
一般知识点
和孩子兄弟链存储结构以及特点。
二叉树
二叉树的基本概念
了解二叉树、满二叉树和完全二叉树的定义、二叉树的逻辑表示方法和二叉树的基本术语。
一般知识点
二叉树树的性
质
了解二叉树树的5个性质及其应用。
重要知识点
二叉树与树、森林之间的转换
了解森林、树转换为二叉树以及二叉树还原为森林、树的过程。
一般知识点
二叉树存储结构
掌握二叉树的顺序存储结构和二叉树的链式存储结构。
重要知识点
二叉树的基本运算及其实现
掌握二叉树的基本运算及其实现过程。
重要知识点
二叉树的遍历
掌握二叉树的先序遍历、中序遍历、后序遍历和层次遍历算法设计，了解先序遍历、中序遍历和后序遍历非递归算法设计。
重要知识点
二叉树遍历应用
掌握二叉树的4种遍历在二叉树算法设计中的应用。
难度知识点
二叉树的构造
掌握由先序遍历、中序遍历序列构造二叉树和由后序遍历、中序遍历序列构造二叉树的过程。
一般知识点
线索二叉树
了解线索二叉树的概念、线索二叉树的构造和遍历过程。
一般知识点
哈夫曼树
掌握哈夫曼树的概念、构造哈夫曼树和产生哈夫曼编码的过程。
一般知识点
图
图的基本概念
了解图的定义和图的基本术语。
一般知识点
图的存储结构
掌握图的邻接矩阵存储方法和邻接表表存储方法。
重要知识点
图的遍历
掌握图深度优先搜索遍历和广度优先搜索遍历算法。
重要知识点
图遍历算法的
应用
掌握图的两种遍历算法在图算法设计中的应用。
难度知识点
生成树和最小生成树
了解生成树和最小生成树的概念，掌握构
造最小生成树的普里姆算法和克鲁斯卡尔算法。
重要知识点
最短路径
了解最短路径的概念，掌握构造最短路径的狄克斯特拉算法和弗洛伊德算法。
重要知识点
拓扑排序
了解拓扑排序的概念和拓扑排序过程。
一般知识点
AOE网与关键路径
了解AOE网与关键路径的概念、求解关键路径的过程。
一般知识点
查找
查找的基本概念
查找表和平均查找长度的定义。
一般知识点
线性表的查找
掌握顺序查找、折半查找和分块查找算法设计和算法分析。
重要知识点
树表的查找
掌握二叉排序树的算法设计，了解平衡二
叉树、B-和B+树的组织和查找过程。
重要知识点
哈布表查找
掌握哈希表的基本概念、哈希函数构造方法、哈希冲突解决方法和哈希查找过程。
重要知识点
内排序
排序的基本概念
了解排序算法的稳定性、排序算法的分类。
一般知识点
插入排序
掌握直接插入排序算法的思路、排序算法
和算法分析，折半插入排序算法的思路、排序算法和算法分析，希尔排序算法的思路、排序算法和算法分析。
重要知识点
交换排序
掌握冒泡排序算法的思路、排序算法和算
法分析，快速排序算法的思路、排序算法和算法分析。
重要知识点
选择排序
掌握直接选择排序算法的思路、排序算法
和算法分析，堆排序算法的思路、排序算法和算法分析。
重要知识点
归并排序
掌握归并排序算法的思路，二路归并算法
和算法分析。
重要知识点
基数排序
掌握基数排序算法的思路、排序算法和算
法分析。
重要知识点
各种内排序方法的比较和选择
掌握各种内排序方法时间和空间因素的比较和分析。
难度知识点
外排序
外排序的基本概念
了解外排序概念和外排序的一般过程。
一般知识点
磁盘排序
掌握磁盘排序中生成初始归并段、多路平
衡归并和构造最佳归并树的过程。
重要知识点
磁带排序
了解磁带排序的特点和磁带的多路平衡归并排序过程。
一般知识点
自我学习
四、课程能力点
能力单元
能力点名称
能力点要求
能力点类型
备注
面向数据结构的算法设计
数据结构算法设计流程
掌握从数据逻辑结构到存储结构的映射关系，算法的时间复杂度和空间复杂度分析，使学生能够从数据结构角度出发，掌握从逻辑结构t存储结构t基本运算算法设计的流程，并通
过设计合理的存储结构来设计出好算法的过程。
思维能力点
线性表
线性表算法设计
掌握线性表的顺序存储结构和链式存储结构中线性表基本运算算法设计方法。
设计能力点
线性表应用
掌握线性表的逻辑结构T存储结构
T运算算法设计的主线，利用线性表求解实际应用问题。
设计能力点
栈和队列
栈算法设计
掌握栈的顺序存储结构和链式存储结构中栈基本运算算法设计方法。
设计能力点
队列算法设计
掌握队列的顺序存储结构和链式存储结构中队列基本运算算法设计方法。
设计能力点
栈的应用
掌握栈在实际求解问题中的应用方法。
设计能力点
队列的应用
掌握队列在实际求解问题中的应用方法。
设计能力点
递归
递归算法设计
递归算法设计的一般步骤，包括基于递归数据结构的递归算法设计方法和基于递归求解方法的递归算法设计方法。
思维能力点
二叉树
二叉树结构
掌握二叉树、满二叉树和完全二叉树的性质和结点计算。
思维能力点
二叉树遍历算法设计
掌握二叉树4种遍历算法设计
设计能力点
二叉树遍历算法的应用
掌握基于二叉树遍历的二叉树递归算法设计
设计能力点
图
图遍历算法设
计
掌握基于两种图遍历的图算法设计
设计能力点
图的应用
掌握求最小生成树的Prim和Kruskal算法和求最短路径的Dijkstra和Flody算法。
设计能力点
查找
查找算法设计
掌握顺序查找、折半查找、二叉排序树和哈布表查找算法。
思维能力点
查找的应用
基于不同的数据结构选择合适的查找算法求解问题。
设计能力点
内排序
内排序算法设计
掌握直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、二路归并排序和基数排序算法。
思维能力点
内排序的应用
基于不冋的要求选择合适的内排序算法求解问题。
设计能力点
五、授课课时安排
知识单元
授课
课时
涵盖知识点情况
授课目标重难点要求
备注
1绪论
4
数据结构的基本概念；算法的基
目标：
①数据结构的基本概
本概念；算法描述；算法分析；数据结构+算法=程序
念，②数据逻辑结构和存储结构的映射关系，③数据类型和数据结构的区别和联系，④利用抽象数据类型表述求解问题的方法，⑤算法的特性和采用C/C++语言描述算法的方法，⑥算法设计目标和分析方法，包括时间复杂度和空间复杂度分析，⑦从数据结构的角度设计好算法的过程。
重点和难点：
①算法的时间和空间复杂度分析，特别是递归算法的时间和空间复杂度分析，②如何设计好的算法。
2、线性表
10
线性表及其逻辑结构；线性表的顺序存储结构一顺序表；线性表的链式存储结构一单链表；线性表的链式存储结构双链表；线
性表的链式存储结构一循环链表；线性表的应用；有序表。
目标：
①线性表的逻辑结构特点和线性表抽象数据类型的描述方法，②线性表的两类存储结构设计方法以及各自的优缺点，③顺序表算法设计方法，④单链表、双链表和循环链表算法设计方法。
重点：
①顺序表、单链表、双链表和循环链表算法设计方法，②有序表的特点和有序表的归并算法设计方法。
难点：
利用线性表求解复杂问题。
3、栈和队列
8
栈的基本概念；栈的顺序存储结构-顺序栈；栈的链式存储结构-链栈；栈的应用；队列的基本概念；队列的顺序存储结构-顺序队；队列的链式存储结构-链队；队列的应用。
目标：
①栈的逻辑结构特性和栈抽象数据类型的描述方法，②栈的先进后出特点，③栈基本运算在两类存储结构下的实现算法，④栈在实际求解问题中的应用方法，⑤队列的逻辑结构特性和队列抽象数据类型的描述方法，⑥队列的先进后出特点，⑦队列基本运算在两类存储结构下的实现算法，⑧队列在实际求解问题中的应用方法。
重点：
①栈算法设计，②队列算法设计。
难点：
栈和队列在求解复杂问题中的应用。
4、串
4
串的基本概念；串的顺序存储结构-顺序串；串的链式存储结构-链串；串的模式匹配。
目标：
①串的逻辑结构特性和串抽象数据类型的描述方法，②串的两类存储结构设计方法以及各自的优缺点，③顺序串算法设计方法，④链串算法设计方法，⑤串的模式匹配算法设计方法。
重点：
①顺序串运算算法设计，②链串运算算法设计。
难点：
KMP算法。
5、递归
2
递归的基本概念；递归的执行；递归算法的设计。
目标：
①掌握递归和递归模型的概念，②递归算法的执行过程，③递归算法设计的一般步骤。
重点：
①基于递归数据结构的递归算法设计方法，②基于递归求解方法的递归算法设计方法
难点：
利用递归思想求解复杂的应用问题。
6、数组和稀疏矩阵
4
数组的基本概念；特殊矩阵的压缩存储；稀疏矩阵。
目标：
①数组的逻辑结构特性和数组抽象数据类型的描述方法，②数组的顺序存储结构及其特点，③对称矩阵、上三角矩阵、下二角矩阵和二对角矩阵的压缩存储，④稀疏矩阵的两种压缩存储方法。
重点：
各种特殊矩阵的压缩存储方法。
7、树和二叉树
12
树的基本概念；树的性质；树的基本运算；树的存储结构；二叉树的基本概念；二叉树树的性质；二叉树与树、森林之间的转换；二叉树存储结构；二叉树的基本运算及其实现；二叉树的遍历；二叉树遍历应用；二叉树的构造；线索二叉树；哈夫曼树。
目标：
①树的定义及其逻辑结构特性，②树的逻辑结构表示方法和树的性质，③树的遍历方法和树的存储结构，④二叉树的定义及其性质，⑤二叉树与树、森林之间的转换，⑥二叉树的两种存储结构和二叉树的基本运算算法设计。
⑦二叉树的遍历过程、算法设计及其应用。
⑧二叉树的构造过程，⑨线索二叉树的特点及其构造过程，⑩哈夫曼树和哈夫曼编码的构造过程。
重点：
①二叉树性质和二叉树结点计算，②二叉树的遍历
过程、算法设计及其应用。
难点：
灵活利用二叉树的遍历思路进行较复杂二叉树算法设计。
&图
10
图的基本概念；图的存储结构；图的遍历；图遍历算法的应用；生成树和取小生成树；取短路径；拓扑排序；AOE网与关键路径。
目标：
①图的定义及其逻辑结构特性，图抽象数据类型的描述方法，②图的基本术语及其含义，③图的邻接矩阵和邻接表两种主要的存储结构及其特点，④图的深度优先和广度优先遍历算法，⑤图遍历算法的应用，⑥生成树和最小生成树的定义和求最小生成树的
Prim和Kruskal算法，⑦最短路径的概念和求最短路径的Dijkstra和Flody算法，⑧拓扑排序过程，⑨关键路径的定义及其构造过程。
重点：
①图的邻接矩阵和邻接表两种主要的存储结构及其特点，②图的深度优先和广度优先遍历算法，③Prim和Kruskal算法，④Dijkstra和Flody算法。
难点：
图遍历算法的应用。
9、查找
8
查找的基本概念；线性表的查找；树表的查找；哈希表查找。
目标：
①掌握查找的概念，②线性表的顺序查找和折半查找算法，索引存储结构和分块查找方法，③二叉排序树的定义、查找和插入算法、删除过程，④平衡二叉树的特点及其调整方法，⑤B-树的定义和基本操作过程，B+的定义，⑥哈希表的定义及其特点，⑦哈希函数构造方法和解决冲突的方法，⑧各种查找方法的性能分析。
重点：
各种查找算法的实现。
难点：
各种查找方法的性能分析。
10、内排序
8
排序的基本概念；插入排序；交换排序；选择排序；归并排序；基数排序；各种内排序方法的比较和选择。
目标：
①排序的定义和相关概念，②插入排序算法，包括直接插入排序、折半插入排序和希尔排序，③交换排序算法，包括冒泡排序和快速排序，④选择排序算法，包括简单选择排序和堆排序，⑤归并排序算法，包括二路归并排序，⑥基数排序算法，包括最低位优先和最高位优先排序，⑦各种内排序方法的性能分析和比较。
重点：
各种排序算法的实现。
难点：
各种内排序方法的性能分析和比较。
11、外排序
2
外排序的基本概念；磁盘排序；磁带排序。
目标：
①外排序的基本步骤，②磁盘的特性和磁盘排序的基本步骤，③生成初始归并段的方法，④多路平衡归并过程及败者树在归并过程中的应用，⑤最佳归并树的构造过程。
⑥了解磁带排序的概念和磁带多路平衡归并和多阶段归并排序方法。
重点：
①磁盘排序的基本步骤，②最佳归并树的构造过程。
难点：
多路平衡归并过程及败者树在归并过程中的应用。
六、其他课时安排
课时类型
内容
对应能力点
要求
课时
备注
上机实验题
上机实验项目1—线性表
基本运算算法设计。
线性表算法设计
设计顺序表各种基本运算的算法，设计单链表各种基本运算的算法。
3
上机实验项目2—栈基本运算算法设计。
栈算法设计
设计顺序栈各种基本运算的算法，设计链栈各种基本运算的算法。
3
上机实验项目3—用栈求解迷宫问题
栈的应用
熟练掌握栈的特点和应用。
3
上机实验项目4—队列基本运算算法设计。
队列算法设计
设计顺序队各种基本运算的算法，设计链队各种基本运算的算法。
3
上机实验项目5—用队列求解迷宫问题
队列的应用
熟练掌握队列的特点和应用。
3
上机实验项目6—求解n皇后问题。
递归算法设计
掌握递归算法设计方法。
3
上机实验项目7—二叉树
4种遍历算法设计
二叉树遍历算法设计
掌握二叉树4种遍历算法的特点和实现过程。
3
上机实验项目8—图遍历算法设计
图遍历算法设计
掌握图的DFS和BFS遍历算法设计。
3
上机实验项目9—图中带条件的路径查找
图遍历算法设计
掌握图的DFS遍历算法设计。
3
上机实验项目10—线性表的查找算法设计
查找算法设计
掌握顺序查找和折半查找算法设计。
3
上机实验项目11—树表的
查找算法设计
查找算法设计
掌握二叉排序树算法设计。
3
上机头验项目12哈希表的查找算法设计
查找算法设计
掌握哈希表查找算法设计。
3
上机实验项目13—插入排序算法设计
内排序算法设计
掌握直接插入排序、折半插入排序、希尔排序算法设计。
3
上机实验项目14—交换排序算法设计
内排序算法设计
掌握冒泡排序、快速排序算法设计。
3
上机实验项目15—选择排序算法设计
内排序算法设计
掌握简单选择排序和堆排序算法设计。
3
上机实验项目16归并序算法设计
内排序算法设计
掌握二路归并排序算法设计。
3
综合实验题
上机实验项目1—线性表应用1:
①求集合（用单链表表示）的并、交和差运算，②求两个多项式相
线性表应用
熟练掌握线性表的各种存储结构和求解问题的算法设计。
6
加运算，③链表综合算法设计。
上机实验项目2—用二叉树表示家谱并实现相关算法
二叉树遍历算法的应用
掌握基于二叉树遍历的二叉树递归算法设计。
6
上机实验项目3—GIS中取短路径规划。
图的应用
掌握求图的最短路径的算法。
6
上机实验项目3—各种内排序算法的时间比较。
内排序的应用
掌握各种内排序算法的求解策略。
6
七、教学案例安排
案例名称
案例内容及要求
知识单元能力单元
备注
表连接问题求解
从问题描述、数据组织到运算算法设计完整过程。
线性表
用栈求解迷宫问题
从问题描述、数据组织到运算算法设计完整过程。
栈
用队列求解迷宫问题
从问题描述、数据组织到运算算法设计完整过程。
队列
二叉树递归算法设计
以二叉树的常用算法为例，说明二叉树遍历算法的通用设计方法。
二叉树
图算法设计
以图的遍历算法为例，说明求解图问题的通用设计方法。
图
八、教材及参考用书
（1）教材
数据结构教程（第5版），李春葆等，北京：
清华大学出版社，2017
（2）习题集
【1】数据结构教程（第5版）学习指导，李春葆等，北京：
清华大学出版社，2017
【2】数据结构教程（第5版）上机实验指导，李春葆等，北京：
清华大学出版社，2017
【3】新编数据结构习题与解析，清华大学出版社，李春葆等，2013.5
（3）参考用书
【1】数据结构基础，Horowitz,E.（朱仲涛译），北京：
清华大学出版社，2009
【2】数据结构，严蔚敏等，北京：
清华大学出版社，2002
【3】算法导论，Cormen,T,H,等（潘金贵等译），北京：
机械工业出版社，2006九、考核
（1）课内考核环节
考核环节名称
考核环节内容
考核知识单元
预计安排时间
考核形式
备注
第一次课堂测验
已授课知识单元所覆盖的主要知识点，尤其是重点难点
线性表、栈、队列、串、递归和数组
第8周
开卷，笔试
第二次课堂测验
已授课知识单元所覆盖的主要知识点，尤其是重点难点
树、二叉树和图
第14周
开卷，笔试
（2）期末考试
期末考试形式为笔试，一般以闭卷方式进行。
（3）课程成绩评定方法
课程成绩构成有：
期末笔试成绩、平时讨论与课后作业、随堂测试成绩、平时上机实验报告与综合程序设计实验报告。
后三项所占成绩比例加起来不低于50%
升级会员 