数据结构教学大纲

XX师范学院大学本科专业教学大纲中文课程名称：数据结构

英文课程名称：Data Structures

适用专业：信息管理与信息系统

制定单位：商学院

执笔人：

审核人：

单位负责人：

制定时间：2017-2-10

XX师范学院教务处

二〇一七年一月

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

一、课程基本信息

（一）课程代码及课程名称

1.课程代码：06151090

2.课程名称（中/英文）：数据结构/Data Structures

（二）课程类别及课程性质

专业教育必修课程

（三）学时及学分：

总学时数：64；总学分数：3。

其中，讲授学时：32 ，实践（实验）学时：32。

（四）适用专业及开设学期

适用专业：信息管理与信息系统（本科）

开设学期：第二学期

（五）先修课程与后续课程

先修课程：大学计算机基础、高等数学、C语言程序设计

后续课程：数据库原理与应用、管理信息系统分析与设计、管理信息系统、Java程序设计(高级)

二、课程简介

“数据结构”是信息管理与信息系统专业一门重点专业基础课程，也是学科专业核心专业基础课程之一，属于专业学位必修课程。本课程的教学任务是针对大量的信息处理对象，介绍对象信息与数据表示的各种抽象的、基本的逻辑结构及其上的基本运算操作。通过研究各种基本数据结构内在的逻辑关系和它们在计算机中的存储表示方式，初步建立数据结构上基本运算操作的正确性概念，同时，结合各种典型问题讨论其上的各种基本运算操作及其基本算法，讲授各种数据结构的特点、适用范围，以及对一些基本算法效率的定性和定量分析方法，为后续课程提供必要的数据结构基础。此外，配合实验课程的教学中，学生应理论联系

实际，理论指导实践，通过规范地完成一系列数据结构实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高。

三、教学目的与基本要求

（一）该课程教学目的与专业培养要求对应关系矩阵

说明：表格要清晰展示该课程与每项培养要求达成的关联度情况，关联度强的用“●”标识，关联度中等的用“◎”标识，关联度弱的用“○”标识；每门课程与4-8项（底线为总培养要求的50%）培养要求相关联。

（二）教学目的

《数据结构A》在计算机科学中是一门综合性的专业基础课，不仅是一般程序设计的基础，而且是设计和实现操作系统、数据库系统、编译程序及其它系统程序和大型应用程序的重要基础。本课程讨论各种数据组织中的数据的逻辑结构、存储结构以及有关操作的算法。目的是使学生学会分析研究计算机所要加工处理的数据的特征，掌握组织数据、存储数据和处理数据的基本方法，并加强在实际应用中选择合适的数据结构和设计相应算法的训练，课程的具体教学目的如下：

数据结构与算法是计算机科学教育中的一门核心课程。数据结构与算法主要讨论在应用计算机解决问题时，如何有效地组织数据、表示数据和处理数据，以及如何设计正确的算法和评价算法的效率。课程介绍常见的数据结构及其应用，常用的数据处理技术和算法，以及算法效率估算的基本技术。通过本课程的学习，学生应该掌握常用的数据结构，掌握合理地组织数据结构和表示数据的方法，掌握有效地处理数据的方法，掌握评价算法性能的基本方法。通过本课程的训练，进一步提高学生的数据抽象能力；提高学生设计高质量程序的能力。本课程也为学生学习操作系统、编译原理和数据库等后续课程奠定基础。

1. 知识方面

1.1理解数据结构的一些基本概念、理解并掌握算法的描述方法，理解并掌握算法的时间复杂度和空间复杂度的概念以及分析方法。

1.2理解各种数据结构的基本概念，深刻理解各种数据结构的逻辑特性，理解并熟练掌握各种数据结构的存储表示方法，理解并掌握在各种数据结构基础上的算法设计与描述，并理解和掌握对算法性能进行分析的方法以及分析结果。

1.3理解查找、排序的基本概念，掌握各种查找、排序方法及其算法描述和性能分析方法和分析结果。

2. 能力与素质方面

2.1 具备依据工程实际问题的需求合理地组织数据，并在计算机中有效地存储数据的能力。

2.2 具备为解决工程实际问题进行算法设计与分析的能力。

2.3 具备将算法通过具体的编程语言加以实现的能力。

（三）教学要求：

通过本课程的学习，在基础方面，要求学生能够掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。总言之，使应用者较全面的掌握各种常用的数据结构，提高运用数据结构解决实际问题的能力。

1.掌握数据结构的概念及术语。

2.掌握线性表（栈、队列）的存储结构（顺序和链式存储）、算法描述及应用。

3.掌握数组的顺序存储和特殊矩阵的压缩存储。

4.掌握树的基本概念和术语，掌握二叉树的基本性质和特点、存储结构及算法描述、二叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。

5.掌握图的基本概念和术语、存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）、图的遍历、图的连通性（最小生成树）。

6.掌握查找的基本概念、基于线性表的查找方法（顺序、折半）。

7.掌握插入类排序（直接、折半、表、希尔等插入排序）、交换类排序（冒泡、快速排序）。

四、教学内容

（一）绪论（共4学时）

（一）教学目的和要求

介绍数据结构课程的研究对象，基本术语，掌握算法的要领，描述算法的类语言。了解数据结构的发展概况及其在计算机中的地位。

（二）教学重点与难点

教学重点：

1、熟悉各名词、术语的含义，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质；

2、了解抽象数据类型的定义、表示和实现方法；

3、理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）；

4、掌握计算语句频度和估算算法时间复杂度的方法。

教学难点：

1、掌握数据结构的意义及数据结构的基本内容；

2、掌握数据结构及数据、数据元素等相关概念；

3、掌握算法描述的方法；

4、算法时间复杂度的计算。

（三）教学内容