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

《数据结构》课程教学大纲
课程基本信息注：1,课程类别：选填“通识核心课/通识拓展课/通修课/学科基础课/专业主干课/专业选修课/专业实践/
课程名称（中文）
数据结构
课程名称（英文）
Data Structure
课程类别】：
学科基础课
课程性质2
必修
授课语言3
中文
授课学期
第3学期
学分
4
课程学时及分配
总学时
讲课
实验
课外
64
48
16

适用专业
网络工程
教材
《数据结构（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
1 .严蔚敏，李冬梅，吴伟民著，《数据结构（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.2

4 .二叉树的存储结构：顺序存储结构、链 式存储结构；
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.1
2
链表的创立 与应用
分别采用逆序 和正序两种方 法创立链表，输 出链表的内容； 然后将链表的 前m个结点与 后n个结点整 体对调，输出对 调后链表中的 内容。
2
验证

掌握链表的构 造、查找等算法 并灵活运用这 些算法
目标
1.1
目标
2.2
目标
3.1
3
栈的应用一 表达式括弧 匹配检查
输入一个算术 表达式，其中包 含两种括号:圆 括号“()”和方 括号“口”,嵌套 顺序任意，编写 一个算法用于 判别表达式中 括弧是否能够 正确匹配。
2
设计

掌握栈的特性、 栈的基本操作， 并能应用栈解 决具有后进先 出特性的问题
目标
1.1
目标
2.2
目标
3.1
4
循环队列的 创立与应用
首先建立一个 长度为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.1
6
图的创立与
遍历
针对给定的无 向图，实现图的 深度优先遍历 和广度优先遍 历算法，并输出 相应遍历的结 果。
2
设计

掌握图的邻接 表的存储方法、 深度优先以及 广度优先的算 法
目标
2.1
目标
2.2
目标
3.1
7
哈希表的创 建与查找
针对给定的一 组序列，采用除 留余数法设计 一个哈希表，并 分别采用开放 地址法和链地 址法解决哈希 冲突，完成相应 的建表和查表 算法。
2
验证

掌握哈希函数 的构造方法，处 理冲突的机制 以及查找的算 法
目标
1.1
目标
2.2
目标
3.1
8
快速排序算 法实现
针对给定的无 序数列，采用快 速排序算法进 行排序，要求 能输出每一次 分划后的结果 以及最终排序 结果。
2
验证

掌握快速排序 的算法、枢轴的 选择方法
目标
1.1
目标
2.2
目标
3.1
2.实验类型：选填”验证性/综合性/设计性”；实习类型：选填“认识实习/生产实习/毕业实习”
五、课程评价（一）考核内容、考核方式与课程目标对应关系
课程目标
考核内容
课程目标在各考核方式中占比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%