数据结构理论(二)课程教学大纲

《数据结构》教学大纲

课程性质专业必修课

课程编号xx882034-2课程名称数据结构

适用专业物联网工程、计算机科学与技术、软件工程

先修课程C语言程序设计

总学时40学时学分数2.5

一、课程简介

《数据结构》是计算机科学与技术、软件工程、网络工程专业的核心课程，作为学

科的专业基础课，具有承上启下的重要作用。通过本课程的学习，使学生理解、掌握基

本数据结构的特点，了解数据结构与算法的关系，着重培养学生的算法设计与分析的基本

理论知识和技能,提高学生设计算法、设计合适的数据结构的能力。本课程强调理论和实

践的结合，突出对学生的动手能力的培养。在对学生进行基本数据结构的技术、理论、

设计等各种技能培养的同时，培养学生将实际问题转化为基本数据结构的问题的分析能

力，鼓励学生学以致用，将学到的知识用以解决实际问题，从而提高学生算法设计能力

和软件开发能力。

二、课程教学目标

通过本课程的学习，学生应实现如下目标：

1、知识目标：

了解：数据结构的基本概念、算法的时间复杂度的概念、串的基本操作、多维数组、

广度表、二叉树的相关递归与非递归算法、图的相关算法、外排序的相关算法思想等。

掌握：简单的时间复杂度的计算、顺序表的相关操作用插入、删除算法、单链表的

相关操作与插入删除算法、栈与队列的相关操作与插入删除算法、二叉树的基本性质及

二叉树的遍历及二叉树的简单的递归算法、哈夫曼树、树到二叉树的转换、图的基本概

念及图的最小生树、图的关键路径、最短路径等基本算法思想应用、查找的基本概念、

平均查找长度、折半查找树的生成、二叉排序树的生成、哈希表的生成及简单的内排序

（快速排序、堆排序、归并排序等）的应用等。

2、能力目标:

(1)对数据结构的分类与经典算法初步的认识和了解；

(2)掌握常见的顺序结构、链式结构、栈与队列的基本算法及简单应用；

(3)掌握树型结构基本算法中的递归与非递归算法及简单应用；

(4)在实训中，培养和锻炼学生运用相关算法解决问题、进行应用开发的能力,

为将来从事计算机方面的开发或计算机类管理奠定坚实的基础。

三、课程教学基本要求

为了更好地掌握本课程的知识，必须先修《C语言程序设计》、《离散数学》等课程,

要求同学们教室上课，课后按要求完成给定的习题或思考题。

四、课程教学模块(或教学内容)与学时分配

序号教学模块知识点学时

(1)掌握数据结构的基本概念

项目一

(2)了解抽象数据类型

1数据结构简3

(3)了解算法时间复杂度和空间复杂度的分析

介

(4)了解算法的描述方法。

(1)理解线性表的定义及其运算；

(2)理解顺序表和链表的定义、组织形式、结

项目二线性构特征和类型说明；

2表的基本操(3)掌握在顺序表和链表上实现的插入、删除6

作和按值查找的算法；

(4)了解循环链表、双(循环)链表的结构特点

和在其上施加的插入、删除等操作。

(1)理解栈的定义、特征及在其上所定义的基

本运算；

项目三栈与(2)掌握在两种存储结构上对栈所施加的基本

3队列的基本运算的实现；6

操作(3)理解队列的定义、特征及在其上所定义的

基本运算；

(4)掌握在两种存储结构上对队列所施加的基

本运算的实现

(1)了解串的逻辑定义；

项目四串的(2)掌握用顺序存储串及堆存储串时的特点及

4基本操作在这两种存储方式下基本操作的实现；2

(3)了解改进的模式匹配算法；

(1)掌握数组的顺序存储结构及特殊矩阵的存

项目五数组储方式；

53

及稀疏矩阵(2)了解稀疏矩阵的压缩存储方式一三元组表

(1)深刻理解二叉树的定义、性质及其存储方

法；

(2)熟练掌握二叉树的二叉链表存储方式、结

项目二叉树点结构和类型定义；

6的性质及基(3)理解并掌握二叉树的三种遍历算法；掌握8

本操作二叉树的线索化方法；

(4)灵活运用二叉树的遍历方法解决相关的应

用问题。

(1)理解图的基本概念及术语；

(2)掌握图的两种存储结构(邻接矩阵和邻接

表)方法；

(3)熟练掌握图的两种遍历(深度优先搜索遍

项目七图的历和广度优先搜索遍历)的算法思想、步骤，并

76

基本操作能列出在两种存储结构上按上述两种遍历算法

得到的序列；

(4)理解最小生成树的概念，能按Prim算法

构造最小生成树；

(5)领会拓扑排序、关键路径、最短路径的算

法思想

(1)了解查找的基本思想及查找成功和不成功

的概念；

(2)掌握在顺序表、有序表、索引表、散列表

8项目八查找等上的查找方法和算法，并能求出相应的平均4

查找长度；

(3)理解并掌握二叉排序树的各种算法

1)领会排序的基本思想和基本概念；

(2)理解并掌握插入排序、冒泡排序、快速排

项目九内排

9序、直接选择排序、堆排序、归并排序和基数2

序

排序的基本思想、步骤和时空效率分析

五、教学方法与策略

1、讲授法：从数据结构的基本概念及数据应用与组织入手，讲授数据的四种结构

及四种结构的表示方式及在内存的组织方法及各种方法的具体实现。在程序设计中注意

培养学生的独立编写程序的能力，注意培养学生的创新能力和进取精神。

2、实验课：掌握线性结构与树型结构的典型算法。在程序设计训练中，由顺序到

链式再到栈与列、队列、二叉树，由易到难，在指导学生的过程中要注重启发学生的思

维与培养学生的创新意识扎扎实实练好基本功。

六、学生学习成效考核方式

考核环节构成占总成绩

评分依据

(均为100分制)的比重

上课出勤与作业上课缺席一次扣2分，缺课达1/3取消资格。30%

期末考试成绩70%

七、选用教材

⑴严蔚敏,吴伟民.