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

数据结构课程教学大纲课程基本信息注：1,课程类别：选填“通识核心课/通识拓展课/通修课/学科基础课/专业主干课/专业选修课/专业实践/课程名称（中文）数据结构课程名称（英文）Data Structure课程类别】：学科基础课课程性质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语言描述，机械工 业出版社，2019o1 .严蔚敏，李冬梅，吴伟民著，数据结构（C语言版第2版附微课视频），人民邮电 出版社，2017o.陈卫卫，王庆瑞主编，数据结构与算法（第2版），高等教育出版社，2015o特性、存储表示、算法描述、分析以 及基本的算法应用例2.1具有将理论知识应用于构建解决工 程实际问题的模型、设计算法并分析 评价算法的能力讲授、实验、案 例2.2具有依据需求正确地设计和分析相 关算法、合理地设计数据的逻辑结 构、有效地存储和处理数据的能力讲授、实验、案 例3. 1具有终身学习的意识，探究与创新的 精神，严谨求实的科学态度讲授、实验、案 例注：1 .支撑毕业要求指标点：选填项。需要进行专业认证，有毕业要求指标点可参照的课程必填，无明确 毕业要求指标点可参照的可不填。三、理论教学内容章标题教学内容学时思政融入点1学生学习预期成果2教学方 式3课程 目标第1章1.数据结构的基本概念、术语及抽象数据从每个同 学日常的 过马路讲 起，谈到 如何设置 不同路口 的红绿 灯，使得 通过该路掌握数据 结构的基 本知识；具讲授、目标绪论类型的表示和实现2.算法和算法分析2口的车流 量和人流有基本的案例1.1量最大， 进而说明 我们学习 数据结构 的口的。 另外，强 调我们每 个人都不算法分析 的能力要闯红 灯，引导 学生除了 努力学习 科学文化 知识外， 还要具备 遵纪守 法、敬业 守信、作 风严谨的 大国工匠 素质。第2章 线性表1 .线性表的定义、相关概念（前驱、后继、 表长、位序、空表等）、线性表的抽象数 据结构类型定义；2 .线性表的顺序表示和运算实现;顺序表 的插入和删除操作的实现方法3 .线性链表的有关概念：头结点、结点、 数据域、指针域、指针（链）；线性链表 的存储结构、插入和删除操作的实现方法 及其时间复杂度分析4 .循环链表的存储结构以及插入和删除操 作的实现方法及其时间复杂度分析2掌握线性 表的基本 概念、术 语、特性； 掌握线性 表的顺序 存储和链 表存储的 表示及实 现方法； 具有应用 线性表解 决多项式 加减、相乘 等问题的 能力讲授、 实验、 案例目标1.1目标2.2第3章 栈和队 列1 .栈的有关概念：栈、栈顶、栈底、空栈 的定义；2 .栈的“后进先出”特点；3 .栈的抽象数据类型定义；4 .栈的表示和实现：顺序栈和链栈；5 .栈的应用举例：数制转换、括号匹配的 检验、表达式求值（应用栈实现表达式求 值的过程）；6 .队列的定义及有关概念，队列的“先进 先出”特点，队列的抽象数据类型定义；7 .链队列一队列的链式表示和实现；8 .循环队列一队列的顺序表示和实现:循6通过常见 的排队例 子对学生 进行思想 政治引 导，从而 引申出课 堂要遵守 课堂秩 序、遵守 国家的各 项法规，掌握栈和 队列的基 本概念、术 语、特性； 掌握栈和 队列存储 表小及头 现方法； 具有应用 栈解决后 进先出特讲授、 实验、 案例目标1.1目标2.1目标2.2环队列的存储结构，循环队列的插入和删 除操作实现教育学生 要懂规 矩，守纪 律，老实 守信。性的现实 问题的能 力第4章 字符串1 .串的定义，串长、空串、子串、主串、 位置、相等、空格串等概念；2 .串的表示和头现；（1）定长顺序存储表示（2）堆分配存储表示（3）串的块链存储表不3 .串的简单模式匹配算法2掌握串的 基本概念、 特性、存储 表示及各 种操作方 法；具有应用简单串匹 配算法完 成串匹配 的能力讲授、 实验、 案例目标1.1目标2.2第5章 数组和 广义表1 .数组的抽象数据结构类型定义；2 . 一维数组的顺序存储表示，二维数组的 顺序存储表示：以行序存储和以列序存储； 数组中存储元素和修改元素值的操作；3 .矩阵的压缩存储：对称矩阵的压缩存 储；稀疏矩阵的抽象数据类型定义，稀疏 因子的定义，稀疏矩阵压缩存储的实现方 法：三元组顺序表；十字链表。4掌握数组 的顺序表 示及实现、 稀疏矩阵 的概念、稀 疏矩阵的 压缩存储 方法；具有应用 三元组表 示法直接 求解稀疏 矩阵的转 置阵的能 力讲授、 案例目标1.1目标2.2第6章 树和二 叉树1 .树的抽象数据类型定义。结点、结点的 度、叶子（终端结点）、分支结点（非终 端结点）、树的度、双亲、孩子、兄弟、 祖先、子孙、深度、有序树、无序树和森 林等术语的定义；2 .二叉树的抽象数据类型定义；3 .二叉树的5个性质；满二叉树和完全二 叉树的概念；8掌握树与 二叉树的 相关概念、 术语、存储 方式、二叉 树的性质讲授、 实验、 案例目标1.1目标2.1目标2.24 .二叉树的存储结构：顺序存储结构、链 式存储结构；5 .遍历二叉树：先序遍历、中序遍历、后 序遍历的概念及递归算法；6 .树的存储结构：双亲表示法、孩子表示 法、孩子兄弟表示法；7 .树或森林与二叉树的相互转换方法；8 .哈夫曼树及其应用：路径长度、树的路 径长度、树的带权路径长度、最优二叉树 （哈夫曼树）的定义；哈夫曼编码算法证明、树与 二叉树的 遍历方法； 具有把树 型问题转 换成二叉 树问题进 行求解的 能力；具有应用 哈夫曼树 进行报文 编码的能 力第7章 图1 .基本概念及术语：顶点、弧（弧头、弧 尾）、有向图、无向图、完全图、网、子 图、度（出度、入度）、路径、回路（环）、 简单回路、连通图（强连通图）、连通分 量（强连通分量）等；2 .图的存储结构：邻接矩阵和邻接表；3 .图的遍历：深度优先、广度优先；4 .图的连通性问题：最小生成树的定义； 构造最小生成树的算法（Prim算法和 Kruskal 算法）；5 .图的应用：拓扑排序、重连通图和关节 点、关键路径以及单源最短路径问题（Dijkstra 算法）8图的应用 之一是人 工智能， 借此向学 生讲授人 工智能发 展的相关 知识；讲 述人工智 能的时代 已经来 临，许多 重复性的 劳动都可 以由人工 智能来完 成，我们 只有努力 学习，才 能不被人 工智能所 替代，才 能不被社 会淘汰； 同时引导 培养学生 的科学精掌握图的 存储表不、 图的遍历 算法；具有基本 的应用图 解决现实 问题的能 力讲授、 实验、 案例目标 1.1 目标2.2 目标3.1注：L思政融入点：至少写3条，简述该课程教学中将思政教育内容与专业教育内容有机融合的知识点（下 同）。神与工匠 精神。掌握静态第8 查找章1 .顺序查找的过程、算法以及性能分析； 平均查找长度的定义；2 .有序表的折半查找过程、算法以及性能 分析；3 .索引顺序表的查找过程、算法以及性能 分析；4 .二叉排序树的定义及查找过程；二叉排 序树的插入和删除；二叉排序树的查找分 析；平衡二叉树（AVL树）的概念及构造 过程；5 . B-树的定义；6 .哈希表：基本概念：哈希（Hash）函数、 冲突、同义词、哈希表、散列、哈希地址 （散列地址）等；哈希函数的构造要求、 除留余数法；处理冲突的方法：开放地址 法、链地址法；哈希表的查找及其分析6查找表:顺 序表的查 找,有序表 的查找，索 引顺序表 的查找； 掌握动态 查找表:二 叉排序树， 平衡二叉 树；掌握哈希 表及其查 找讲授、 实验、 案例目标2.1目标2.2目标3.1掌握常用第9章 内部排 序1 .排序的定义；排序方法的时间和空间特 性、稳定性；2 .插入排序:直接插入排序和希尔排序算 法；3 .快速排序算法；4 .选择排序：堆排序算法；5 .归并排序算法；6 .各种内部排序方法的比拟6的排序方 法及其算 法分析； 具有应用 各种排序 算法对各 种数据进 行排序的讲授、 实验、 案例目标2.1目标2.2目标3.1能力2 .学生学习预期成果：描述学生在学完本节内容后应获得的知识、能力或素养水平（下同）.教学方式:包括讲授、讨论、案例、演示等，但不限于所列，根据课程实际需要列举实践（实验或实习）教学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个数据 入队列(mn), 接着进行k次 出队列的操作 (k=m),再将 j 个数据入队列 (jn),最后从对 头到队尾依次 输出队列中的 元素。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平时 表现课程 作业课程 实验期末 考试占比 统计目标L1是否掌握了各种数据结构的基本概念、 逻辑特性、存储表示、算法描述、分析 以及基本的算法应用1%2%3%18%24%目标2.1是否具有将理论知识应用于构建解决工 程实际问题的模型、设计算法并分析评 价算法的能力1%3%5%25%34%目标2.2是否具有依据需求正确地设计和分析相 关算法、合理地设计数据的逻辑结构、 有效地存储和处理数据的能力1%3%5%25%34%目标3是否具有终身学习的意识，探究与创新 的精神，严谨求实的科学态度2%2%2%2%8%合计5%10%15%70%100%各考核方式占总成绩权重（自行赋值）5%10%15%70%100%注：1 .课程目标在考核方式及占比：主要根据课程目标自行设计和制定多元化考核方式，表中所列仅为参考（红色数据可删除）。但所列考核方式必须覆盖全体学生，可根据当学期具体教学情况酌情调整。 2各考核方式占总成绩权重：根据课程实际情况对各考核方式占总成绩的权重予以赋值。（二）考核方式评分标准1.课程作业评分标准课程目标评分标准占比90-100 （优）80-89 （良）70-79 （中）60-69（及格）0-59（不及格）5%目标1. 1:能够很好 地掌握各 种数据结 构的基本 概念、逻辑 特性、存储 表示、算法 描述、分析 以及基本 的算法应 用能够较好地 掌握各种数 据结构的基 本概念、逻 辑特性、存 储表示、算 法描述、分 析以及基本 的算法应用能够掌握各 种数据结构 的基本概 念、逻辑特 性、存储表 示、算法描 述、分析以 及基本的算 法应用基本掌握 各种数据 结构的基 本概念、逻 辑特性、存 储表示、算 法描述、分 析以及基 本的算法 应用不能掌握 各种数据 结构的基 本概念、逻 辑特性、存 储表示、算 法描述、分 析以及基 本的算法 应用1%目标2. 1：具有很强 的将理论 知识应用具有较强的 将理论知识 应用于构建 解决工程实具有将理论 知识应用于 构建解决工 程实际问题基本具有 将理论知 识应用于 构建解决不具有将 理论知识 应用于构 建解决工1%