数据结构A
（Data Structures A）
课程编号： 06311360
学 分： 5.0
学 时： 75 （其中：讲课学时：60 实验学时：0 上机学时：15）
先修课程：离散数学、程序设计基础、面向对象程序设计
适用专业：计算机科学与技术
教 材：《数据结构—C++实现（第二版）》，缪淮扣等，科学出版社，2014年第二版
开课学院：计算机科学与通信工程学院
一、课程目标
《数据结构A》在计算机科学中是一门综合性的专业基础课，不仅是一般程序设计的基础，而且是设计和实现操作系统、数据库系统、编译程序及其它系统程序和大型应用程序的重要基础。本课程讨论各种数据组织中的数据的逻辑结构、存储结构以及有关操作的算法。目的是使学生学会分析研究计算机所要加工处理的数据的特征，掌握组织数据、存储数据和处理数据的基本方法，并加强在实际应用中选择合适的数据结构和设计相应算法的训练，课程的具体目标如下：
1. 知识方面
1.1理解数据结构的一些基本概念、理解并掌握算法的描述方法，理解并掌握算法的时间复杂度和空间复杂度的概念以及分析方法。
1.2理解各种数据结构的基本概念，深刻理解各种数据结构的逻辑特性，理解并熟练掌握各种数据结构的存储表示方法，理解并掌握在各种数据结构基础上的算法设计与描述，并理解和掌握对算法性能进行分析的方法以及分析结果。
1.3理解查找、排序的基本概念，掌握各种查找、排序方法及其算法描述和性能分析方法和分析结果。
2. 能力与素质方面
2.1 具备依据工程实际问题的需求合理地组织数据，并在计算机中有效地存储数据的能力。
2.2 具备为解决工程实际问题进行算法设计与分析的能力。
2.3 具备将算法通过具体的编程语言加以实现的能力。
二、课程目标与专业毕业要求指标点的对应关系
指标点2.3：具备将工程基础知识用于计算机领域复杂工程问题进行求解的能力。
指标点3.1：具备对计算机领域复杂工程问题进行识别和有效分解的能力。
指标点3.2：具备对分解后的计算机领域复杂工程问题进行表达与建模的能力。
指标点6.3：理解离散结构、计算模型在计算机问题求解中的意义与基本运用。
课程目标
| 毕业要求指标点 | 指标点2.3 | 指标点3.1 | 指标点3.2 | 指标点6.3 |
| 课程目标1.1 | √ | |||
| 课程目标1.2 | √ | √ | √ | √ |
| 课程目标1.3 | √ | √ | √ | √ |
| 课程目标2.1 | √ | √ | √ | |
| 课程目标2.2 | √ | √ | √ | |
| 课程目标2.3 | √ |
三、课程内容及要求
第一章 绪论
本章支持课程目标：1.1理解数据结构的一些基本概念、理解并掌握算法的描述方法，理解并掌握算法的时间复杂度和空间复杂度的概念以及分析方法。
（一）教学内容与教学方法
1. 数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。（讲授）
2. 算法时间复杂度和空间复杂度的分析。（讲授）
（二）知识、能力与素质等方面的基本要求
1. 了解本课程的性质、任务和目的。
2. 掌握数据结构的一些基本概念。
3. 具有对算法的时间复杂度和空间复杂度进行分析的能力。
4. 了解算法的描述方法。
（三）重点与难点
1. 重点
数据、数据元素、数据项；逻辑结构和存储结构在概念上的联系与区别；评价算法优劣的标准及方法。
2. 难点
算法与程序的区别；逻辑结构、存储结构的联系与区别；算法的时间复杂度分析方法。
第二章 线性表
本章支持课程目标：1.2理解各种数据结构的基本概念，深刻理解各种数据结构的逻辑特性，理解并熟练掌握各种数据结构的存储表示方法，理解并掌握在各种数据结构基础上的算法设计与描述，并理解和掌握对算法性能进行分析的方法以及分析结果；2.1 具备依据工程问题的需求合理地组织数据，并在计算机中有效地存储数据的能力；2.2 根据数据结构的基本概念、原理和方法，具备算法设计与分析的能力；2.3 具备将算法通过具体的编程语言加以实现的能力。
（一）教学内容与教学方法
1. 线性表的基本概念和类型定义。（讲授）
2. 线性表的顺序存储表示及基本操作的实现。（讲授+演示）
3. 线性表的链式存储表示及基本操作的实现（单链表、循环链表、双向链表、静态链表）。（讲授+演示）
4. 一元多项式的表示及相加。（讲授+演示）
（二）知识、能力与素质等方面的基本要求
1. 掌握线性表的基本概念和类型定义。
2. 熟练掌握顺序表和单链表上的基本操作方法及其算法实现能力。
3. 掌握循环链表和双向链表的定义和它的插入、删除等操作方法。
4. 了解一元多项式的表示及相加运算。
（三）重点与难点
1. 重点
顺序表和链式表（单链表、双向链表）的基本操作。
2. 难点
链式表（单链表、双向链表）的基本操作以及一元多项式的相加运算。
第三章 栈和队列
本章支持课程目标：1.2理解各种数据结构的基本概念，深刻理解各种数据结构的逻辑特性，理解并熟练掌握各种数据结构的存储表示方法，理解并掌握在各种数据结构基础上的算法设计与描述，并理解和掌握对算法性能进行分析的方法以及分析结果；2.1 具备依据工程问题的需求合理地组织数据，并在计算机中有效地存储数据的能力；2.2 根据数据结构的基本概念、原理和方法，具备算法设计与分析的能力；2.3 具备将算法通过具体的编程语言加以实现的能力。
（一）教学内容与教学方法
1. 栈的定义，栈的顺序存储表示、链式存储表示及基本操作的实现，栈的应用（表达式计算）。（讲授+案例+演示）
2. 队列的定义，队列的顺序存储表示（循环队列）、链式存储表示（链队列）及基本操作的实现。（讲授+案例+演示）
3. 递归。
（二）知识、能力与素质等方面的基本要求
1. 掌握栈和队列的定义。
2. 熟练掌握顺序存储表示及链式存储表示的栈和队列的基本操作的方法以及算法实现。
3. 掌握表达式求值等方法，具有利用栈求解后缀表达式、将中缀表达式转换成后缀表达式的能力。
4. 了解递归的概念。
（三）重点与难点
1. 重点
栈和队列的顺序存储表示、链式存储表示及基本操作的实现。
2. 难点
顺序栈的溢出判断条件；循环队列的队空、队满判断条件；递归。
第四章 串、数组和广义表
本章支持课程目标：1.2理解各种数据结构的基本概念，深刻理解各种数据结构的逻辑特性，理解并熟练掌握各种数据结构的存储表示方法，理解并掌握在各种数据结构基础上的算法设计与描述，并理解和掌握对算法性能进行分析的方法以及分析结果；2.1 具备依据工程问题的需求合理地组织数据，并在计算机中有效地存储数据的能力；2.2 根据数据结构的基本概念、原理和方法，具备算法设计与分析的能力。
（一）教学内容与教学方法
1. 串的基本概念。（讲授）
2. 数组的定义以及顺序存储结构。（讲授）
3. 特殊矩阵和稀疏矩阵的定义、存储和操作。（讲授+演示）
4. 广义表的定义。（讲授）
（二）知识、能力与素质等方面的基本要求
1. 了解串的基本概念。
2. 掌握数组的定义以及顺序存储结构，具有存储地址换算的能力。
3. 掌握特殊矩阵和稀疏矩阵的定义和压缩存储表示。
4. 掌握稀疏矩阵的转置方法并了解其算法。
5. 掌握广义表的定义。
（三）重点与难点
1. 重点
掌握数组的定义和数组的存储结构、特殊矩阵和稀疏矩阵的压缩存储、广义表的定义。
2. 难点
稀疏矩阵的压缩存储表示下的运算的实现。
第五章 树和二叉树
本章支持课程目标：1.2理解各种数据结构的基本概念，深刻理解各种数据结构的逻辑特性，理解并熟练掌握各种数据结构的存储表示方法，理解并掌握在各种数据结构基础上的算法设计与描述，并理解和掌握对算法性能进行分析的方法以及分析结果；2.1 具备依据工程问题的需求合理地组织数据，并在计算机中有效地存储数据的能力；2.2 根据数据结构的基本概念、原理和方法，具备算法设计与分析的能力；2.3 具备将算法通过具体的编程语言加以实现的能力。
（一）教学内容与教学方法
1. 树的定义、术语、表示形式、基本操作。（讲授+演示+案例）
2. 二叉树的定义、性质、基本操作、存储结构表示。（讲授）
3. 二叉树的各种遍历方法及实现。（讲授+演示+互动）
4. 线索二叉树。（讲授+演示）
5. 哈夫曼树及其应用。（讲授+演示+案例）
6. 树的存储结构表示，树、森林和二叉树的转换，树和森林的遍历。（讲授+演示）
（二）知识、能力与素质等方面的基本要求
1. 掌握树的定义、性质、存储结构以及树和森林的遍历算法。
2. 熟练掌握二叉树的定义、性质、存储结构。
3. 熟练掌握二叉树的各种遍历方法及其实现，并具有对二叉树进行遍历的能力。
4. 掌握二叉树的其他操作方法及实现。
5. 掌握线索二叉树的定义和算法实现，并具有将二叉树进行线索化的能力。
6. 熟练掌握树、森林与二叉树的转换方法。
7. 熟练掌握哈夫曼树及其应用。
（三）重点与难点
1. 重点
二叉树的概念、遍历及基本操作，二叉树的线索化方法，树的存储结构表示以及树、森林与二叉树的转换方法、树和森林的遍历方法，哈夫曼树及其应用。
2. 难点
二叉树上的复杂运算；线索二叉树的算法实现。
第六章 图
本章支持课程目标：1.2理解各种数据结构的基本概念，深刻理解各种数据结构的逻辑特性，理解并熟练掌握各种数据结构的存储表示方法，理解并掌握在各种数据结构基础上的算法设计与描述，并理解和掌握对算法性能进行分析的方法以及分析结果；2.1 具备依据工程问题的需求合理地组织数据，并在计算机中有效地存储数据的能力；2.2 根据数据结构的基本概念、原理和方法，具备算法设计与分析的能力；2.3 具备将算法通过具体的编程语言加以实现的能力。
（一）教学内容与教学方法
1. 图的定义、术语、基本操作。（讲授）
2. 图的各种存储结构表示。（讲授）
3. 图的深度优先遍历和广度优先遍历以及图的连通分量。（讲授+演示）
4. 图的生成树和最小生成树。（讲授+演示+案例）
5. 最短路径。（讲授+演示+案例+自学）
6. 活动网络。（讲授+演示+案例+自学）
（二）知识、能力与素质等方面的基本要求
1. 掌握图的定义和术语。
2. 熟练掌握图的存储结构表示方法。
3. 熟练掌握图的深度和广度优先搜索方法及其实现，并具有利用深度和广度优先搜索方法对图进行遍历的能力。
4. 熟练掌握求图的最小生成树的普里姆法和克鲁斯卡尔法并了解其实现算法，并具有利用普里姆法和克鲁斯卡尔法构造图的最小生成树的能力。
5. 掌握求解图的最短路径及其长度的方法并了解其实现算法，并具有构造单源点最短路径及其长度的能力。
6. 掌握拓扑排序的方法并了解其实现算法，并具有构造拓扑有序序列的能力。
（三）重点与难点
1. 重点
图的存储结构、深度和广度优先搜索方法及其实现、图的最小生成树的构造方法、图的最短路径及其长度的求解方法、有向无环图的拓扑有序序列的构造方法。
2. 难点
最小生成树、最短路径的算法思想及其算法实现、拓扑排序的算法实现。
第七章 查找
本章支持课程目标：1.3理解查找、排序的基本概念，掌握各种查找、排序方法及其算法描述和性能分析方法和分析结果；2.1 具备依据工程问题的需求合理地组织数据，并在计算机中有效地存储数据的能力；2.2 根据数据结构的基本概念、原理和方法，具备算法设计与分析的能力；2.3 具备将算法通过具体的编程语言加以实现的能力。
（一）教学内容与教学方法
1. 查找的基本概念。（讲授）
2. 顺序表的查找、有序表的折半查找以及索引顺序表查找。（讲授+演示+案例+对比）
3. 二叉排序树定义、查找、插入、删除以及查找性能的分析。（讲授+演示+对比）
4. 平衡二叉树的定义以及平衡旋转。（讲授+演示+对比+自学）
5. 散列表的基本概念、散列函数、处理溢出的闭散列方法和开散列方法以及散列表查找分析。（讲授+演示）
（二）知识、能力与素质等方面的基本要求
1. 了解查找的基本思想及查找成功和不成功的概念，熟练掌握平均查找长度和最大查找长度的定义和计算方法。
2. 熟练掌握在顺序表、有序表上的查找方法及其算法实现，并具有对顺序表、有序表、索引顺序表进行查找分析的能力。
3. 熟练掌握二叉排序树的插入、查找方法及其算法实现，并具有对二叉排序树进行查找分析的能力，了解二叉排序树的删除操作及其算法实现。
4. 了解平衡二叉树的平衡旋转和构造过程。
5. 熟练掌握散列表的构造方法，并具有对散列表进行查找和分析的能力。
（三）重点与难点
1. 重点
顺序表的查找、二叉排序树的查找和插入以及查找性能的分析、散列表的构造方法以及查找性能的分析。
2. 难点
二叉排序树删除操作的算法实现、平衡二叉树的平衡旋转和构造过程。
第八章 排序
本章支持课程目标：1.3理解查找、排序的基本概念，掌握各种查找、排序方法及其算法描述和性能分析方法和分析结果；2.1 具备依据工程问题的需求合理地组织数据，并在计算机中有效地存储数据的能力；2.2 根据数据结构的基本概念、原理和方法，具备算法设计与分析的能力；2.3 具备将算法通过具体的编程语言加以实现的能力。
（一）教学内容与教学方法
1. 基本概念。（讲授）
2. 插入排序。（讲授+演示+对比）
3. 交换排序。（讲授+演示+对比）
4. 选择排序。（讲授+演示+对比）
5. 归并排序。（讲授+演示）
6. 基数排序。（讲授+演示+对比）
7. 各种内部排序方法的比较讨论。（讲授+对比）
（二）知识、能力与素质等方面的基本要求
1. 领会排序的基本思想和基本概念，理解稳定性的概念。
2. 理解并掌握各种排序方法的基本思想、步骤、算法，并具有时空效率分析的能力。
3. 了解各种典型的内部排序算法的特点和适用范围。
（三）重点与难点
1. 重点
各种排序方法及时空效率分析。
2. 难点
快速排序、堆排序及其算法实现。
四、学时分配及教学方法及对毕业要求指标点的支撑
| 章 | 课时分配 | 教学方法 | 对指标点的支撑 | |||
| 讲课 | 实验 | 上机 | 课外 | |||
| 第一章 绪论 | 3 | 0 | 讲授 | 6.3 | ||
| 第二章 线性表 | 10 | 4 | 讲授+演示 | 2.3，3.1，3.2，6.3 | ||
| 第三章 栈、队列和递归 | 5 | 0 | 讲授+案例+演示 | 2.3，3.1，3.2，6.3 | ||
| 第四章 串、数组和广义表 | 6 | 0 | 讲授+演示 | 2.3，3.1，3.2，6.3 | ||
| 第五章 树和二叉树 | 10 | 4 | 讲授+演示+案例+互动 | 2.3，3.1，3.2，6.3 | ||
| 第六章 图 | 10 | 3 | 讲授+演示+案例+自学 | 2.3，3.1，3.2，6.3 | ||
| 第七章 查找 | 8 | 2 | 讲授+案例+演示+对比+自学 | 2.3，3.1，3.2，6.3 | ||
| 第八章 排序 | 8 | 2 | 讲授+演示+对比 | 2.3，3.1，3.2，6.3 | ||
| 合计 | 60 | 15 | ||||
五、本课程开设的实验项目
| 编号 | 实验项目名称 | 学时 | 类型 | 要求 | 备注 |
| 1. 1 | 线性表操作 | 4 | 设计性 | 必做 | |
| 2. | 二叉树操作 | 4 | 设计性 | 必做 | |
| 3. 2 | 图的操作 | 3 | 验证性 | 必做 | |
| 4. | 查找操作 | 2 | 设计性 | 必做 | |
| 5. | 内部排序操作 | 2 | 验证性 | 必做 |
实验一 线性表操作
1. 实验内容
单链表的创建、合并和输出。
2. 实验目的
(1) 熟悉用Visual C++进行程序设计的方法。
(2) 掌握单链表的创建、查找、插入和合并等运算。
3. 实验题目
本实验要求实现以下功能：
(1) 从键盘输入顺序任意的5个整数，按有序插入的要求生成第一个有序单链表，将该链表输出显示。
(2) 再从键盘输入顺序任意的5个整数，按有序插入的要求生成第二个有序单链表，将该链表输出显示。
(3) 将这两个有序单链表合并成一个有序单链表，要求使用两个单链表的原有空间进行合并，将生成的有序单链表输出显示。
4. 实验仪器设备
(1) 学生每个一台PC机。
(2) 已安装VS.net环境。
实验二 二叉树操作
1. 实验内容
二叉树的建立和遍历。
2. 实验目的
(1) 进一步掌握指针变量的使用。
(2) 掌握二叉树的结构特征以及各种存储结构的特点及使用范围。
(3) 掌握用指针类型描述、访问和处理二叉树的运算。
(4) 掌握栈或队列的使用。
3. 实验题目
本实验要求实现以下功能：
(1) 按前序次序建立一棵二叉树，以‘＃’表示空。
(2) 中序、后序遍历该二叉树，输出遍历序列。
(3) 求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。
(4) 试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅助存储结构实现二叉树的层次遍历算法。
4. 实验仪器设备
(1) 学生每个一台PC机。
(2) 已安装VS.net环境。
实验三 图的操作
1. 实验内容
图的生成和图的遍历。
2. 实验目的
(1) 掌握图的基本存储方法——邻接表和邻接矩阵。
(2) 熟练掌握图的两种遍历方法。
3. 实验题目
本实验要求实现以下功能：
(1) 以邻接矩阵或邻接表作为存储结构建立一个无向图。
(2) 按深度优先遍历该无向图，输出遍历序列。
(3) 按广度优先遍历该无向图，输出遍历序列。
4. 实验仪器设备
(1) 学生每个一台PC机。
(2) 已安装VS.net环境。
实验四 查找操作
1. 实验内容
二叉排序树的建立、二叉排序树中结点的查找。
2. 实验目的
(1) 熟悉二叉排序树的定义。
(2) 理解二叉排序树的建立过程。
(3) 掌握二叉排序树中查找结点的算法。
3. 实验题目
本实验要求实现以下功能：
(1) 对从键盘输入的顺序任意的若干个正整数建立一颗二叉排序树，以-1作为结束。
(2) 按先序、中序和后序遍历该二叉排序树，输出每种遍历的结果。
(3) 从键盘输入一个整数，在二叉排序树中查找，给出是否查找成功的结果。
4. 实验仪器设备
(1) 学生每个一台PC机。
(2) 已安装VS.net环境。
实验五 内部排序操作
1. 实验内容
快速排序。
2. 实验目的
(1) 熟悉各种内部排序算法的思想。
(2) 理解快速排序算法。
3. 实验题目
本实验要求实现以下功能：对从键盘输入的顺序任意的8个正整数，通过各种排序（至少2个排序方法）使之成为有序的序列。输出每一趟排序的结果。
4. 实验仪器设备
(1) 学生每个一台PC机。
(2) 已安装VS.net环境。
注：本课程为专业基础课，授课对象为大二本科生，实验类型主要包括验证性实验和设计性实验，实验报告主要包括题目、实验内容、程序中使用的数据结构及符号说明、程序的主要流程图、程序主要模块的功能说明、程序运行时的初值和运行结果、收获及体会、源程序。实验评价内容与评分比重以及评分细则参见附录1。
六、课程考核与毕业要求达成度计算
（一）考核方式
| 考核方式或途径 | 考核要求 | 考核权重 | 对指标点支持 | 备注 |
| 平时作业 | 主要考核学生对课堂讲授的知识点的复习、理解和掌握程度，考核作业是否提交或按时提交、考核所完成作业的质量和正确程度。总分数平均计算（取5次作业） | 10% | 3.2（60%） 3.1（40%） | |
| 课堂和实验考勤 | 主要考核学生课堂听讲出勤情况、上机实验出勤情况。缺勤一次扣1分 | 10% | ||
| 实验 | 完成5个实验，主要考核对算法的理解，编程能力。 | 10% | 2.3（60%） 3.2（40%） | 评分细则见附录1 |
| 期末考试 | 闭卷 | 70% | 3.2（15%） 3.1（65%） 6.3（20%） |
（二）本课程毕业要求达成度计算
说明：课程指标点达成度为对应指标点部分的所有得分除以对应指标点在总评成绩的所占的总分数，对应指标点的得分包括平时作业部分、实验部分、期末考试成绩部分，其中n为总评成绩合格的学生数。
七、参考书目及学习资料
1.《数据结构（C语言版）》，严蔚敏，清华大学出版社，1997年第1版。
2.《数据结构（用面向对象方法与C++语言描述）》，殷人昆，清华大学出版社，2007年第2版。
3. 《数据结构、算法与应用:C++语言描述数据结构、算法与应用：C++语言描述（Data Structures,Algorithms,and Application in C++）》，[美]Sartaj，Sahni著，王立柱 等译，机械工业出版社，2015年第2版。
八、大纲说明
1. 采用多媒体和黑板相结合的教学手段，配合例题的讲解及适当的思考题，保证讲课进度的同时，注意学生的掌握程度和课堂的气氛。
2. 根据各章节的具体情况，课后可布置适当的书面作业或思考题，以加深学生对所学内容的理解和掌握。
3. 本课程有15个学时的实验，具体实验内容任课教师亦可以根据实际教学情况 适当调整。
制定人：施化吉
审定人：潘雨青
批准人：张建明
2015 年 9 月
附录1: 实验评价内容与评分比重以及评分细则
实验评价内容与评分比重
| 评分项编号 | 实验评价内容 | 所占比重 | 要求 | 对毕业要求指标点支撑 |
| 1 | 预习准备情况 | 20% | 要求明确实验要求、事先准备好相应的程序代码。 | 3.2 |
| 2 | 编程实现能力与运行结果 | 60% | 能够编程实现，给出运行结果。 | 2.3 |
| 3 | 报告清晰，按时提交 | 20% | 报告清晰，提交准时 | 3.2 |
注：具体评分细则见下表的实验评分细则。
实验评分细则（每次作业按100分计算）
| 项目 | 优秀（100-90） | 良好（80-） | 中等（70-79） | 及格（60-69） | 不及格（59及以下） |
| 预习准备情况 20分 | 明确实验要求、已准备好所有程序代码； 18-20分 | 明确实验要求、已准备了大部分程序代码； 16-17分 | 对实验要求较明确、已准备了部分程序代码； 14-15分 | 对实验要求理解得不够透彻、只有少量程序代码或只有一些简单的思路； 12-13分 | 对实验要求理解不明确，有极少或没有程序代码和思路； 11分及以下 |
| 编程实现能力与运行结果 60分 | 程序正确，运行结果正确且提示较为清晰和友好； 54-60分 | 程序正确，运行结果正确但提示不够清晰友好； 48-53分 | 程序能运行，但运行结果有少量错误； 42-47分 | 程序能运行，但运行结果不正确或程序错误较多无法运行或没有程序； 41-36分 | 只有个别程序能运行或程序错误较多无法运行或没有程序； 35分及以下 |
| 报告清晰，按时提交 20分 | 报告清楚，按时提交； 18-20分 | 报告较清楚，按时提交； 16-17分 | 报告清楚或较清楚，但未按时提交 14-15分 | 报告不清楚但按时提交 12-13分 | 报告不清楚也未按时提交 11分及以下 |
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
