数据结构大纲(32学时)

第3页《数据结构》课程教学大纲课程代码：********。课程负责人：********。课程中文名称:数据结构。课程英文名称：DataStructures。课程类别：专业基础课必修。课程学分数：3（16学时为1学分）课程学时数：讲课32学时，上机16学时。授课对象：计算机科学与技术专业，软件工程，人工智能。本课程的前导课程：高级语言程序设计。本课程的后续课程：操作系统、数据库应用技术等。一、教学目的数据结构课程是计算机专业一门重要的专业基础课。通过本课程的学习，使得学生从数据逻辑结构、存储结构和基本运算算法设计三个层面掌握基本的数据组织和数据处理方法，能够从问题出发设计面向数据结构的求解算法，具有基本的算法时间复杂度和空间复杂度分析能力，为后续课程如操作系统等课程学习打下较好的基础。二、教学要求通过讲授和上机实验，使学生领会数据结构的基本原理，掌握线性表、栈和队列、串、数组和稀疏矩阵、树和二叉树、图、查找和排序等基本数据结构及其相关算法设计方法，具备较好的数据组织、数据存储和数据处理能力。三、授课课时安排（48学时）知识单元涵盖知识点情况*知识点学时小计1、绪论1.1什么是数据结构1.2算法及其描述1.3Python简介121.4算法分析：①算法时间复杂度分析；②算法空间复杂度分析12、线性表2.1线性表的定义2.2线性表的顺序存储结构：①顺序表以及线性表基本运算算法在顺序表中的实现；②顺序表的应用算法设计示例242.3线性表的链式存储结构：①单链表以及线性表基本运算算法在单链表中的实现；②单链表的应用算法设计示例；③双链表以及线性表基本运算算法在双链表中的实现；④双链表的应用算法设计示例23、栈和队列3.1栈：①栈的定义；②顺序栈及其实现；③顺序栈的应用算法设计示例；④链栈及其实现；⑤链栈的应用算法设计示例243.2队列：①队列的定义；②顺序队及其实现；③顺序队的应用算法设计示例；④链队及其实现；⑤链队的应用算法设计示例24、串和数组4.1串①串的定义；②串的存储结构—顺序串和链串124.2数组：①数组的基本概念；②特殊矩阵的压缩存储15、树和二叉树6.1树：①树的定义和逻辑表示；②树的基本术语；③树的性质；④树的基本运算；⑤树的存储结构166.2二叉树：①二叉树的概念；②二叉树的性质；③二叉树存储结构16.3二叉树先序、中序和后序遍历：①二叉树遍历的概念；②先序、中序和后序遍历递归算法16.4二叉树的层次遍历：①层次遍历过程；②层次遍历算法设计16.5二叉树的构造6.7哈夫曼树6.8二叉树与树、森林之间的转换26、图7.1图的基本概念7.2图的存储结构：①邻接矩阵；②邻接表157.3图的遍历：①图遍历的概念；②深度优先遍历；③广度优先遍历17.4生成树和最小生成树：①生成树和最小生成树的概念；②普里姆算法；③克鲁斯卡尔算法1.57.5最短路径：①最短路径的概念；②狄克斯特拉算法；③弗洛伊德算法1.57、查找8.1查找的基本概念8.2线性表的查找：①顺序查找；②折半查找；③索引存储结构和分块查找258.3树表的查找：①二叉排序树；②平衡二叉树28.4哈希表查找：①哈希表的基本概念；②哈希函数构造方法；③哈希冲突解决方法；④哈希表查找及性能分析18、排序9.1排序的基本概念9.2插入排序：①直接插入排序；②折半插入排序；③希尔排序149.3交换排序：①冒泡排序；②快速排序19.4选择排序：①简单选择排序；②堆排序19.5归并排序9.6基数排序1*教材中所有带"*"的内容均为提高知识点，不作为课堂讲授内容以减少课堂学时，删除递归一章的课堂讲授。四、上机课时安排（16课时）知识单元实验内容学时1、线性表上机实验题**32、栈和队列上机实验题33、树和二叉树上机实验题34、图上机实验题35、查找和排序上机实验题4**上机实验题均来自于教材，教师可以根据学生的情况选择相应的题目。五、教材及参考用书（1）教材数据结构教程（Python语言描述）（第2版），李春葆等，北京：清华大学出版社，2024（2）实验指导书数据结构教程学习与上机实验指导，李春葆等，北京：清华大学出版社，2024（3）参考用书[1]SedgewickR.，WayneK.著，谢路云译.算法（第4版）.人民邮电出版社，2012[2]李文辉等.程序设计导引及在线实践（第2版）.清华大