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

数据结构I课程教学大纲一、课程基本信息课程名称（中文）数据结构I课程名称（英文）Data Structure I课程类别：学科基础课程课程性质必修授课语言中文授课学期第3学期学分4课程学时及分配总学时讲课实验课外6448160适用专业物联网工程等授课学院计算机与软件学院先修课程物联网工程导论、程序设计基础后续课程数据库系统、操作系统、算法设计与分析课程简介课程基本定位：本课程为物联网工程专业专业主干课。该课程的目标 是研究各种数据的抽象表示、实现方法、算法的设计过程以及算法的 分析，是计算机软件设计的重要理论和实践基础课程。该课程往往同 高效的检索算法和索引技术有关，它不仅是学习计算机操作系统、数 据库系统、算法设计与分析等课程的重要基础，同时为从事物联网工 程技术工作和科学研究奠定初步的基础。课程复杂工程问题：本课程中的“数据结构课程设计”是在理解抽象 的理论概念、掌握数据模型的一些典型应用，并逐步具有解决实际问 题的能力的基础上，将线性表、栈、队列、树、图、查找、排序等知 识点贯串进来，融合个性需要，给出解决实际问题的技术方案。在具 体的实施过程中，按照探究未知知识领域的途径，通过提出问题、分 析问题、创造性地解决问题、知识迁移等步骤予以实施。同时，分析 该解决方案是否为最优方案，是否有改进的空间，通过查阅文献、小 组讨论等方式，创造性地给出改进方案，并能对该方案进行算法分析。核心学习结果：结合自主学习，理解数据结构的基本概念、逻辑特性， 掌握各种数据结构的存储方法、相关算法及应用；能够运用数据结构 的相关专业知识，分析计算机系统的复杂工程问题，设计合适的算法， 并正确有效地开展实验验证工作。主要教学方法：讲授、案例、实验、专题研讨大纲更新时间二、课程目标（3）课程考试评分标准无抄袭痕 迹，图文并 茂；能正确 问答所提 的问题。痕迹，图文并 茂；能比拟正 确问答所提 的问题。好，无抄袭痕 迹，图文并 茂；能比拟正 确问答所提 的问题。袭痕迹，图文 并茂；能基本 正确问答所提 的问题。课程目标评分标准90-100 （优）80-89 （良）70-79 （中）60-69 （及格）0-59（不及格）标 L1：能够很好 地掌握各 种数据结 构的基本 概念、逻辑 特性、算法 描述、算法 的分析和 设计方法。能够较好地 掌握各种数 据结构的基 本概念、逻辑 特性、算法描 述、算法的分 析和设计方 法。能够掌握各 种数据结构 的基本概念、 逻辑特性、算 法描述、算法 的分析和设 计方法。基本掌握各种 数据结构的基 本概念、逻辑 特性、算法描 述、算法的分 析和设计方 法。不能掌握各种 数据结构的基 本概念、逻辑 特性、算法描 述、算法的分 析和设计方 法。目标1. 2：能够很好 地掌握将 理论知识 应用于构 建模型、算 法的基本 知识。能够较好地 掌握将理论 知识应用于 构建模型、算 法的基本知 识。能够掌握将 理论知识应 用于构建模 型、算法的基 本知识。基本掌握将理 论知识应用于 构建模型、算 法的基本知 识。不能掌握将理 论知识应用于 构建模型、算 法的基本知 识。目标2. 1 ：具有很强 的根据工 程问题实 际应用和 需求，对问 题进行分 析和推理， 抽象出其 数据模型 的能力。具有较强的 根据工程问 题实际应用 和需求，对问 题进行分析 和推理，抽象 出其数据模 型的能力。具有一般的 根据工程问 题实际应用 和需求，对问 题进行分析 和推理，抽象 出其数据模 型的能力。基本具有根据 工程问题实际 应用和需求， 对问题进行分 析和推理，抽 象出其数据模 型的能力。不具有根据工 程问题实际应 用和需求，对 问题进行分析 和推理，抽象 出其数据模型 的能力。目标2. 2：具有很强 的根据工 程问题实 际应用和 需求，分析 和设计正 确的算法具有较强的 根据工程问 题实际应用 和需求，分析 和设计正确 的算法的能 力。具有一般的 根据工程问 题实际应用 和需求，分析 和设计正确 的算法的能 力。基本具有根据 工程问题实际 应用和需求， 分析和设计正 确的算法的能 力。不具有根据工 程问题实际应 用和需求，分 析和设计正确 的算法的能 力。的能力。目标2. 3：具有很强 的根据设 计出的算 法，合理地 组织、存储 和处理数 据的能力。具有较强的 根据设计出 的算法，合理 地组织、存储 和处理数据 的能力。具有一般的 根据设计出 的算法，合理 地组织、存储 和处理数据 的能力。基本具有根据 设计出的算 法，合理地组 织、存储和处 理数据的能 力。不具有根据设 计出的算法， 合理地组织、 存储和处理数 据的能力。七、参考书目及学习资料.萨特吉萨尼（美）著，王立柱，刘志红译，数据结构、算法与应用：C+语言描述 （第2版），机械工业出版社，2015o1 .陈卫卫，王庆瑞主编，数据结构与算法（第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.22指标点2.2：应用数学、自然科学、 工程科学和专业知识的基本原理， 针对物联网工程领域的智慧标识和 感知、信息传送和智能处理等环节 的复杂工程问题进行抽象、描述和 表达。课程目标2.13指标点3.2：能够合理地组织、存 储和处理数据，根据各类资源作用 及特定需求，正确地进行算法和模 块设计。课程目标2.2课程目标2.34指标点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.31个空的顺序表L c,将La与Lb 的内容合并到L c中，使得Lc 也是有序的，并2验证入和合并等算 法并能灵活运 用这些算法。目标2.4目标3.1输出Lc中的内 容。2链表的创立 与应用分别采用逆序 和正序两种方 法创立链表，输 出链表的内容； 然后将链表的 前m个结点与 后n个结点整 体对调，输出对 调后链表中的 内容。2验证掌握链表的构 造、查找等算 法并灵活运用 这些算法。目标2.3目标2.4目标3.13栈的应用一 表达式括弧 匹配检查假设一个算术 表达式中包含 假设数学表达 式中允许包含 两种括号:圆括 号()和方括号 口；嵌套顺序任 意，编写一个算 法用于判别表 达式中括弧是 否能够正确匹 配。2设计掌握栈的特 性、栈的基本 操作，并能应 用栈解决具有 后进先出特性 的问题。目标2.3目标2.4目标3.14循环队列的 创立与应用假设循环队列 的最大长度为 n,现在依次将 m个数据入队 歹U，接着进行k 次出队列的操 作，再将，个数 据入队列，最后 从对头到队尾 依次输出队列 中的元素。2验证掌握队列的特 性、循环队列 的基本操作， 并能对其进行 简单应用。目标2.3目标2.4目标3.15二叉树的创 建与遍历根据给定的二 叉树，先人工对 其进行先序遍 历,根据先序遍 历的结果编写 程序创立该二 叉树；然后用非 递归中序遍历 算法，输出中序2设计掌握二叉树的 创立、遍历的 基本算法，并 对其进行简单 应用。目标2.3目标2.4目标3.1遍历的结果。6图的创立与 遍历对给定的无向 图图，实现图的 深度优先遍历 和广度优先遍 历算法并输出 相应的结果。2设计掌握图的邻接 表的存储方 法、深度优先 以及广度优先 的算法。目标2.3目标2.4目标3.17哈希表的创 建与查找针对某个图书 馆中的书号，设 il个哈希表， 完成相应的建 表和查表算法。2设计掌握哈希函数 的构造方法， 处理冲突的机 制以及查找的 算法。目标2.3目标2.4目标3.18快速排序算 法实现对给定的无序 数组用快速排 序算法进行排 序，要求能输 出每一次分划 后的结果以及 最终排序结果。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 ：实验报告 格式规范， 文字严谨， 内容正确， 条理性好，实验报告格 式规范，文字 严谨，内容比 较正确，条理 性好，无抄袭实验报告格 式比拟规范， 文字比拟严 谨，内容正 确，条理性实验报告格式 基本规范，文 字严谨，内容 基本正确，条 理性好，无抄实验报告有明 显的抄袭痕 迹，不能正确 问答所提的问 题。