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

《数据结构I》课程教学大纲
一、课程基本信息
课程名称（中文）
数据结构I
课程名称（英文）
Data Structure I
课程类别：
学科基础课程
课程性质
必修授课语言中文
授课学期
第3学期
学分
4
课程学时及分配
总学时
讲课
实验
课外
64
48
16
0
适用专业
物联网工程等
授课学院
计算机与软件学院
先修课程
物联网工程导论、程序设计基础
后续课程
数据库系统、操作系统、算法设计与分析
课程简介
课程基本定位：本课程为物联网工程专业专业主干课。该课程的目标 是研究各种数据的抽象表示、实现方法、算法的设计过程以及算法的 分析，是计算机软件设计的重要理论和实践基础课程。该课程往往同 高效的检索算法和索引技术有关，它不仅是学习计算机操作系统、数 据库系统、算法设计与分析等课程的重要基础，同时为从事物联网工 程技术工作和科学研究奠定初步的基础。
课程复杂工程问题：本课程中的“数据结构课程设计”是在理解抽象 的理论概念、掌握数据模型的一些典型应用，并逐步具有解决实际问 题的能力的基础上，将线性表、栈、队列、树、图、查找、排序等知 识点贯串进来，融合个性需要，给出解决实际问题的技术方案。在具 体的实施过程中，按照探究未知知识领域的途径，通过提出问题、分 析问题、创造性地解决问题、知识迁移等步骤予以实施。同时，分析 该解决方案是否为最优方案，是否有改进的空间，通过查阅文献、小 组讨论等方式，创造性地给出改进方案，并能对该方案进行算法分析。
核心学习结果：结合自主学习，理解数据结构的基本概念、逻辑特性， 掌握各种数据结构的存储方法、相关算法及应用；能够运用数据结构 的相关专业知识，分析计算机系统的复杂工程问题，设计合适的算法， 并正确有效地开展实验验证工作。
主要教学方法：讲授、案例、实验、专题研讨
大纲更新时间

二、课程目标（3）课程考试评分标准

无抄袭痕 迹，图文并 茂；能正确 问答所提 的问题。
痕迹，图文并 茂；能比拟正 确问答所提 的问题。
好，无抄袭痕 迹，图文并 茂；能比拟正 确问答所提 的问题。
袭痕迹，图文 并茂；能基本 正确问答所提 的问题。

课程目标
评分标准
90-100 （优）
80-89 （良）
70-79 （中）
60-69 （及格）
0-59
（不及格）
□标 L1：
能够很好 地掌握各 种数据结 构的基本 概念、逻辑 特性、算法 描述、算法 的分析和 设计方法。
能够较好地 掌握各种数 据结构的基 本概念、逻辑 特性、算法描 述、算法的分 析和设计方 法。
能够掌握各 种数据结构 的基本概念、 逻辑特性、算 法描述、算法 的分析和设 计方法。
基本掌握各种 数据结构的基 本概念、逻辑 特性、算法描 述、算法的分 析和设计方 法。
不能掌握各种 数据结构的基 本概念、逻辑 特性、算法描 述、算法的分 析和设计方 法。
目标1. 2：
能够很好 地掌握将 理论知识 应用于构 建模型、算 法的基本 知识。
能够较好地 掌握将理论 知识应用于 构建模型、算 法的基本知 识。
能够掌握将 理论知识应 用于构建模 型、算法的基 本知识。
基本掌握将理 论知识应用于 构建模型、算 法的基本知 识。
不能掌握将理 论知识应用于 构建模型、算 法的基本知 识。
目标2. 1 ：
具有很强 的根据工 程问题实 际应用和 需求，对问 题进行分 析和推理， 抽象出其 数据模型 的能力。
具有较强的 根据工程问 题实际应用 和需求，对问 题进行分析 和推理，抽象 出其数据模 型的能力。
具有一般的 根据工程问 题实际应用 和需求，对问 题进行分析 和推理，抽象 出其数据模 型的能力。
基本具有根据 工程问题实际 应用和需求， 对问题进行分 析和推理，抽 象出其数据模 型的能力。
不具有根据工 程问题实际应 用和需求，对 问题进行分析 和推理，抽象 出其数据模型 的能力。
目标2. 2：
具有很强 的根据工 程问题实 际应用和 需求，分析 和设计正 确的算法
具有较强的 根据工程问 题实际应用 和需求，分析 和设计正确 的算法的能 力。
具有一般的 根据工程问 题实际应用 和需求，分析 和设计正确 的算法的能 力。
基本具有根据 工程问题实际 应用和需求， 分析和设计正 确的算法的能 力。
不具有根据工 程问题实际应 用和需求，分 析和设计正确 的算法的能 力。

的能力。

目标2. 3：
具有很强 的根据设 计出的算 法，合理地 组织、存储 和处理数 据的能力。
具有较强的 根据设计出 的算法，合理 地组织、存储 和处理数据 的能力。
具有一般的 根据设计出 的算法，合理 地组织、存储 和处理数据 的能力。
基本具有根据 设计出的算 法，合理地组 织、存储和处 理数据的能 力。
不具有根据设 计出的算法， 合理地组织、 存储和处理数 据的能力。

七、参考书目及学习资料.萨特吉・萨尼（美）著，王立柱，刘志红译，《数据结构、算法与应用：C++语言描述 （第2版）》，机械工业出版社，2015o
1 .陈卫卫，王庆瑞主编，《数据结构与算法（第2版）》，高等教育出版社，2015o.邓俊辉主编，《数据结构（C++语言版）第3版》，清华大学出版社，2013o
课程总目标
课程子目标
达成方法
L知识
1.1 :掌握各种数据结构的基本概念、逻辑特性、存 储结构、算法的分析和设计方法。
1.2 ：掌握将理论知识应用于构建模型、算法的基本 知识。
讲授、实验、案 例。
2 .能力
2.1 ：具有根据工程问题实际应用和需求，对问题进 行分析和推理，抽象出其数据模型的能力。
2.2 ：具有根据工程问题实际应用和需求，分析和设 计正确的算法的能力。
2.3 ：具有根据设计出的算法，合理地组织、存储和 处理数据的能力。
2.4 ：具有依据工程实际问题的需求，制定适当的研 究路线，设计实验方案。
讲授、实验、案 例。
3.素养
3.1：培养研究问题的意识、独立思考的精神、能够 结合所学知识正确分析问题的内涵。
实验、案例。

、理论教学环节及基本要求
三、课程目标及对毕业要求指标点的支撑U!
序号
支撑的毕业要求指标点
课程目标
1
指标点1.3：能够运用工程基础、 专业知识和数学模型方法，对物联 网工程领域的智慧标识和感知、信 息传送和智能处理环节的复杂工程 问题的进行推理和分析。
课程目标L1
课程目标1.2
2
指标点2.2：应用数学、自然科学、 工程科学和专业知识的基本原理， 针对物联网工程领域的智慧标识和 感知、信息传送和智能处理等环节 的复杂工程问题进行抽象、描述和 表达。
课程目标2.1
3
指标点3.2：能够合理地组织、存 储和处理数据，根据各类资源作用 及特定需求，正确地进行算法和模 块设计。
课程目标2.2
课程目标2.3
4
指标点4.2：能够根据物联网工程 领域的智慧标识和感知、信息传送 和智能处理环节的系统特征及应用 需求，选择研究路线，设计实验方 案。
课程目标2.4
课程目标3.1

章标题
教学内 容
学时
预期学习成果
（描述学生在学完本 节内容后其知识、能力 或素养预期成果到达
的程度，后同）
教学方式
（讲授、专题研 讨、案例、实验、 实地调研等，但 不限于此）
课程目标
第一章
绪论
2
掌握数据结构基本概 念、基本术语、算法的 描述方法、算法时间复 杂度的分析方法。
讲授、案例
目标L1
目标3」
第二章
线性表
4
掌握线性表的基本概 念、术语、特性、线性 表的顺序存储表示及 实现、线性表的链接存 储表示及实现。
讲授、案例、实 验、作业
目标L1
目标1.2
目标2.3
第二早
栈和队 列
6
掌握栈的基本概念、术 语、特性、栈的顺序存 储表示及实现、栈的链 接存储表示及实现、栈 的应用。
掌握队列的基本概念、 术语、特性、队列的顺 序存储表示及实现、队 列的链接存储表示及 实现。
讲授、案例、实 验、作业
目标
目标L2
目标2.3
第四章
字符串
2
掌握串的定义，串长、 空串、子串、主串、位 置、相等、空格串等概 念、串的三种存储表示 及实现、简单的串的模 式匹配算法。
讲授、案例、实 验、作业
目标1.1
目标L2
第五章
数组和 广义表
4
掌握数组的顺序表示 及实现、稀疏矩阵的概 念、稀疏矩阵的压缩存 储方法及应用。
讲授、案例、作 业
目标L1
目标L2
目标2.3
第六章
树和二 叉树
8
掌握树与二叉树的相 关概念、术语、存储方 式、二叉树的性质证明 及应用、树与二叉树的 遍历方法、树与二叉树
讲授、案例、实 验、作业
目标L1
目标L2
目标2.3

的相互转换、哈夫曼树 及其编码。

第七章
图
8
掌握图的邻接矩阵、邻 接表存储表示、图的深 度优先遍历、广度优先 遍历算法、图的基本应 用及其复杂度分析:最 小（代价）生成树、重 连通图的判定、最短路 径、拓扑排序、关键 路径。
讲授、案例、实 验、作业
目标2.1
目标2.2
目标2.3
第八章
查找
6
掌握静态查找表:顺序 表的查找，有序表的查 找，索引顺序表的查 找。
掌握动态查找表:二叉 排序树，平衡二叉树。 掌握哈希表及其查找。
讲授、案例、实 验
目标2.2
目标2.3
第九章
内部排 序
6
掌握常用的排序方法 及其算法复杂度的分 析，包括：直接插入排 序，二分法插入排序， 直接选择排序，冒泡排 序，希尔排序，快速排 序,堆排序，归相F序， 基数排序。
讲授、案例、实 验、作业
目标2.2
目标2.3

五、实践（实验）教学环节及基本要求
编号
实践（实验） 工程名称
教学内容
学时
实验类型
预期学习成果
课程目标

顺序表的创 建与合并
动态创立2个 顺序表:La, Lb , La与Lb是有 序表；再创立一

掌握顺序表构 造、查找、插
目标2.3
1
个空的顺序表L c,将La与Lb 的内容合并到L c中，使得Lc 也是有序的，并
2
验证
入和合并等算 法并能灵活运 用这些算法。
目标2.4
目标3.1

输出Lc中的内 容。

2
链表的创立 与应用
分别采用逆序 和正序两种方 法创立链表，输 出链表的内容； 然后将链表的 前m个结点与 后n个结点整 体对调，输出对 调后链表中的 内容。
2
验证
掌握链表的构 造、查找等算 法并灵活运用 这些算法。
目标2.3
目标2.4
目标3.1
3
栈的应用一 表达式括弧 匹配检查
假设一个算术 表达式中包含 假设数学表达 式中允许包含 两种括号:圆括 号〃()〃和方括号 〃口；嵌套顺序任 意，编写一个算 法用于判别表 达式中括弧是 否能够正确匹 配。
2
设计
掌握栈的特 性、栈的基本 操作，并能应 用栈解决具有 后进先出特性 的问题。
目标2.3
目标2.4
目标3.1
4
循环队列的 创立与应用
假设循环队列 的最大长度为 n,现在依次将 m个数据入队 歹U，接着进行k 次出队列的操 作，再将，个数 据入队列，最后 从对头到队尾 依次输出队列 中的元素。
2
验证
掌握队列的特 性、循环队列 的基本操作， 并能对其进行 简单应用。
目标2.3
目标2.4
目标3.1
5
二叉树的创 建与遍历
根据给定的二 叉树，先人工对 其进行先序遍 历,根据先序遍 历的结果编写 程序创立该二 叉树；然后用非 递归中序遍历 算法，输出中序
2
设计
掌握二叉树的 创立、遍历的 基本算法，并 对其进行简单 应用。
目标2.3
目标2.4
目标3.1

遍历的结果。

6
图的创立与 遍历
对给定的无向 图图，实现图的 深度优先遍历 和广度优先遍 历算法并输出 相应的结果。
2
设计
掌握图的邻接 表的存储方 法、深度优先 以及广度优先 的算法。
目标2.3
目标2.4
目标3.1
7
哈希表的创 建与查找
针对某个图书 馆中的书号，设 il个哈希表， 完成相应的建 表和查表算法。
2
设计
掌握哈希函数 的构造方法， 处理冲突的机 制以及查找的 算法。
目标2.3
目标2.4
目标3.1
8
快速排序算 法实现
对给定的无序 数组用快速排 序算法进行排 序，要求能输 出每一次分划 后的结果以及 最终排序结果。
2
验证
掌握快速排序 的算法、枢轴 的选择方法。
目标2.3
目标2.4
目标3.1
六、课程评价
（一）考核内容、考核方式与课程目标对应关系
课程目标
考核内容
考核方式及占比（％）
成绩（%）
作业
课程实验
考试

目标1.1
是否掌握各种数据结 构的基本概念、逻辑特 性、存储结构、算法的 分析和设计方法。
3.5%
1.5%
20%
25.0%
目标1.2
是否掌握将理论知识 应用于构建模型、算法 的基本知识。
3.5%
1.5%
15%
20.0%
目标2.1
是否具有根据工程问 题实际应用和需求，对 问题进行分析和推理， 抽象出其数据模型的 能力。
3.0%
2.5%
10%
15.5%
目标2.2
是否具有根据工程问 题实际应用和需求，分
2.5%
2.5%
15%
20%

析和设计正确的算法 的能力。

目标2.3
是否具有根据设计出 的算法，合理地组织、 存储和处理数据的能 力。
2.5%
2.0%
10%
14.5%
目标2.4
是否具有依据工程实 际问题的需求，制定适 当的研究路线，设计实 验方案。

2.0%

2.0%
目标3.1
是否具有研究问题的 意识、独立思考的精 神、能够结合所学知识 正确分析问题的能力。

3.0%

3.0%
合计
15%
15%
70%
100%

(二)考核方式评分标准
1.评分标准总体说明：
(1)本课程通过知识讲授、实验、课程考试等环节组成，最终要求学生能够认真完成实 验和作业，通过课程考试。
(2)总评成绩由期末考试、作业和实验环节构成，各项课程子目标成绩按五等百分制评定，根据考核方式及占比表中规定的比例折算得到个人最终成绩。
2.评分标准分项说明(1)课程作业评分标准
课程目标
评分标准
90-100 （优）
80-89 （良）
70-79 （中）
60-69 (及格)
0-59
(不及格)
目标1. 1:
能够很好地
能够较好地
能够掌握各
基本掌握各种
不能掌握各种

掌握各种数
掌握各种数
种数据结构
数据结构的基
数据结构的基

据结构的基
据结构的基
的基本概念、
本概念、逻辑
本概念、逻辑

本概念、逻
本概念、逻辑
逻辑特性、存
特性、存储结
特性、存储结

辑特性、存
特性、存储结
储结构、算法
构、算法的分
构、算法的分

储结构、算
构、算法的分
的分析和设
析和设计方
析和设计方

法的分析和
析和设计方
计方法。
法。
法。

设计方法。
法。

目标1. 2：
能够很好地
能够较好地
能够掌握将
基本掌握将理
不能掌握将理

掌握将理论
掌握将理论
理论知识应
论知识应用于
论知识应用于

知识应用于
知识应用于
用于构建模
构建模型、算
构建模型、算
（2）课程实验评分标准

构建模型、 算法的基本 知识。
构建模型、算 法的基本知 识。
型、算法的基 本知识。
法的基本知 识。
法的基本知 识。
目标2. 1 ：
具有很强的
具有较强的
具有一般的
基本具有根据
不具有根据工

根据工程问
根据工程问
根据工程问
工程问题实际
程问题实际应

题实际应用
题实际应用
题实际应用
应用和需求，
用和需求，对

和需求，对
和需求，对问
和需求，对问
对问题进行分
问题进行分析

问题进行分
题进行分析
题进行分析
析和推理，抽
和推理，抽象

析和推理，
和推理，抽象
和推理，抽象
象出其数据模
出其数据模型

抽象出其数 据模型的能 力。
出其数据模 型的能力。
出其数据模 型的能力。
型的能力。
的能力。
目标2. 2：
具有很强的
具有较强的
具有一般的
基本具有根据
不具有根据工

根据工程问
根据工程问
根据工程问
工程问题实际
程问题实际应

题实际应用
题实际应用
题实际应用
应用和需求，
用和需求，分

和需求，分
和需求，分析
和需求，分析
分析和设计正
析和设计正确

析和设计正
和设计正确
和设计正确
确的算法的能
的算法的能

确的算法的 能力。
的算法的能 力。
的算法的能 力。
力。
力。
目标2. 3：
具有很强的
具有较强的
具有一般的
基本具有根据
不具有根据设

根据设计出
根据设计出
根据设计出
设计出的算
计出的算法，

的算法，合
的算法，合理
的算法，合理
法，合理地组
合理地组织、

理地组织、
地组织、存储
地组织、存储
织、存储和处
存储和处理数

存储和处理 数据的能 力。
和处理数据 的能力。
和处理数据 的能力。
理数据的能 力。
据的能力。

课程目标
评分标准
90-100 （优）
80-89 （良）
70-79 （中）
60-69 （及格）
0-59
（不及格）
目标1. 1:
能够很好 地掌握各 种数据结 构的基本 概念、逻辑 特性、算法 描述、算法 的分析和 设计方法。
能够较好地 掌握各种数 据结构的基 本概念、逻辑 特性、算法描 述、算法的分 析和设计方 法。
能够掌握各 种数据结构 的基本概念、 逻辑特性、算 法描述、算法 的分析和设 计方法。
基本掌握各种 数据结构的基 本概念、逻辑 特性、算法描 述、算法的分 析和设计方 法。
不能掌握各种 数据结构的基 本概念、逻辑 特性、算法描 述、算法的分 析和设计方 法。
目标1. 2：
能够很好 地掌握将 理论知识
能够较好地 掌握将理论 知识应用于
能够掌握将 理论知识应 用于构建模
基本掌握将理 论知识应用于 构建模型、算
不能掌握将理 论知识应用于 构建模型、算

应用于构 建模型、算 法的基本 知识。
构建模型、算 法的基本知 识。
型、算法的基 本知识。
法的基本知 识。
法的基本知 识。
目标2. 1：
具有很强 的根据工 程问题实 际应用和 需求，对问 题进行分 析和推理， 抽象出其 数据模型 的能力。
具有较强的 根据工程问 题实际应用 和需求，对问 题进行分析 和推理，抽象 出其数据模 型的能力。
具有一般的 根据工程问 题实际应用 和需求，对问 题进行分析 和推理，抽象 出其数据模 型的能力。
基本具有根据 工程问题实际 应用和需求， 对问题进行分 析和推理，抽 象出其数据模 型的能力。
不具有根据工 程问题实际应 用和需求，对 问题进行分析 和推理，抽象 出其数据模型 的能力。
目标2. 2：
具有很强 的根据工 程问题实 际应用和 需求，分析 和设计正 确的算法 的能力。
具有较强的 根据工程问 题实际应用 和需求，分析 和设计正确 的算法的能 力。
具有一般的 根据工程问 题实际应用 和需求，分析 和设计正确 的算法的能 力。
基本具有根据 工程问题实际 应用和需求， 分析和设计正 确的算法的能 力。
不具有根据工 程问题实际应 用和需求，分 析和设计正确 的算法的能 力。
目标2. 3：
具有很强 的根据设 计出的算 法，合理地 组织、存储 和处理数 据的能力。
具有较强的 根据设计出 的算法，合理 地组织、存储 和处理数据 的能力。
具有一般的 根据设计出 的算法，合理 地组织、存储 和处理数据 的能力。
基本具有根据 设计出的算 法，合理地组 织、存储和处 理数据的能 力。
不具有根据设 计出的算法， 合理地组织、 存储和处理数 据的能力。
目标2. 4：
具有很强 的研究问 题的意识、 独立思考 的精神、能 够结合所 学知识正 确分析问 题的能力。
具有较强的 研究问题的 意识、独立思 考的精神、能 够结合所学 知识正确分 析问题的能 力。
具有一般的 研究问题的 意识、独立思 考的精神、能 够结合所学 知识正确分 析问题的能 力。
基本具有研究 问题的意识、 独立思考的精 神、能够结合 所学知识正确 分析问题的能 力。
不具有研究问 题的意识、独 立思考的精 神、能够结合 所学知识正确 分析问题的能 力。
目标3. 1 ：
实验报告 格式规范， 文字严谨， 内容正确， 条理性好，
实验报告格 式规范，文字 严谨，内容比 较正确，条理 性好，无抄袭
实验报告格 式比拟规范， 文字比拟严 谨，内容正 确，条理性
实验报告格式 基本规范，文 字严谨，内容 基本正确，条 理性好，无抄
实验报告有明 显的抄袭痕 迹，不能正确 问答所提的问 题。