32学时数据结构课程的教与学（含教学大纲）
《数据结构》课程教学大纲课程代码：********。课程负责人：********。课程中文名称: 数据结构。课程英文名称：Data Structures。课程类别：专业基础课 必修。课程学分数：3。课程学时数：讲课32/48学时，上机32学时。授课对象：计算机科学与技术专业。本课程的前导课程：高级语言程序设计。本课程的后续课程：操作系统、数据库应用技术等。一、教学目的数据结构是计算机专业一门重要的专业基础课。通过本课程的学习，使得学生从数据逻辑结构、存储结构和基本运算算法设计三个层面掌握基本的数据组织和数据处理方法，能够从问题出发设计面向数据结构的求解算法，并能够对算法进行时间复杂度与空间复杂度分析。为后续课程如操作系统等课程学习打下基础。二、教学要求通过讲授和上机实验，使学生了解《数据结构》的原理和特点。掌握线性表、栈和队列、串、数组和稀疏矩阵、树和二叉树、图、查找和排序等基本数据结构及其相关算法的设计。具备一定的利用数据结构方法求解实际问题的能力。三、课程知识点知识单元知识点名称知识点内容知识点类型备注数据结构概述数据结构的基本概念认识数据结构的定义、包括数据逻辑结构、存储结构和运算的3个层次。一般知识点算法的基本概念认识算法的定义和5个基本特性。重要知识点算法描述认识用高级语言如C/C++描述算法的基本方法。一般知识点自我学习算法分析掌握算法的时间复杂度和空间复杂度分析方法。重要知识点数据结构+算法=程序认识从数据结构角度求解问题的基本步骤。重要知识点线性表线性表及其逻辑结构认识线性表的定义和线性表的基本运算。一般知识点线性表的顺序存储结构—顺序表掌握顺序表的存储结构特点和顺序表基本运算的实现。重要知识点线性表的链式存储结构—单链表掌握单链表的存储结构特点、单链表的插入和删除节点操作、单链表的建表方法、以及单链表基本运算的实现。重要知识点线性表的链式存储结构—双链表掌握双链表的存储结构特点、双链表的插入和删除节点操作、双链表的建表方法、以及双链表基本运算的实现。重要知识点线性表的链式存储结构—循环链表掌握循环链表的存储结构特点、循环链表的插入和删除节点操作、循环链表的建表方法、以及循环链表基本运算的实现。重要知识点线性表的应用掌握从求解问题描述、数据组织到运算算法设计完整过程。难度知识点栈栈的基本概念了解栈的定义、栈的逻辑结构特性和栈的基本运算。一般知识点栈的顺序存储结构-顺序栈掌握顺序栈的存储结构特点和顺序栈基本运算的实现。重要知识点栈的链式存储结构-链栈掌握链栈的存储结构特点和链栈基本运算的实现。重要知识点栈的应用了解栈在表达式求值中的应用。难度知识点队列队列的基本概念了解队列的定义、队列的逻辑结构特性和队列的基本运算。一般知识点队列的顺序存储结构-顺序队掌握顺序队的存储结构特点和顺序队基本运算的实现。重要知识点队列的链式存储结构-链队掌握链队的存储结构特点和链队基本运算的实现。重要知识点队列的应用了解队列在病人看病问题中的应用。难度知识点串串的基本概念了解串的定义、串的逻辑结构特性和串的基本运算。一般知识点串的顺序存储结构-顺序串掌握顺序串的存储结构特点和顺序串基本运算的实现。一般知识点串的链式存储结构-链串掌握链串的存储结构特点和链串基本运算的实现。一般知识点数组和稀疏矩阵数组的基本概念了解数组的定义和数组的存储结构。一般知识点特殊矩阵的压缩存储了解对称矩阵、上下三角矩阵和对角矩阵的压缩存储。重要知识点稀疏矩阵了解稀疏矩阵的特点、稀疏矩阵的三元组表示和十字链表表示。一般知识点树树的基本概念了解树的定义、树的逻辑表示方法和树的基本术语。一般知识点树的性质了解树的4个性质及其应用。一般知识点树的基本运算掌握树的先根遍历、后根遍历和层次遍历过程。一般知识点树的存储结构掌握树的双亲存储结构、孩子链存储结构和孩子兄弟链存储结构以及特点。一般知识点二叉树二叉树的基本概念了解二叉树、满二叉树和完全二叉树的定义、二叉树的逻辑表示方法和二叉树的基本术语。一般知识点二叉树树的性质了解二叉树树的5个性质及其应用。重要知识点二叉树与树、森林之间的转换了解森林、树转换为二叉树以及二叉树还原为森林、树的过程。一般知识点二叉树存储结构掌握二叉树的顺序存储结构和二叉树的链式存储结构。重要知识点二叉树的基本运算及其实现掌握二叉树的基本运算及其实现过程。重要知识点二叉树的遍历掌握二叉树的先序遍历、中序遍历、后序遍历和层次遍历算法设计，了解先序遍历、中序遍历和后序遍历非递归算法设计。重要知识点二叉树遍历应用掌握二叉树的4种遍历在二叉树算法设计中的应用。难度知识点二叉树的构造掌握由先序遍历、中序遍历序列构造二叉树和由后序遍历、中序遍历序列构造二叉树的过程。一般知识点线索二叉树了解线索二叉树的概念、线索二叉树的构造和遍历过程。一般知识点哈夫曼树掌握哈夫曼树的概念、构造哈夫曼树和产生哈夫曼编码的过程。一般知识点图图的基本概念了解图的定义和图的基本术语。一般知识点图的存储结构掌握图的邻接矩阵存储方法和邻接表表存储方法。重要知识点图的遍历掌握图深度优先搜索遍历和广度优先搜索遍历算法。重要知识点图遍历算法的应用掌握图的两种遍历算法在图算法设计中的应用。难度知识点生成树和最小生成树了解生成树和最小生成树的概念，掌握构造最小生成树的普里姆算法和克鲁斯卡尔算法。重要知识点最短路径了解最短路径的概念，掌握构造最短路径的狄克斯特拉算法和弗洛伊德算法。重要知识点拓扑排序了解拓扑排序的概念和拓扑排序过程。一般知识点AOE网与关键路径了解AOE网与关键路径的概念、求解关键路径的过程。一般知识点查找查找的基本概念查找表和平均查找长度ASL的定义。一般知识点线性表的查找掌握顺序查找、折半查找和分块查找算法设计和算法分析。重要知识点树表的查找掌握二叉排序树的算法设计。重要知识点了解平衡二叉树、B和B+树的组织和查找过程。一般知识点哈希表查找掌握哈希表的基本概念、哈希函数构造方法、哈希冲突解决方法和哈希查找过程。重要知识点排序排序的基本概念了解排序算法的稳定性、排序算法的分类。一般知识点插入排序掌握直接插入排序算法的思路、排序算法和算法分析，折半插入排序算法的思路、排序算法和算法分析，希尔排序算法的思路、排序算法和算法分析。重要知识点交换排序掌握冒泡排序算法的思路、排序算法和算法分析，快速排序算法的思路、排序算法和算法分析。重要知识点选择排序掌握直接选择排序算法的思路、排序算法和算法分析，堆排序算法的思路、排序算法和算法分析。重要知识点归并排序掌握归并排序算法的思路，二路归并算法和算法分析。重要知识点基数排序掌握基数排序算法的思路、排序算法和算法分析。重要知识点各种内排序方法的比较和选择掌握各种内排序方法时间和空间因素的比较和分析。难度知识点外排序的基本概念了解外排序概念和外排序的一般过程。一般知识点磁盘排序掌握磁盘排序中生成初始归并段、多路平衡归并和构造最佳归并树的过程。重要知识点四、课程能力点能力单元能力点名称能力点要求能力点类型备注面向数据结构的算法设计数据结构算法设计流程掌握从数据逻辑结构到存储结构的映射关系，算法的时间复杂度和空间复杂度分析，使学生能够从数据结构角度出发，掌握从逻辑结构→存储结构→基本运算算法设计的流程，并通过设计合理的存储结构来设计出好算法的过程。思维能力点线性表线性表算法设计掌握线性表的顺序存储结构和链式存储结构中线性表基本运算算法设计方法。设计能力点线性表应用掌握线性表的逻辑结构→存储结构→运算算法设计的主线，利用线性表求解实际应用问题。设计能力点栈和队列栈算法设计掌握栈的顺序存储结构和链式存储结构中栈基本运算算法设计方法。设计能力点队列算法设计掌握队列的顺序存储结构和链式存储结构中队列基本运算算法设计方法。设计能力点栈的应用掌握栈在实际求解问题中的应用方法。设计能力点队列的应用掌握队列在实际求解问题中的应用方法。设计能力点二叉树二叉树结构掌握二叉树、满二叉树和完全二叉树的性质和结点计算。思维能力点二叉树遍历算法设计掌握二叉树4种遍历算法设计设计能力点二叉树遍历算法的应用掌握基于二叉树遍历的二叉树递归算法设计设计能力点图图遍历算法设计掌握基于两种图遍历的图算法设计设计能力点图的应用掌握求最小生成树的Prim和Kruskal算法和求最短路径的Dijkstra和Flody算法。设计能力点查找查找算法设计掌握顺序查找、折半查找、二叉排序树和哈希表查找算法。思维能力点查找的应用基于不同的数据结构选择合适的查找算法求解问题。设计能力点排序内排序算法设计掌握直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、二路归并排序和基数排序算法。思维能力点内排序的应用基于不同的要求选择合适的内排序算法求解问题。设计能力点五、授课课时安排（32/48课时）知识单元授课课时涵盖知识点情况授课目标重难点要求备注1、绪论2/2数据结构的基本概念；算法的基本概念；算法描述；算法分析；数据结构+算法=程序目标：①数据结构的基本概念，②数据逻辑结构和存储结构的映射关系，③数据类型和数据结构的区别和联系，④利用抽象数据类型表述求解问题的方法，⑤算法的特性和采用C/C++语言描述算法的方法，⑥算法设计目标和分析方法，包括时间复杂度和空间复杂度分析，⑦从数据结构的角度设计好算法的过程。重点和难点：①算法的时间和空间复杂度分析，特别是递归算法的时间和空间复杂度分析，②如何设计好的算法。2、线性表6/8线性表及其逻辑结构；线性表的顺序存储结构—顺序表；线性表的链式存储结构—单链表；线性表的链式存储结构—双链表；线性表的链式存储结构—循环链表；线性表的应用；有序表。目标：①线性表的逻辑结构特点和线性表抽象数据类型的描述方法，②线性表的两类存储结构设计方法以及各自的优缺点，③顺序表算法设计方法，④单链表、双链表和循环链表算法设计方法。重点：顺序表、单链表、双链表和循环链表算法设计方法。难点：利用线性表求解复杂问题。3、栈和队列4/6栈的基本概念；栈的顺序存储结构-顺序栈；栈的链式存储结构-链栈；栈的应用；队列的基本概念；队列的顺序存储结构-顺序队；队列的链式存储结构-链队；队列的应用。目标：①栈的逻辑结构特性和栈抽象数据类型的描述方法，②栈的先进后出特点，③栈基本运算在两类存储结构下的实现算法，④栈在实际求解问题中的应用方法，⑤队列的逻辑结构特性和队列抽象数据类型的描述方法，⑥队列的先进后出特点，⑦队列基本运算在两类存储结构下的实现算法，⑧队列在实际求解问题中的应用方法。重点：①栈算法设计，②队列算法设计。难点：栈和队列在求解复杂问题中的应用。4、串2/2串的基本概念；串的顺序存储结构-顺序串；串的链式存储结构-链串。目标：①串的逻辑结构特性和串抽象数据类型的描述方法，②串的两类存储结构设计方法以及各自的优缺点，③顺序串算法设计方法，④链串算法设计方法。重点：①顺序串运算算法设计，②链串运算算法设计。5、数组和稀疏矩阵2/2数组的基本概念；特殊矩阵的压缩存储；稀疏矩阵。目标：①数组的逻辑结构特性和数组抽象数据类型的描述方法，②数组的顺序存储结构及其特点，③对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储，④稀疏矩阵的两种压缩存储方法。重点：各种特殊矩阵的压缩存储方法。6、树和二叉树6/8树的基本概念；树的性质；树的基本运算；树的存储结构；二叉树的基本概念；二叉树树的性质；二叉树与树、森林之间的转换；二叉树存储结构；二叉树的基本运算及其实现；二叉树的遍历；二叉树遍历应用；二叉树的构造；线索二叉树；哈夫曼树。目标：①树的定义及其逻辑结构特性，②树的逻辑结构表示方法和树的性质，③树的遍历方法和树的存储结构，④二叉树的定义及其性质，⑤二叉树与树、森林之间的转换，⑥二叉树的两种存储结构和二叉树的基本运算算法设计。⑦二叉树的遍历过程、算法设计及其应用。⑧二叉树的构造过程，⑨线索二叉树的特点及其构造过程，⑩哈夫曼树和哈夫曼编码的构造过程。重点：①二叉树性质和二叉树结点计算，② 二叉树的遍历过程、算法设计及其应用。难点：灵活利用二叉树的遍历思路进行较复杂二叉树算法设计。7、图4/8图的基本概念；图的存储结构；图的遍历；图遍历算法的应用；生成树和最小生成树；最短路径；拓扑排序；AOE网与关键路径。目标：①图的定义及其逻辑结构特性，图抽象数据类型的描述方法，②图的基本术语及其含义，③图的邻接矩阵和邻接表两种主要的存储结构及其特点，④图的深度优先和广度优先遍历算法，⑤图遍历算法的应用，⑥生成树和最小生成树的定义和求最小生成树的Prim和Kruskal算法，⑦最短路径的概念和求最短路径的Dijkstra和Flody算法，⑧拓扑排序过程，⑨关键路径的定义及其构造过程。重点：①图的邻接矩阵和邻接表两种主要的存储结构及其特点，②图的深度优先和广度优先遍历算法，③Prim和Kruskal算法，④Dijkstra和Flody算法。难点：图遍历算法的应用。8、查找3/6查找的基本概念；线性表的查找；树表的查找；哈希表查找。目标：①掌握查找的概念，②线性表的顺序查找和折半查找算法，索引存储结构和分块查找方法，③二叉排序树的定义、查找和插入算法、删除过程，④平衡二叉树的特点及其调整方法，⑤B-树的定义和基本操作过程，B+的定义，⑥哈希表的定义及其特点，⑦哈希函数构造方法和解决冲突的方法，⑧各种查找方法的性能分析。重点：各种查找算法的实现。难点：各种查找方法的性能分析。9、排序3/6排序的基本概念；插入排序；交换排序；选择排序；归并排序；基数排序；各种内排序方法的比较和选择。目标：①排序的定义和相关概念，②插入排序算法，包括直接插入排序、折半插入排序和希尔排序，③交换排序算法，包括冒泡排序和快速排序，④选择排序算法，包括简单选择排序和堆排序，⑤归并排序算法，包括二路归并排序，⑥基数排序算法，包括最低位优先和最高位优先排序，⑦各种内排序方法的性能分析和比较。⑧外排序的基本过程。重点：各种排序算法的实现。难点：各种内排序方法的性能分析和比较。六、上机课时安排（32课时）课时类型内容对应能力点要求课时备注上机实验题上机实验项目1－线性表基本运算算法设计。线性表算法设计设计顺序表各种基本运算的算法，设计单链表各种基本运算的算法。2上机实验项目2－栈基本运算算法设计。栈算法设计设计顺序栈各种基本运算的算法，设计链栈各种基本运算的算法。2上机实验项目3－队列基本运算算法设计。队列算法设计设计顺序队各种基本运算的算法，设计链队各种基本运算的算法。2上机实验项目4－求解n皇后问题。递归算法设计掌握递归算法设计方法。2上机实验项目5－二叉树4种遍历算法设计二叉树遍历算法设计掌握二叉树4种遍历算法的特点和实现过程。2上机实验项目6—图遍历算法设计图遍历算法设计掌握图的DFS和BFS遍历算法设计。2上机实验项目7—图中带条件的路径查找图遍历算法设计掌握图的DFS遍历算法设计。2上机实验项目8—线性表的查找算法设计查找算法设计掌握顺序查找和折半查找算法设计。2上机实验项目9—树表的查找算法设计查找算法设计掌握二叉排序树算法设计。2上机实验项目10—哈希表的查找算法设计查找算法设计掌握哈希表查找算法设计。2上机实验项目11—插入排序算法设计内排序算法设计掌握直接插入排序、折半插入排序、希尔排序算法设计。1上机实验项目12—交换排序算法设计内排序算法设计掌握冒泡排序、快速排序算法设计。1上机实验项目13—选择排序算法设计内排序算法设计掌握简单选择排序和堆排序算法设计。1上机实验项目14—归并序算法设计内排序算法设计掌握二路归并排序算法设计。1综合实验题上机实验项目1－线性表应用1：①求集合（用单链表表示）的并、交和差运算，② 求两个多项式相加运算，③ 链表综合算法设计。线性表应用熟练掌握线性表的各种存储结构和求解问题的算法设计。3上机实验项目2－用二叉树表示家谱并实现相关算法二叉树遍历算法的应用掌握基于二叉树遍历的二叉树递归算法设计。3上机实验项目3－GIS中最短路径规划。图的应用掌握求图的最短路径的算法。3上机实验项目3－各种内排序算法的时间比较。内排序的应用掌握各种内排序算法的求解策略。3七、教学案例安排案例名称案例内容及要求知识单元能力单元备注求解两个多项式相加运算问题从问题描述、数据组织到运算算法设计完整过程。线性表用栈求表达式值问题从问题描述、数据组织到运算算法设计完整过程。栈用队列求解病人看病问题从问题描述、数据组织到运算算法设计完整过程。队列二叉树递归算法设计以二叉树的常用算法为例，说明二叉树遍历算法的通用设计方法。二叉树图算法设计以图的遍历算法为例，说明求解图问题的通用设计方法。图八、考核（1）课内考核环节（2）期末考试：期末考试形式为笔试，一般以闭卷方式进行。（3）课程成绩评定方法：课程成绩构成有：期末笔试成绩、平时讨论与课后作业、随堂测试成绩、平时上机实验报告与综合程序设计实验报告。后三项所占成绩比例加起来不低于30%。九、教材及参考用书（1）教材数据结构简明教程（第2版），李春葆等，北京：清华大学出版社，2019（2）习题集【1】数据结构学习与实验指导，李春葆等，北京：清华大学出版社，2019【2】新编数据结构习题与解析（第2版），清华大学出版社，李春葆等，2019扫描，优惠购书提供PPT课件，源码，答案，上机，教案，教学大纲，20小时微课视频讲解本书适合32/48学时，本书内容包括概论、线性表、栈和队列、串、数组和稀疏矩阵、树和二叉树、图、查找和排序，附录中给出了书中全部算法代码清单和2018年全国计算机专业数据结构考研大纲。 本书具有概念清楚、表述明晰、示例丰富、图示准确和内容完整等特点，尤其注重知识点之间结构关系的展示和通用算法设计方法的提炼。每个知识点都提供了配套的微课视频（共20小时）。如果需要72学时的教材，点击下面图片，可以查看相对应的教学大纲
——相关图书推荐——