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

课程名称（中文/英文）:数据结构（Data Structure）

课程编号:9631214　　　　　　

课程类别:专业必修课

适用专业:信息管理与信息系统、计算机科学与技术（计算机应用、软件工程、网络工程）

总学时数:90，其中讲授:54 学时；上机:　0学时；实验:36 学时；课外: 0 学时

制订单位:华南师范大学增城学院计算机系

一、教学大纲说明

1.课程的地位、作用和任务

本课程是计算机专业的重要基础技术课程，通过讨论数据的各种逻辑结构、物理结构以及相关算法，使学生能根据实际问题的需要选择合适的数据结构和设计算法，并为学习数据库、操作系统等后继课程打下基础。

2.课程教学的目的和要求

本课程的教学要求是:要求学生学会分析要求计算机加工的数据对象的特性，以便选择适当的数据逻辑结构和存储结构以及相应的算法，并初步掌握算法的时间分析和空间分析的技巧。另一方面，学习本课程的过程也是进行复杂程序设计的训练过程，训练学生应用各种典型算法进行具体应用问题的程序设计，这包括程序中变量设计、函数中参数设计、程序的书写格式等方面的训练，要求学生书写的程序结构清楚，正确易读。

3.课程教学改革设想

本课程以培养学生实践能力为中心，在教学中针对不同知识点采取不同教学策略，注重培养学生解决实际问题的能力，在实践课中添加大量练习。并开设了《数据结构课程设计》课程，培养学生解决综合问题的能力。

4.课程与其它课程的联系

本课程为专业基础课，在一门语言课作为先行课的基础上，作为其他专业主干课程的先行课。

5.教材与教学参考书

1）《数据结构》（C语言版本） 严蔚敏 编 清华大学出版社

2）《数据结构》中国轻工业出版社

3）《使用数据结构题解》 清华大学出版社 徐士良 编著

6.考试改革设想及成绩计算方法

在考试题目类型的选择上，加大对主观知识考核的比例，在传统题型的分值上做调整，并增加与专业、生活有关的应用题。期末成绩由以下几方面组成:期末笔试，期末机试，平时作业和上机作业（包括独立完成情况和理解情况）。

二、课程的教学内容、重点和难点（按章节填写）

第一章 绪论

1、掌握各种基本术语的含义、区别与联系。

2、掌握基本的数据结构类型和它们的主要特点，并能举例。

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

第二章 线性表

1、掌握线性表的逻辑结构特性。

2、熟练掌握线性表的两种不同存储结构（顺序存储结构和链式存储结构）的描述方法和各种基本操作的算法。

3、掌握单链表和循环链表。

第三章 栈和队列

1、了解栈和队列的结构特点及存储结构。

2、掌握栈和队列在两种存储结构下实现基本操作的算法。

3、熟练掌握栈的链式存储结构和循环队列。

第四章 数组和串

1、了解数组基本概念。

2、了解串及相关操作。

第五章 树

1、掌握树的定义、各个基本术语以及树的各种存储结构。

2、了解树、森林与二叉树的转换方法。

3、了解树和森林的遍历。

第六章 二叉树及应用

1、掌握二叉树的基本概念、性质、各种存储结构的特点及其基本操作的实现。

2、熟练掌握二叉树各种遍历算法及其应用。

3、掌握如何建立哈夫曼树，了解哈夫曼树在编码、判定问题中的应用。

第七章 图

1、了解图的基本术语。

2、掌握图的各种存储结构及使用原则

3、掌握图的深度优先搜索和广度优先搜索算法。

4、掌握图生成最小生成树的方法，知道求最短路径的方法。

5、拓扑排序的应用实例和排序过程中栈的变化

6、了解网络中的关键路径及其求解。

7、了解图的若干应用算法。

第八章 查找

1、了解查找的基本概念。

2、熟练掌握顺序查找、二分查找和分块查找的特点及算法。、

3、掌握二叉排序树的构造，查找及删除算法。

4、了解散列表的构造方法和处理冲突的基本方法。

5、掌握查找成功时平均查找长度的计算方法。

第九章 排序

1、了解排序的基本概念。

2、熟练掌握各种内部排序方法的算法。

3、熟悉各种内部排序方法的特点、性能，能根据不同的实际情况比较、分析、选用不同的内部排序方法。

4、了解外部排序的概念和特点。

三、学时分配