数据结构 课程教学大纲.docxVIP

数据结构 课程教学大纲 lbrack;数据结构rsqb;课程教学大纲 《数据结构》课程教学大纲--2021版 一、课程基本信息 课程名称：数据结构 英文名称：Data Structure 课程编码: 11107C/11207C 课程类别：专业主干课 总学时: 64学时（含实验16学时） 总学分: 4 适用专业：计算机科学与技术/网络工程方向 先修课程：高级语言程序设计，离散数学，概率论与数理统计 开课系部: 计算机科学与技术系 二、课程的性质和任务 《数据结构》是计算机科学与技术专业的一门专业必修课程。它系统地介绍线性表、栈、队列、字符串、数组、广义表、树、二叉树、图、查找表等常用数据结构的基本概念、操作及其典型应用例子。在知识方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法，使学生了解数据对象的特性，数据组织的基本方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。通过学习，初步具备分析问题、解决问题的能力，养成良好的程序设计风格，积聚和提高基本的分析设计能力，为后续课程的学习打下坚实的基础。 三、课程教学基本要求 （一）理论教学内容和基本要求 第一章绪论? 数据结构的基本概念；算法设计；时间和空间复杂度? 本章知识点：理解相关的基本概念；掌握算法五大要素；掌握计算语句频度和估算算法时间复杂度的方法。? 重点：基本概念 难点：算法的时间和空间复杂度，数据结构的概念 第二章线性表? 线性表的逻辑结构；线性表的存储结构及操作的实现；一元多项式的表示；习题讨论课 本章知识点：掌握线性表的逻辑结构、线性表的存储结构、线性表在顺序结构和链式结构上实现基本操作的方法；理解从时间和空间复杂度的角度比较线性表两种存储结构的不同特点及其适用场合。重点：线性表的概念 难点：线性表的表示及实现 第三章栈和队列? 栈的定义，表示及实现；表达式求值；栈与递归过程；队列的定义，表示及实现； 本章知识点：了解栈和队列的特点；掌握在两种存储结构上栈的基本操作的实现；掌握循环队列和链队列的基本运算；掌握递归算法执行过程中栈状态的变化过程。? 重点：栈和队列的表示和实现 难点：循环队列 第四章串? 串的逻辑结构，存储结构；串的应用； 本章知识点：理解串的基本运算的定义，掌握利用这些基本运算来实现串的其它各种运算的方法；掌握在顺序存储结构上实现串的各种操作的方法；重点掌握串上实现的模式匹配算法。 重点：串的各种运算方法 难点：串的模式匹配算法 第五章数组和广义表? 数组的存储结构；稀疏矩阵的表示及操作的实现；广义表的定义和存储结构；广义表的递归算法； 本章知识点：掌握数组在以行为主的存储结构中的地址计算方法；掌握矩阵实现压缩存储时的下标变换；理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法；掌握广义表的定义及其存储结构，学会广义表的表头，表尾分析方法。 重点:稀疏矩阵存储，矩阵元素地址的计算 难点：矩阵的三元组存储时算法 第六章树和二叉树? 树的基本概念；二叉树的性质和存储结构；遍历二叉树和线索二叉树；树的存储结构和遍历；树和森林；哈夫曼树及其应用；习题讨论课? 本章知识点：理解二叉树的结构特点；掌握二叉树的各种存储结构的特点及适用范围；深入掌握按各种次序遍历二叉树的递归和非递归算法；掌握二叉树的线索化，在中序线索树上找给定结点的前驱和后继的方法；掌握树的各种存储结构及其特点；掌握建立最优二叉树和哈夫曼编码的方法。? 重点：二叉树概念，性质，遍历算法 难点：二叉树线索化，二叉树的非递归算法 第七章图? 图的基本概念；图的存储结构；图的遍历及应用：最小生成树、最短路径等、拓扑排序。 本章知识点：熟悉图的各种存储结构，了解实际问题与采用何种存储结构和算法有密切联系；掌握遍历图的递归和非递归算法；掌握应用图的遍历算法求各种简单路径问题，比如，最小生成树、最短路径、拓扑排序等。? 重点：图的相关概念，图的遍历算法 难点：最小生成树，最短路径，拓扑排序 第九章查找? 静态查找表(顺序表, 有序表, 索引顺序表) ；动态查找表(二叉排序树, 平衡二叉树,B-树和B+树) 的建立和查找；哈希表的建立，查找及分析；习题讨论课。? 本章知识点：理解顺序查找，折半查找和索引查找的方法，并能灵活应用；掌握二叉排序树的构造方法及算法；掌握二叉平衡树的建立方法；了解B-树，B+树的特点以及它们的建立过程；掌握哈希表的构造方法；按定义计算各种查找方法在等概率情况下查找成功时和失败时的平均查找