《数据结构》课程教学大纲
、
课程中文名称:数据结构。
课程英文名称：DataStructures。
课程类别：专业基础课必修。
课程学分数：3（16学时为1学分）
课程学时数：讲课32学时，上机16学时。
授课对象：计算机科学与技术专业。
本课程的前导课程：高级语言程序设计。
本课程的后续课程：操作系统、数据库应用技术等。
一、教学目的
数据结构课程是计算机专业一门重要的专业基础课。通过本课程的学习，使得学生从数据逻辑结构、存储结构和基本运算算法设计三个层面掌握基本的数据组织和数据处理方法，能够从问题出发设计面向数据结构的求解算法，具有基本的算法时间复杂度和空间复杂度分析能力，为后续课程如操作系统等课程学习打下较好的基础。
二、教学要求
通过讲授和上机实验，使学生领会数据结构的基本原理，掌握线性表、栈和队列、串、数组和稀疏矩阵、树和二叉树、图、查找和排序等基本数据结构及其相关算法设计方法，具备较好的数据组织、数据存储和数据处理能力。
三、授课课时安排（48学时）
知识单元
涵盖知识点情况*
知识点学时
小计
1、绪论
1.1什么是数据结构
1.2算法及其描述
1.3Python简介
1
2
1.4算法分析：
①算法时间复杂度分析；②算法空间复杂度分析
1
2、线性表
2.1线性表的定义
2.2线性表的顺序存储结构：
①顺序表以及线性表基本运算算法在顺序表中的实现；②顺序表的应用算法设计示例
2
4
2.3线性表的链式存储结构：
①单链表以及线性表基本运算算法在单链表中的实现；②单链表的应用算法设计示例；③双链表以及线性表基本运算算法在双链表中的实现；④双链表的应用算法设计示例
2
3、栈和队列
3.1栈：
①栈的定义；②顺序栈及其实现；③顺序栈的应用算法设计示例；④链栈及其实现；⑤链栈的应用算法设计示例
2
4
3.2队列：
①队列的定义；②顺序队及其实现；③顺序队的应用算法设计示例；④链队及其实现；⑤链队的应用算法设计示例
2
4、串和数组
4.1串
①串的定义；②串的存储结构—顺序串和链串
1
2
4.2数组：
①数组的基本概念；②特殊矩阵的压缩存储
1
5、树和二叉树
6.1树：
①树的定义和逻辑表示；②树的基本术语；③树的性质；④树的基本运算；⑤树的存储结构
1
6
6.2二叉树：
①二叉树的概念；②二叉树的性质；③二叉树存储结构
1
6.3二叉树先序、中序和后序遍历：
①二叉树遍历的概念；②先序、中序和后序遍历递归算法
1
6.4二叉树的层次遍历：
①层次遍历过程；②层次遍历算法设计
1
6.5二叉树的构造
6.7哈夫曼树
6.8二叉树与树、森林之间的转换
2
6、图
7.1图的基本概念
7.2图的存储结构：
①邻接矩阵；②邻接表
1
5
7.3图的遍历：
①图遍历的概念；②深度优先遍历；③广度优先遍历
1
7.4生成树和最小生成树：
①生成树和最小生成树的概念；②普里姆算法；③克鲁斯卡尔算法
1.5
7.5最短路径：
①最短路径的概念；②狄克斯特拉算法；③弗洛伊德算法
1.5
7、查找
8.1查找的基本概念
8.2线性表的查找：
①顺序查找；②折半查找；③索引存储结构和分块查找
2
5
8.3树表的查找：
①二叉排序树；②平衡二叉树
2
8.4哈希表查找：
①哈希表的基本概念；②哈希函数构造方法；③哈希冲突解决方法；④哈希表查找及性能分析
1
8、排序
9.1排序的基本概念
9.2插入排序：
①直接插入排序；②折半插入排序；③希尔排序
1
4
9.3交换排序：
①冒泡排序；②快速排序
1
9.4选择排序：
①简单选择排序；②堆排序
1
9.5归并排序
9.6基数排序
1
*教材中所有带"*"的内容均为提高知识点，不作为课堂讲授内容以减少课堂学时，删除递归一章的课堂讲授。三、授课课时安排（48学时）
知识单元
涵盖知识点情况*
知识点学时
小计
1、绪论
1.1什么是数据结构
1.2算法及其描述
1.3Python简介
1
2
1.4算法分析：
①算法时间复杂度分析；②算法空间复杂度分析
1
2、线性表
2.1线性表的定义
2.2线性表的顺序存储结构：
①顺序表以及线性表基本运算算法在顺序表中的实现；②顺序表的应用算法设计示例
2
6
2.3线性表的链式存储结构：
①单链表以及线性表基本运算算法在单链表中的实现；②单链表的应用算法设计示例；③双链表以及线性表基本运算算法在双链表中的实现；④双链表的应用算法设计示例；⑤循环链表
2
2.4顺序表和链表的比较
2.5线性表的应用：
求解两个多项式相加问题
2
3、栈和队列
3.1栈：
①栈的定义；②顺序栈及其实现；③顺序栈的应用算法设计示例；④链栈及其实现；⑤链栈的应用算法设计示例
2
6
⑦栈的综合应用（用栈求解简单表达式求值问题，用栈求解迷宫问题）
1
3.2队列：
①队列的定义；②顺序队及其实现；③顺序队的应用算法设计示例；④链队及其实现；⑤链队的应用算法设计示例
2
⑦队列的综合应用（用队列求解迷宫问题）
1
4、串和数组
4.1串
①串的定义；②串的存储结构—顺序串和链串；③串的模式匹配（BF算法和KMP算法）
2
4
4.2数组：
①数组的基本概念；②特殊矩阵的压缩存储；③稀疏矩阵
2
5、递归
5.1什么是递归
①递归的定义；②何时使用递归；③递归模型；④递归的执行过程；⑤递归算法的时空分析
1
2
5.2递归算法的设计：
①递归算法设计的步骤；②基于递归数据结构的递归算法设计；③基于归纳方法的递归算法设计
1
6、树和二叉树
6.1树：
①树的定义和逻辑表示；②树的基本术语；③树的性质；④树的基本运算；⑤树的存储结构
1
7
6.2二叉树：
①二叉树的概念；②二叉树的性质；③二叉树存储结构；④二叉树的递归算法设计；⑤二叉树的基本运算及其实现
2
6.3二叉树先序、中序和后序遍历：
①二叉树遍历的概念；②先序、中序和后序遍历递归算法；③递归遍历算法的应用
1
6.4二叉树的层次遍历：
①层次遍历过程；②层次遍历算法设计；③层次遍历算法的应用
1
6.5二叉树的构造
6.6线索二叉树
1
6.7哈夫曼树
6.8二叉树与树、森林之间的转换
1
7、图
7.1图的基本概念
7.2图的存储结构：
①邻接矩阵；②邻接表
1
7
7.3图的遍历：
①图遍历的概念；②深度优先遍历；③广度优先遍历；④非连通图的遍历；⑤图遍历算法的应用
2
7.4生成树和最小生成树：
①生成树和最小生成树的概念；②普里姆算法；③克鲁斯卡尔算法
1.5
7.5最短路径：
①最短路径的概念；②狄克斯特拉算法；③弗洛伊德算法
1.5
7.6拓扑排序
7.7AOE网与关键路径
1
8、查找
8.1查找的基本概念
8.2线性表的查找：
①顺序查找；②折半查找；③索引存储结构和分块查找
2
7
8.3树表的查找：
①二叉排序树；②平衡二叉树；③B-树和B+树
3
8.4哈希表查找：
①哈希表的基本概念；②哈希函数构造方法；③哈希冲突解决方法；④哈希表查找及性能分析
2
9、排序
9.1排序的基本概念
9.2插入排序：
①直接插入排序；②折半插入排序；③希尔排序
2
6
9.3交换排序：
①冒泡排序；②快速排序
1
9.4选择排序：
①简单选择排序；②堆排序
1
9.5归并排序：
①自底向上的二路归并排序；②自顶向下的二路归并排序
9.6基数排序
9.7各种内排序方法的比较和选择
2
10、复习
课程知识点归纳和总结
1
1
*教材中所有带"*"的内容均为提高知识点，不作为课堂讲授内容以减少课堂学时。三、授课课时安排（60学时）
知识单元
涵盖知识点情况*
知识点学时
小计
1、绪论
1.1什么是数据结构
1.2算法及其描述
1
4
1.3Python简介
1.5
1.4算法分析：
①算法时间复杂度分析；②算法空间复杂度分析
1.5数据结构的目标
1.5
2、线性表
2.1线性表的定义
2.2线性表的顺序存储结构：
①顺序表以及线性表基本运算算法在顺序表中的实现；②顺序表的应用算法设计示例
3
8
2.3线性表的链式存储结构：
①单链表以及线性表基本运算算法在单链表中的实现；②单链表的应用算法设计示例；③双链表以及线性表基本运算算法在双链表中的实现；④双链表的应用算法设计示例；⑤循环链表
3
2.4顺序表和链表的比较
2.5线性表的应用：
求解两个多项式相加问题
2
3、栈和队列
3.1栈：
①栈的定义；②顺序栈及其实现；③顺序栈的应用算法设计示例；④链栈及其实现；⑤链栈的应用算法设计示例
2
6
⑥栈的综合应用（用栈求解简单表达式求值问题，用栈求解迷宫问题）
1
3.2队列：
①队列的定义；②顺序队及其实现；③顺序队的应用算法设计示例；④链队及其实现；⑤链队的应用算法设计示例；⑥Python中的双端队列deque
2
⑦队列的综合应用（用队列求解迷宫问题）；⑧优先队列（堆）
1
4、串和数组
4.1串
①串的定义；②串的存储结构—顺序串和链串；③串的模式匹配（BF算法和KMP算法）
3
5
4.2数组：
①数组的基本概念；②特殊矩阵的压缩存储；③稀疏矩阵
2
5、递归
5.1什么是递归：
①递归的定义；②何时使用递归；③递归模型；④递归的执行过程；⑤递归算法的时空分析
1
3
5.2递归算法的设计：
①递归算法设计的步骤；②基于递归数据结构的递归算法设计；③基于归纳方法的递归算法设计
2
6、树和二叉树
6.1树：
①树的定义和逻辑表示；②树的基本术语；③树的性质；④树的基本运算；⑤树的存储结构
1
9
6.2二叉树：
①二叉树的概念；②二叉树的性质；③二叉树存储结构；④二叉树的递归算法设计；⑤二叉树的基本运算及其实现
2
6.3二叉树先序、中序和后序遍历：
①二叉树遍历的概念；②先序、中序和后序遍历递归算法；③递归遍历算法的应用；④先序、中序和后序遍历非递归算法
2
6.4二叉树的层次遍历：
①层次遍历过程；②层次遍历算法设计；③层次遍历算法的应用
1
6.5二叉树的构造
6.6线索二叉树
1
6.7哈夫曼树
6.8二叉树与树、森林之间的转换
1
6.9并查集
1
7、图
7.1图的基本概念
7.2图的存储结构：
①邻接矩阵；②邻接表
1
8
7.3图的遍历：
①图遍历的概念；②深度优先遍历；③广度优先遍历；④非连通图的遍历；⑤图遍历算法的应用
2.5
7.4生成树和最小生成树：
①生成树和最小生成树的概念；②普里姆算法；③克鲁斯卡尔算法
1.5
7.5最短路径：
①最短路径的概念；②狄克斯特拉算法；③弗洛伊德算法
1.5
7.6拓扑排序
7.7AOE网与关键路径
1.5
8、查找
8.1查找的基本概念
8.2线性表的查找：
①顺序查找；②折半查找；③索引存储结构和分块查找
2
7
8.3树表的查找：
①二叉排序树；②平衡二叉树；③B树；④B+树
3
8.4哈希表查找：
①哈希表的基本概念；②哈希函数构造方法；③哈希冲突解决方法；④哈希表查找及性能分析
2
9、排序
9.1排序的基本概念
9.2插入排序：
①直接插入排序；②折半插入排序；③希尔排序
2
8
9.3交换排序：
①冒泡排序；②快速排序
1
9.4选择排序：
①简单选择排序；②堆排序
1
9.5归并排序：
①自底向上的二路归并排序；②自顶向下的二路归并排序
9.6基数排序
9.7各种内排序方法的比较和选择
2
10.8外排序：
①生成初始归并段的方法；②多路归并方法
2
10、复习
课程知识点归纳和总结
2
2
*教材中部分带"*"的内容作为提高知识点，不作为课堂讲授内容。
四、上机课时安排（16课时）
知识单元
实验内容
学时
1、线性表
上机实验题**
3
2、栈和队列
上机实验题
3
3、树和二叉树
上机实验题
3
4、图
上机实验题
3
5、查找和排序
上机实验题
4
**上机实验题均来自于教材，教师可以根据学生的情况选择相应的题目。五、教材及参考用书本书提供多页PPT课件，大纲，源码，答案，上机，40小时视频，教案，题库（多道题目）本书配套《数据结构教程（Python语言描述)学习与上机实验指导》（ISBN
）
本书配套视频演示
六、考核
（1）期末考试：期末考试形式为笔试，一般以闭卷方式进行。
（2）课程成绩评定方法：期末考试成绩、课后作业、上机实验（含实验报告）和其他。后三项所占成绩比例加起来不低于30%。
