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

《数据结构》课程教学大纲 课程英文名称：Data Structure 课程编码：Z108006 总学分：4 总学时：64 理论学时：48 实验学时：16 课程性质：专业基础必选核心课程 开课单位：信息科学与技术学院 大纲制定者：高攀 大纲审定者： 审定日期： 课程简介： 本课程是计算机相关专业的专业基础必选核心课程。在计算机科学中，数据结构不仅是一般程序 设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基 础。数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对 算法性能的分析。通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理 和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适 当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程 的学习过程也是讲行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养 学生的数据抽象能力和程序设计的能力。 一、课程的地位与作用 本课程为必修课程。数据结构是介于数学，计算机硬件和计算机软件三者之间的一门核心课程 它是一门综合性的专业基础必选核心课程。 通过本课程的学习，培养学生分析问题、解决问题的能力，学会对处理的数据建立抽象数据类型 利用抽象数据类型进行程序设计。掌握对典型的数据结构的各种基本操作，并使学生对算法的复杂度 有一定的分析能力。 二、课程的教学目标与基本要求 1.教学目标 要求学生通过学习，掌握基本算法和数据结构，它是学习操作系统、编译原理、数据库原理等 算机专业核心课程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。 2.基本要求 本课程在整个学习过程中安排有课堂讲授、课后作业、上机实验、课程设计、期中考试和期未考 试、自学研究等环节。课堂讲授要求采用多媒体课件并结合算法演示软件进行教学，以教师讲授为主 同时应贯穿师生讨论及课堂训练等多种教学方式。 三、课程知识单元与知识点 第1章绪论 1.1数据结构的研究内容 1.2基本概念和术语 1.3抽象数据类型的表示与实现 1.4算法和算法分析 1.5小结 第2章线性表

《数据结构》课程教学大纲 课程英文名称： Data Structure 课程编码：Z108006 总学分：4 总学时：64 理论学时：48 实验学时：16 课程性质：专业基础必选核心课程 开课单位：信息科学与技术学院 大纲制定者： 高攀 大纲审定者： 审定日期： 课程简介： 本课程是计算机相关专业的专业基础必选核心课程。在计算机科学中，数据结构不仅是一般程序 设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基 础。数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对 算法性能的分析。通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理 和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适 当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程 的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养 学生的数据抽象能力和程序设计的能力。 一、课程的地位与作用 本课程为必修课程。数据结构是介于数学，计算机硬件和计算机软件三者之间的一门核心课程, 它是一门综合性的专业基础必选核心课程。 通过本课程的学习，培养学生分析问题、解决问题的能力，学会对处理的数据建立抽象数据类型， 利用抽象数据类型进行程序设计。掌握对典型的数据结构的各种基本操作，并使学生对算法的复杂度 有一定的分析能力。 二、课程的教学目标与基本要求 1. 教学目标 要求学生通过学习，掌握基本算法和数据结构，它是学习操作系统、编译原理、数据库原理等计 算机专业核心课程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。 2. 基本要求 本课程在整个学习过程中安排有课堂讲授、课后作业、上机实验、课程设计、期中考试和期未考 试、自学研究等环节。课堂讲授要求采用多媒体课件并结合算法演示软件进行教学，以教师讲授为主， 同时应贯穿师生讨论及课堂训练等多种教学方式。 三、课程知识单元与知识点 第 1 章 绪论 1.1 数据结构的研究内容 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.5 小结 第 2 章 线性表

2.1线性表的类型定义 22线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4线性表的应用 2.5小结 第3章栈和队列 3.1栈 32栈的应用 3.3栈与递归 3.4队列 3.5队列的应用 3.6小结 第4章串、数组和广义表 41串 4.2数组 43广义表 4.4小结 第5章树和二叉树 5.1树的定义和基本术语 52二叉树 5.3遍历二叉树和线索二叉杨树 5.4树和森林 55林夫号树及其应用 5.6小结 第6意图 6.1图的定义和基本术语 6.2图的存储结构 6.3图的遍历 6.4图的应用 6.5小结 第7章查找 7.1查找的基本概念 7.2线性表的查找 7.3树表的查找 7,3.1二叉排序树 7.3.4B+树 7.4散列表的查找 7.5小结 第8章排序 8.1基本概念和排序方法概述

2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 线性表的应用 2.5 小结 第 3 章 栈和队列 3.1 栈 3.2 栈的应用 3.3 栈与递归 3.4 队列 3.5 队列的应用 3.6 小结 第 4 章 串、数组和广义表 4.1 串 4.2 数组 4.3 广义表 4.4 小结 第 5 章 树和二叉树 5.1 树的定义和基本术语 5.2 二叉树 5.3 遍历二叉树和线索二叉树 5.4 树和森林 5.5 赫夫曼树及其应用 5.6 小结 第 6 章 图 6.1 图的定义和基本术语 6.2 图的存储结构 6.3 图的遍历 6.4 图的应用 6.5 小结 第 7 章 查找 7.1 查找的基本概念 7.2 线性表的查找 7.3 树表的查找 7.3.1 二叉排序树 7.3.4 B+树 7.4 散列表的查找 7.5 小结 第 8 章 排序 8.1 基本概念和排序方法概述

82插入排疗 8.3交换排序 8.4选择排序 85归并排序 8.6基数排序 87小结 四、时间分配（黑体小四，表格内为五号宋体，以下为范例，教学环节可根据课程特点自行 加列) 教学环节（学时） 知识 单元 知识点 实 课 1 绪论 2 2 2 线性表 8 2 10 栈和队列 6 8 4 串、数组和广义表 4 4 树和二叉树 8 4 12 10 7 查找 2 8 0 排序 6 4 10 总计 16 64 五、课程其他说明（黑体小四，表格内为五号宋体） 1、主要先修课程：程序设计基础、高等数学、计算机组成原理 2、适用专业类别：计算机科学与技术、电子信息工程、信息管理与信息系统 3、主要教材：严蔚敏等.数据结构(C语言版)，北京：清华大学出版社： 4、考核方式及成绩构成：闭卷考试，平时成绩30%，期末试卷考试成绩70% 六、实验项目及要求（黑体小四，表格内为五号宋体，纯理论课程不填此项内容，此 表仅用于理论含实验课程的实验部分) 实验项 实验内容 学 实验 目名称 类型 顺序表 顺序表的表示；顺序表的初始化、插入、剧除、查找等操作。 验证性 2 链表 链表的表示：链表的初始化、插入、刷除、查找等操作。 验证性 表达式计 先将中缀表达式（就是我们通常所见的）转换为后缀表达式，比如 a+bc+d要变成abc*+d+:转换的方法用栈来实现，涉及到运算符的优 2 验证性 先级：然后用另一个栈来对表达式计算结果

8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 小结 四、时间分配（黑体小四，表格内为五号宋体，以下为范例，教学环节可根据课程特点自行 加列） 知识 单元 知 识 点 教学环节（学时） 讲 课 研 讨 课 实 验 上 机 课 外 小 计 1 绪论 2 2 2 线性表 8 2 10 3 栈和队列 6 2 8 4 串、数组和广义表 4 4 5 树和二叉树 8 4 12 6 图 8 2 10 7 查找 6 2 8 8 排序 6 4 10 总 计 48 16 64 五、课程其他说明（黑体小四，表格内为五号宋体） 1、主要先修课程：程序设计基础、高等数学、计算机组成原理 2、适用专业类别：计算机科学与技术、电子信息工程、信息管理与信息系统 3、主要教材：严蔚敏等. 数据结构（C 语言版），北京：清华大学出版社； 4、考核方式及成绩构成：闭卷考试，平时成绩 30%,期末试卷考试成绩 70%。 六、实验项目及要求（黑体小四，表格内为五号宋体，纯理论课程不填此项内容，此 表仅用于理论含实验课程的实验部分） 序 号 实验项 目名称 实验内容 学 时 实验 类型 1 顺序表 顺序表的表示 ；顺序表的初始化、插入、删除、查找等操作。 2 验证性 2 链表 链表的表示 ；链表的初始化、插入、删除、查找等操作。 2 验证性 3 表达式计 算 先将中缀表达式（就是我们通常所见的）转换为后缀表达式，比如 a+b*c+d 要变成 abc*+d+；转换的方法用栈来实现，涉及到运算符的优 先级；然后用另一个栈来对表达式计算结果 2 验证性

根据给定一串字符（或一个文本文件），自动生成n个权值( Ti中只有 其中每棵 4 Huffman 综码 的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右 2 验证 子树权值之和：在F中删除这两棵树，同时将新得到的二叉树加入F中： 4.重复2,3，直到F只含一棵树为止：然后求出每个字符对应的Huffmar 编码，继而求出整个字符串（或文本文件）的Huffman码流 根据输入的弧，生成AE-网。从始点开始，找出到终点的多条路径， 关键路径 求这些路径上的关键活动。由关键活动组成的从始点到终点的路径，即 2 验证 为关键路径。 给定若干个路由器（顶点）及各路由器之间的代价值（顶点之间的权值）， 最短路经 求从指定路由器（始点v0》开始，到其它各路由器（其余各顶点）的 最短路径，直到所有路由器（顶点）计算完成为止 给定一个记录关键字的值，与二叉排序树的根结点值比较，如果小于根 二叉排序 结点的值，则向左子树查找： 如果大于根结点的值，则向右子树查找 如果查找到叶子结点leaf,仍没有找到记录，则：如果关键字的值小 2 验证 树 于leaf的值，则插入该leaf结点的左边，做leaf的左孩子，否则做 1caf的右孩子 先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待 希尔排序 整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排 2 验证 快速排序 通过一趟将待排记录分割成独立的两个部分，其中一部分记录的关键子 均比另一部分记录的关键字小。再对两个部分分别进行快速排序。 验证 10 堆排序 首先将一个无序序列建成一个堆：然后输出堆顶元素：在输出堆顶元素 2 之后，调整剩余的元素成为一个新堆。 验证

4 Huffman 编码 根据给定一串字符（或一个文本文件），自动生成 n 个权值(w1, w2,.,wn)构成 n 棵二叉树的集合 F={T1, T2,.,Tn}，其中每棵二叉树 Ti 中只有一个带树为 Ti 的根结点；在 F 中选取两棵根结点的权值最小 的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右 子树权值之和；在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中； 4.重复 2, 3，直到 F 只含一棵树为止；然后求出每个字符对应的 Huffman 编码，继而求出整个字符串（或文本文件）的 Huffman 码流 2 验证 5 关键路径 根据输入的弧，生成 AOE-网。从始点开始，找出到终点的多条路径， 求这些路径上的关键活动。由关键活动组成的从始点到终点的路径，即 为关键路径。 2 验证 6 最短路经 给定若干个路由器（顶点）及各路由器之间的代价值（顶点之间的权值）， 求从指定路由器（始点 v0）开始，到其它各路由器（其余各顶点）的 最短路径，直到所有路由器（顶点）计算完成为止 2 设计 7 二叉排序 树 给定一个记录关键字的值，与二叉排序树的根结点值比较，如果小于根 结点的值，则向左子树查找；如果大于根结点的值，则向右子树查找。 如果查找到叶子结点 leaf，仍没有找到记录，则：如果关键字的值小 于 leaf 的值，则插入该 leaf 结点的左边，做 leaf 的左孩子，否则做 leaf 的右孩子 2 验证 8 希尔排序 先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待 整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排 序 2 验证 9 快速排序 通过一趟将待排记录分割成独立的两个部分，其中一部分记录的关键字 均比另一部分记录的关键字小。再对两个部分分别进行快速排序。 2 验证 10 堆排序 首先将一个无序序列建成一个堆；然后输出堆顶元素；在输出堆顶元素 之后，调整剩余的元素成为一个新堆。 2 验证 5