《数据结构》课程教学大纲

《数据结构》课程教学大纲课程基本信息注：1,课程类别：选填“通识核心课/通识拓展课/通修课/学科基础课/专业主干课/专业选修课/专业实践/课程名称（中文）数据结构课程名称（英文）DataStructure课程类别】：学科基础课课程性质2必修授课语言3中文授课学期第3学期学分4课程学时及分配总学时讲课实验课外644816适用专业网络工程教材《数据结构（C语言版）》，严蔚敏，吴伟民编著，清华大学出版社，2018授课学院计算机与软件学院先修课程程序设计基础；离散数学后续课程数据库系统原理；算法设计与分析；操作系统课程简介课程基本定位：本课程为网络工程专业的学科基础课。该课程的目标是研究各种数据的抽象表示、实现方法、算法的设计过程以及算法的分析，是计算机软件设计的重要理论和实践基础课程。该课程往往同高效的检索算法和索引技术有关，它不仅是学习计算机操作系统、数据库系统、算法设计与分析等课程的重要基础，同时为从事网络工程方面的软件开发工作和科学研究奠定初步的基础。核心学习结果：能够理解数据结构的基本概念、逻辑特性；掌握各种数据结构的存储方法、相关算法及应用；能够运用数据结构的相关专业知识，分析计算机系统的复杂工程问题、设计合适的算法，并正确有效地开展实验验证工作。主要教学方法：讲授、案例、实验大纲更新时间素质拓展”2.课程性质：选填“选修/必修”3.授课语言：选填“中文/双语/全英文或其他语种”二、课程目标

序号课程目标（参考培养目标、毕业要求、课程定位）支撑毕业要求指标点1达成途径1.1掌握各种数据结构的基本概念、逻辑讲授、实验、案于构建解决工程实际问题的模型、设计算法并分析评价算法的能力际问题的模型、设计算法并分析评价算法的能力的模型、设计算法并分析评价算法的能力工程实际问题的模型、设计算法并分析评价算法的能力程实际问题的模型、设计算法并分析评价算法的能力目标2.2：很强的依具有较强的具有依据需基本具有不具有依据需求正依据需求正求正确地设依据需求据需求正确地设计确地设计和计和分析相正确地设确地设计分析相关算关算法、合计和分析和分析相和分析相法、合理地理地设计数相关算法、关算法、合关算法、合设计数据的据的逻辑结合理地设理地设计理地设计逻辑结构、构、有效地计数据的数据的逻1%数据的逻有效地存储存储和处理逻辑结构、辑结构、有和处理数据数据的能力有效地存效地存储辑结构、有的能力储和处理和处理数效地存储数据的能据的能力和处理数力据的能力目标3.1：具有很强具有较强的具有终身学基本具有不具有终的终身学终身学习的习的意识，终身学习身学习的习的意识，意识，探究探究与创新的意识，探意识，探究探究与创与创新的精的精神，严究与创新与创新的2%新的精神，神，严谨求谨求实的科的精神，严精神,严谨严谨求实实的科学态学态度谨求实的求实的科的科学态度度科学态度学态度2.课程实验评分标准课程目标评分标准占比90-100（优）80-89（良）70-79（中）60-69（及格）0-59（不及格）15%目标1.1:能够很好能够较好地能够掌握各基本掌握不能掌握地掌握各掌握各种数种数据结构各种数据各种数据种数据结据结构的基的基本概结构的基结构的基构的基本本概念、逻念、逻辑特本概念、逻本概念、逻概念、逻辑辑特性、存性、存储表辑特性、存辑特性、存3%特性、存储储表示、算示、算法描储表示、算储表示、算表示、算法法描述、分述、分析以法描述、分法描述、分描述、分析析以及基本及基本的算析以及基析以及基以及基本的算法应用法应用本的算法本的算法的算法应应用应用

用目标2.1：具有很强的将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力具有较强的将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力具有将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力基本具有将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力不具有将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力5%目标2.2：很强的依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力具有较强的依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力具有依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力基本具有依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力不具有依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力5%目标3.1：具有很强的终身学习的意识，探究与创新的精神，严谨求实的科学态度具有较强的终身学习的意识，探究与创新的精神，严谨求实的科学态度具有终身学习的意识，探究与创新的精神，严谨求实的科学态度基本具有终身学习的意识，探究与创新的精神，严谨求实的科学态度不具有终身学习的意识，探究与创新的精神，严谨求实的科学态度2%3.期末考试评分标准（笔试类评分标准可在大纲中按以下格式予以说明，也可在通过“试卷分析表”予以说明）

课程目标评分标准占比90-100（优）80-89（良）70-79（中）60-69（及格）0-59（不及格）70%目标1.1:能够很好地掌握各种数据结能够较好地掌握各种数据结构的基能够掌握各种数据结构的基本概基本掌握各种数据结构的基不能掌握各种数据结构的基18%构的基本概念、逻辑特性、存储表示、算法描述、分析以及基本的算法应本概念、逻辑特性、存储表示、算法描述、分析以及基本的算法应用念、逻辑特性、存储表示、算法描述、分析以及基本的算法应用本概念、逻辑特性、存储表示、算法描述、分析以及基本的算法应用本概念、逻辑特性、存储表示、算法描述、分析以及基本的算法应用目标2.1：具有很强的将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力具有较强的将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力具有将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力基本具有将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力不具有将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力25%目标2.2：很强的依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力具有较强的依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力具有依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力基本具有依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力不具有依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力25%目标3.1：具有很强的终身学习的意识，探究与创新的精神，严谨求实的科学态度具有较强的终身学习的意识，探究与创新的精神，严谨求实的科学态度具有终身学习的意识，探究与创新的精神，严谨求实的科学态度基本具有终身学习的意识，探究与创新的精神，严谨求实的科学态度不具有终身学习的意识，探究与创新的精神,严谨求实的科学态度2%注：考核方式和课程目标在考核方式中占比应与“（一）考核内容、考核方式与课程目标对应关系”一致。所列考核环节，除了笔试类均须依次给出评分标准，格式同上。笔试类课程考核评分标准可以在本课程大纲里进行说明，也可以通过提交“试卷分析表”予以说明。六、参考书目及学习资料.马克・艾伦・维斯（美）著，冯舜玺译，《数据结构与算法分析C语言描述》，机械工业出版社，2019o.严蔚敏，李冬梅，吴伟民著，《数据结构（C语言版第2版附微课视频）》，人民邮电出版社，2017o.陈卫卫，王庆瑞主编，《数据结构与算法（第2版）》，高等教育出版社，2015o特性、存储表示、算法描述、分析以及基本的算法应用例2.1具有将理论知识应用于构建解决工程实际问题的模型、设计算法并分析评价算法的能力讲授、实验、案例2.2具有依据需求正确地设计和分析相关算法、合理地设计数据的逻辑结构、有效地存储和处理数据的能力讲授、实验、案例3.1具有终身学习的意识，探究与创新的精神，严谨求实的科学态度讲授、实验、案例注：1.支撑毕业要求指标点：选填项。需要进行专业认证，有毕业要求指标点可参照的课程必填，无明确毕业要求指标点可参照的可不填。三、理论教学内容

章标题教学内容学时思政融入点1学生学习预期成果2教学方式3课程目标第1章1.数据结构的基本概念、术语及抽象数据从每个同学日常的过马路讲起，谈到如何设置不同路口的红绿灯，使得通过该路掌握数据结构的基本知识；具讲授、目标绪论类型的表示和实现2.算法和算法分析2口的车流量和人流有基本的案例1.1量最大，进而说明我们学习数据结构的口的。另外，强调我们每个人都不算法分析的能力要闯红灯，引导学生除了努力学习科学文化知识外，还要具备遵纪守法、敬业守信、作风严谨的大国工匠素质。第2章线性表.线性表的定义、相关概念（前驱、后继、表长、位序、空表等）、线性表的抽象数据结构类型定义；.线性表的顺序表示和运算实现;顺序表的插入和删除操作的实现方法.线性链表的有关概念：头结点、结点、数据域、指针域、指针（链）；线性链表的存储结构、插入和删除操作的实现方法及其时间复杂度分析.循环链表的存储结构以及插入和删除操作的实现方法及其时间复杂度分析2掌握线性表的基本概念、术语、特性；掌握线性表的顺序存储和链表存储的表示及实现方法；具有应用线性表解决多项式加减、相乘等问题的能力讲授、实验、案例目标1.1目标2.2第3章栈和队列.栈的有关概念：栈、栈顶、栈底、空栈的定义；.栈的“后进先出”特点；.栈的抽象数据类型定义；.栈的表示和实现：顺序栈和链栈；.栈的应用举例：数制转换、括号匹配的检验、表达式求值（应用栈实现表达式求值的过程）；.队列的定义及有关概念，队列的“先进先出”特点，队列的抽象数据类型定义；.链队列一队列的链式表示和实现；.循环队列一队列的顺序表示和实现:循6通过常见的排队例子对学生进行思想政治引导，从而引申出课堂要遵守课堂秩序、遵守国家的各项法规，掌握栈和队列的基本概念、术语、特性；掌握栈和队列存储表小及头现方法；具有应用栈解决后进先出特讲授、实验、案例目标1.1目标2.1目标2.2

环队列的存储结构，循环队列的插入和删除操作实现教育学生要懂规矩，守纪律，老实守信。性的现实问题的能力第4章字符串.串的定义，串长、空串、子串、主串、位置、相等、空格串等概念；.串的表示和头现；（1）定长顺序存储表示（2）堆分配存储表示（3）串的块链存储表不.串的简单模式匹配算法2掌握串的基本概念、特性、存储表示及各种操作方法；具有应用简单串匹配算法完成串匹配的能力讲授、实验、案例目标1.1目标2.2第5章数组和广义表.数组的抽象数据结构类型定义；.一维数组的顺序存储表示，二维数组的顺序存储表示：以行序存储和以列序存储；数组中存储元素和修改元素值的操作；.矩阵的压缩存储：对称矩阵的压缩存储；稀疏矩阵的抽象数据类型定义，稀疏因子的定义，稀疏矩阵压缩存储的实现方法：⑴三元组顺序表；⑵十字链表。4掌握数组的顺序表示及实现、稀疏矩阵的概念、稀疏矩阵的压缩存储方法；具有应用三元组表示法直接求解稀疏矩阵的转置阵的能力讲授、案例目标1.1目标2.2第6章树和二叉树.树的抽象数据类型定义。结点、结点的度、叶子（终端结点）、分支结点（非终端结点）、树的度、双亲、孩子、兄弟、祖先、子孙、深度、有序树、无序树和森林等术语的定义；.二叉树的抽象数据类型定义；.二叉树的5个性质；满二叉树和完全二叉树的概念；8掌握树与二叉树的相关概念、术语、存储方式、二叉树的性质讲授、实验、案例目标1.1目标2.1目标2.2.二叉树的存储结构：顺序存储结构、链式存储结构；.遍历二叉树：先序遍历、中序遍历、后序遍历的概念及递归算法；.树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法；.树或森林与二叉树的相互转换方法；.哈夫曼树及其应用：路径长度、树的路径长度、树的带权路径长度、最优二叉树（哈夫曼树）的定义；哈夫曼编码算法证明、树与二叉树的遍历方法；具有把树型问题转换成二叉树问题进行求解的能力；具有应用哈夫曼树进行报文编码的能力第7章图.基本概念及术语：顶点、弧（弧头、弧尾）、有向图、无向图、完全图、网、子图、度（出度、入度）、路径、回路（环）、简单回路、连通图（强连通图）、连通分量（强连通分量）等；.图的存储结构：邻接矩阵和邻接表；.图的遍历：深度优先、广度优先；.图的连通性问题：最小生成树的定义；构造最小生成树的算法（Prim算法和Kruskal算法）；.图的应用：拓扑排序、重连通图和关节点、关键路径以及单源最短路径问题（Dijkstra算法）8图的应用之一是人工智能，借此向学生讲授人工智能发展的相关知识；讲述人工智能的时代已经来临，许多重复性的劳动都可以由人工智能来完成，我们只有努力学习，才能不被人工智能所替代，才能不被社会淘汰；同时引导培养学生的科学精掌握图的存储表不、图的遍历算法；具有基本的应用图解决现实问题的能力讲授、实验、案例目标1.1目标2.2目标3.1

注：L思政融入点：至少写3条，简述该课程教学中将思政教育内容与专业教育内容有机融合的知识点（下同）。神与工匠精神。掌握静态第8查找章.顺序查找的过程、算法以及性能分析；平均查找长度的定义；.有序表的折半查找过程、算法以及性能分析；.索引顺序表的查找过程、算法以及性能分析；.二叉排序树的定义及查找过程；二叉排序树的插入和删除；二叉排序树的查找分析；平衡二叉树（AVL树）的概念及构造过程；.B-树的定义；.哈希表：基本概念：哈希（Hash）函数、冲突、同义词、哈希表、散列、哈希地址（散列地址）等；哈希函数的构造要求、除留余数法；处理冲突的方法：开放地址法、链地址法；哈希表的查找及其分析6查找表:顺序表的查找,有序表的查找，索引顺序表的查找；掌握动态查找表:二叉排序树，平衡二叉树；掌握哈希表及其查找讲授、实验、案例目标2.1目标2.2目标3.1掌握常用第9章内部排序.排序的定义；排序方法的时间和空间特性、稳定性；.插入排序:直接插入排序和希尔排序算法；.快速排序算法；.选择排序：堆排序算法；.归并排序算法；.各种内部排序方法的比拟6的排序方法及其算法分析；具有应用各种排序算法对各种数据进行排序的讲授、实验、案例目标2.1目标2.2目标3.1能力.学生学习预期成果：描述学生在学完本节内容后应获得的知识、能力或素养水平（下同）.教学方式:包括讲授、讨论、案例、演示等，但不限于所列，根据课程实际需要列举实践（实验或实习）教学I

编实验或实习教学内容学时实验或实思政融入点学生学习课程号工程名称习类型2预期成果目标1顺序表的创建与合并动态创立2个有序的顺序表：La,Lb；再创立一个空的顺序表Lc；然后将La与Lb的内容合并到Lc中，使得Lc也是有序的，并输出Lc中的内容。2验证掌握顺序表构造、查找、插入和合并等算法并能灵活运用这些算法目标1.1目标2.2目标3.12链表的创立与应用分别采用逆序和正序两种方法创立链表，输出链表的内容；然后将链表的前m个结点与后n个结点整体对调，输出对调后链表中的内容。2验证掌握链表的构造、查找等算法并灵活运用这些算法目标1.1目标2.2目标3.13栈的应用一表达式括弧匹配检查输入一个算术表达式，其中包含两种括号:圆括号“()”和方括号“口”,嵌套顺序任意，编写一个算法用于判别表达式中括弧是否能够正确匹配。2设计掌握栈的特性、栈的基本操作，并能应用栈解决具有后进先出特性的问题目标1.1目标2.2目标3.14循环队列的创立与应用首先建立一个长度为n的循环队列，然后依次将m个数据入队列(m<n),接着进行k次出队列的操作(k<=m),再将j个数据入队列(j<n),最后从对头到队尾依次输出队列中的元素。2验证掌握队列的特性、循环队列的基本操作，并能对其进行简单应用目标1.1目标2.2目标3.1

注：1.此表可用于课内实践教学环节或某门综合实践课程5二叉树的创建与遍历根据给定的二叉树，先人工对其进行先序遍历，根据先序遍历的结果编写程序创立该二叉树；然后用非递归中序遍历算法，输出中序遍历的结果。2设计掌握二叉树的创立、遍历的基本算法，并对其进行简单应用目标1.1目标2.2目标3.16图的创立与遍历针对给定的无向图，实现图的深度优先遍历和广度优先遍历算法，并输出相应遍历的结果。2设计掌握图的邻接表的存储方法、深度优先以及广度优先的算法目标2.1目标2.2目标3.17哈希表的创建与查找针对给定的一组序列，采用除留余数法设计一个哈希表，并分别采用开放地址法和链地址法解决哈希冲突，完成相应的建表和查表算法。2验证掌握哈希函数的构造方法，处理冲突的机制以及查找的算法目标1.1目标2.2目标3.18快速排序算法实现针对给定的无序数列，采用快速排序算法进行排序，要求能输出每一次分划后的结果以及最终排序结果。2验证掌握快速排序的算法、枢轴的选择方法目标1.1目标2.2目标3.12.实验类型：选填”验证性/综合性/设计性”；实习类型：选填“认识实习/生产实习/毕业实习”五、课程评价（一）考核内容、考核方式与课程目标对应关系

课程目标考核内容课程目标在各考核方式中占比1平时表现课程作业课程