[数据结构与算法]

本科课程教学大纲（理工医类/电气学院）

课程负责人: 主 审:

一、课程描述及课程目标

（一）课程描述

数据结构是一门专业基础课，是学习其他软件开发与设计等方面课程的基础。主要内容包括:线性表、栈和队列、串、数组和广义表、树、图、查找算法和排序算法。数据结构研究数据的组织方式、存储结构（主要包括顺序存储结构与链表存储结构）及其相应的基本算法，内容丰富、学习量大，各部分内容中的方法和技术多，旨在让学生掌握计算机软件系统所必需的数据结构和算法的基本理论和基本方法。要求学生掌握贯穿全课程的各种数据的数据类型、存储结构与基本算法，掌握算法设计的动态性和抽象性。要求学生学会分析计算机处理的数据对象的特征，以便在实际应用中选择或者设计适当的数据类型、存储结构和相应的算法，初步掌握各种类存储结构与基本算法的时间与空间性能分析方法，并培养复杂程序设计的能力。

（二）课程目标

本课程为计算机类专业的专业基础课程，要求学生能够应用数据结构与算法的基本知识及技能解决实际问题，通过本课程的学习，学生应达到下列学习目标:

1.掌握数据结构基本知识及算法设计的技能，核心能力1。

2.具备选择合理数据结构、开发平台进行程序设计的能力，核心能力2。

3.具备计算机应用程序的设计能力，核心能力3。

4.了解本课程内容、方法在行业企业中的实际应用，能够将实验结果，通过文字、图、表的形式撰写实验报告，从而能够完整表达对实验部分的内容的理解与掌握，并学会持续应用、创新，核心能力6。

5.在教师的指导下，通过实验项目训练遵守职业规范和道德，训练严谨的专业学习及工作习惯，核心能力7。

二、课程内容

（一）第1章 绪论

主要知识点:

1.1 数据结构的基本概念；

1.2 算法的五大特性；

1.3 计算语句频度和估算算法时间复杂度和空间复杂度的方法。

教学要求:了解数据结构课程的意义、数据结构与算法在计算机科学中的作用。理解数据结构相关的基本概念，以及算法设计的基本概念。掌握算法的时间和空间复杂度分析的基本方法。

重点:数据结构的基本概念，算法的描述方法，算法的时间和空间复杂度分析。

难点:算法的描述方法，算法的时间和空间复杂度分析。

采用的教学方法:讲解，演示，讨论，习题

理论学时:3学时

习题学时:1学时

（二）第2章 线性表

主要知识点:

2.1 线性表的逻辑结构特点；

2.2 顺序表的存储结构与基本算法；

2.3 单链表、双链表的存储结构与基本算法；

2.4 用单链表表示一元多项式；

2.5 顺序表与链表的计算效率分析。

教学要求:理解线性表的逻辑结构特点。掌握顺序表的存储结构与基本算法，掌握单链表、双链表的存储结构与基本算法。掌握顺序表与链表的计算效率分析方法，学会用单链表表示一元多项式并进行两个多项式的加法计算。

重点:线性表的逻辑结构特点，顺序表的存储结构与基本算法，单链表、双链表的存储结构与基本算法，顺序表与链表的计算效率分析方法，用单链表表示一元多项式并进行两个多项式的加法计算。

难点:顺序表的存储结构与基本算法，链表的存储结构与基本算法，顺序表与链表的计算效率分析方法，用单链表表示一元多项式并进行两个多项式的加法计算。

教学方法:讲解，演示，讨论，习题，专项实验

理论学时:6学时

实验学时:2学时

习题学时:2学时

（三）第3章 栈和队列

主要知识点:

3.1 栈和队列的基本概念；

3.2 栈的数据操作方式与特点（只能在栈顶入栈和出栈）；

3.3 栈的顺序存储方式（顺序栈）与链式存储方式（链栈）；

3.4 队列的数据操作方式（队首出队和队尾入队）；

3.5 队列的顺序存储方式（顺序队）与链式存储方式（链队）；

3.6 循环队列的数据操作与算法（循环顺序队）；

3.7 递归算法过程与栈的内在关系。

教学要求:掌握栈和队列的基本概念。理解栈的数据操作方式与特点（只能在栈顶入栈和出栈），理解栈的顺序存储方式（顺序栈）与链式存储方式（链栈）。理解队列的数据操作方式（队首出队和队尾入队），理解队列的顺序存储方式（顺序队）与链式存储方式（链队），掌握循环队列（循环顺序队）的数据操作方式与基本算法。理解递归算法过程与栈的内在关系。

重点:栈和队列的基本概念，栈的数据操作方式与特点，栈的顺序存储方式与链式存储方式，队列的数据操作方式，队列的顺序存储方式与链式存储方式，循环顺序队的数据操作方式与基本算法。

难点:栈的顺序存储方式与链式存储方式，队列的顺序存储方式与链式存储方式，循环顺序队的数据操作方式与基本算法。

教学方法:讲解，演示，讨论，习题，专项实验

理论学时:5学时

实验学时:4学时

习题学时:3学时

（四）第4章 串、数组和广义表

主要知识点:

4.1 串的存储结构与基本算法；

4.2 串的顺序存储方式；

4.3 KMP算法，NEXT函数和改进NEXT函数的定义及其算法；

4.4 数组在以行为主的存储结构中的地址计算方法；

4.5 特殊矩阵压缩存储时的下标计算方式；

4.6 稀疏矩阵的两种基本存储方式（三元组表顺序存储方式与十字链表的链式存储方式）；

4.7 广义表的表示方式及其存储结构的方式；

4.8 线性结构相关知识点总结、习题训练。

教学要求:理解串的逻辑结构，存储结构与基本算法。掌握串的数据操作方式(重点掌握BF和KMP算法)。了解串的应用案例。掌握数组元素的地址计算方式，以及特殊矩阵压缩存储时的下标计算方式。理解稀疏矩阵数据元素的两种基本存储方式（三元组表顺序存储方式与十字链表的链式存储方式）。理解广义表的表示方式及其存储结构的方式，线性结构知识点总结、巩固。

重点:串的存储结构与基本算法，BF和KMP算法，数组元素的地址计算方式，特殊矩阵压缩存储时的下标计算方式，稀疏矩阵数据元素的两种存储方式（三元组表顺序存储方式与十字链表的链式存储方式），广义表的表示方式及其存储结构的方式。线性结构知识点理解与掌握。

难点:BF和KMP算法，稀疏矩阵数据元素的两种存储方式（三元组表顺序存储方式与十字链表的链式存储方式），广义表的表示方式及其存储结构的方式。线性结构存储方式与算法实现差异和分析。

教学方法:讲解，演示，讨论，习题，专项实验

理论学时:4学时

实验学时:2学时

习题学时:4学时

（五）第5章 树和二叉树

主要知识点:

5.1 树的定义和基本术语（结点，度，叶子，双亲，深度等）；

5.2 二叉树的定义、性质与存储结构；

5.3 按先序、中序、后序遍历二叉树；

5.4 二叉树的线索化（先序，中序，后序）；

5.5 树的存储结构以及森林与二叉树的转换；

5.6 哈夫曼编码与最优二叉树和前缀编码。

教学要求:理解树的定义和基本术语。理解二叉树的定义、性质与存储结构。掌握森林与二叉树的转换方式。掌握二叉树的三种遍历方式和线索二叉树。掌握哈夫曼树、哈夫曼编码的存储结构与基本算法。

重点:树的定义和基本术语，二叉树的定义、性质与存储结构，森林与二叉树的转换方式，二叉树的三种遍历方式和线索二叉树，哈夫曼树、哈夫曼编码的存储结构与基本算法。

难点:二叉树的三种遍历方式和线索二叉树，森林与二叉树的转换方式，哈夫曼树与哈夫曼编码。

教学方法:讲解，演示，讨论，习题，专项实验

理论学时:8学时

实验学时:4学时

习题学时:2学时

（六）第6章 图

主要知识点:

6.1 图的两种基本存储结构（邻接矩阵与邻接表）；

6.2 图的存储结构及其相应的基本算法；

6.3 图的广度优先搜索与深度优先搜索；

6.4 图的生成树、最小生成树、最短路径、拓扑排序、关键路径等基本概念和算法。

6.5 求最小生成树时采用的存储结构与基本算法，Kruskal算法与Prim算法。

教学要求:理解图的基本概念与基本性质。掌握图的两种基本的存储结构方式（邻接矩阵与邻接表）。掌握图的深度优先遍历方式和广度优先遍历方式。理解最小生成树、最短路径、拓扑排序、关键路径等基本概念与基本算法。

重点:图的两种基本存储结构方式（邻接矩阵与邻接表），图的深度优先遍历方式和广度优先遍历方式，最小生成树、最短路径、拓扑排序、关键路径等基本概念与基本算法，求最小生成树时采用的存储结构与基本算法（Kruskal算法与Prim算法）。

难点:最小生成树、最短路径、拓扑排序、关键路径等基本概念与基本算法，求最小生成树时采用的存储结构与基本算法（Kruskal算法与Prim算法）。

教学方法:讲解，演示，讨论，习题，专项实验

理论学时:6学时

实验学时:4学时

习题学时:2学时

（七）第7章 查找

主要知识点:

7.1 顺序查找、折半查找的存储结构与算法；

7.2 折半查找的判定树;

7.3 二叉排序树；

7.4 平衡二叉树；

7.5 B-树，B+树；

7.6 哈希表的构造原理与构造方法；

教学要求:理解顺序查找、折半查找的存储结构与算法特点。掌握折半查找判定树的分析方法。掌握二叉排序树的分析方法。理解平衡二叉树，B-树和B+树。理解哈希表的构造原理与构造方法。

重点:顺序查找、折半查找的存储结构与算法，折半查找的判定树，二叉排序树，平衡二叉树，哈希表。

难点:折半查找判定树的分析，二叉排序树的分析，哈希表的构造原理和构造方法。

教学方法:讲解，演示，讨论，习题，实验考查

理论学时:3学时

实验学时:2学时

习题学时:1学时

（八）第8章 排序

主要知识点:

8.1 各种排序算法的特点；

8.2 各种排序算法的过程；

8.3 各种排序算法的时间复杂度分析与空间复杂度分析；

8.4 外部排序的过程。

教学要求:理解各种排序算法的存储结构特点，算法的优点与缺点，以及算法的功能效益。理解各种排序算法的时间复杂度分析与空间复杂度分析。

重点:各种排序方法的存储结构与算法，时间复杂度分析与空间复杂度分析。

难点:各种排序方法的存储结构与算法，时间复杂度分析与空间复杂度分析。

教学方法:讲解，演示，讨论，习题

理论学时:3学时

习题学时:1学时

三、课程的预期学习成果

在本门课程结束时，学生应该能够:

1.分析研究计算机处理的数据结构的特性；

2.设计数据对象的数据类型、存储结构及相应的基本算法；

3.对存储结构与算法进行时间复杂度分析和空间复杂度分析；

4.提高数据抽象能力和程序设计能力；

5.提高分析和解决问题的效率。

四、课程要求

（一）出勤

学生应积极参与课堂教学并完成相关的作业、实验内容。

（二）阅读资料

学生应认真进行课前预习，阅读教材和指定参考书及重要的参考文献。

（三）课堂演示

结合理论课教学内容，教师课堂演示、同学讨论。

（四）课程实验

第10至18周安排学生实验课，实验课程由学生完成专项实验内容、实验报告等。必要时可安排学生进行效果展示与讨论。

（五）小考、期中考与期末考

课程中随机问答。适时随堂小考，并集中安排闭卷形式的期中考试。期末考试形式为闭卷笔试。

（六）学术诚信

按中山大学南方学院相关规定执行。

（七）剽窃的定义以及相应的惩罚

剽窃是严重违反学校规章制度的行为。一经发现，将上报相关部门，并受到包括开除学籍在内的严厉处罚。

五、课程资料

（一）教科书-必读

严蔚敏，李冬梅，吴伟民．数据结构（C语言版）（第2版）．人民邮电出版社． 2015年2月.

（二）教科书-强烈推荐

1.严蔚敏主编，数据结构（C语言版），清华大学出版社．2012年5月.

2.殷人昆主编，数据结构（用面向对象方法与C++描述），清华大学出版社．2007年6月.

3.李春葆主编，数据结构教程（第4版）上机实验指导，清华大学出版社.2013年1月.

（三）文章-必读

近年《计算机学报》、《软件学报》等国内、国际期刊杂志刊登的文章。

（四）文章-强烈推荐

与算法设计相关的各类文章。

（五）其他参考资料

1.Data Structures and Program Design in C++, Robert Kruse, Alex,高等教育出版社，2000.

2.A Practical Introduction to Data Structures and Algorithm Analysis, Clifford A. Shaffer, 电子工业出版社，2002

六、教学活动以及对于预期学习成果的评估

（一）教学活动

1、个人预习

2、课堂讲授

3、课堂问答、演示

4、习题讲解

5、小型实验项目

6、期中考试

7、期末考试

（二）对预期学习成果的考察

七、评估的程序和方法

（一）评分体系

1、平时: 50%

（1）出勤率: 10%

（2）课堂参与: 根据情况加分

（3）课后作业、课堂实验、期中考试: 40%

2、期末考试: 50%

（二）考核内容及要求

1、笔试部分

（1）理解数据结构的基本知识、逻辑结构与存储结构（核心能力1、2、3）；

（2）能够设计合适的算法并选择较好的存储结构设计程序（核心能力1、2）。

2、实验考查部分

（1）能够根据实际问题，选用合适的程序开发工具和方法（核心能力2）；

（2）能够根据课程要求，通过文字、图、表的形式撰写实验报告，并进行分析与总结（核心能力6）；

（3）能够按照实验项目要求，按时完成，并培养良好的职业习惯（核心能力7）。

八、教学进度与学时分配表

注:此表一式三份，于开学两周内填好，一份送教务与科研部，一份开课单位留存，一份自留。