《数据结构与算法》教学大纲(信息与计算科学专业、数学与应用数学)

( Data Structure and Algorithm )

一、基本信息

课程编号：L1133126 

课程类别：专业教育必修课

适用层次：本科

适用专业：数学与应用数学、信息与计算科学专业

开课学期：第四学期

总 学 分：4学分

总 学 时：学时（理论课48学时，实验课16学时）

考核方式：考试

二、课程教育目标

“数据结构与算法”是针对处理大量非数值问题而形成的一门学科，内涵丰富，应用范围广。它既有完整的学科体系与学科深度，又有较强的实践性。通过该课程的学习，应使学生理解和掌握各种数据结构（物理结构和逻辑结构）的概念以及有关的算法，熟悉并了解各种常用数据结构的基本应用，并能对算法做出时间及空间复杂度的分析，从算法和数据结构的相互依存关系中把握算法设计及分析的艺术与技能。通过上机实习和课程设计的训练，使学生能够编制、调试具有一定难度的应用程序，培养良好的软件工程习惯。

三、教学内容与要求

Ⅰ. 理论课教学内容

（一）绪论

掌握数据结构的概念、名词与术语、抽象数据类型ADT、算法的基本概念、算法分析方法。

本部分的重点是数据类型的基本概念与术语、抽象数据结构ADT、算法及算法分析。

本部分的难点是抽象数据结构ADT、算法分析基本技术。

（二）线性表

掌握线性表的定义及ADT、线性表的顺序表示及算法、线性表的链式表示及算法和顺序表和链表的比较及应用。

本部分的重点是线性表的ADT、顺序表及线性表的插入、删除、查找操作，各自的优缺点。

本部分的难点是顺序表及线性表的插入、删除和查找操作。

（三）栈和队列

1.掌握栈的定义及ADT、栈的存储表示及算法、队列的定义及ADT、队列的存储表示及算法。

2.理解栈的应用、队列的应用。

本部分的重点是栈和队列的ADT、基本操作和应用。

本部分的难点是栈的进栈、出栈操作，队列的进队、出队操作。

（四）串

理解串的定义及ADT、理解串的存储表示及算法、理解串的应用示例。

本部分的重点是串的ADT、串的基本操作。

本部分的难点是串的基本操作。

（五）树和二叉树

1.掌握树的定义和术语、ADT、二叉树的性质及存储表示、树的遍历。

2.理解二叉树的线索化技术、树的应用。

本部分的重点是二叉树的ADT、二叉树的性质、二叉链表、二叉树的先序、中序、后序遍历、二叉树的线索化、赫夫曼树的构造、赫夫曼编码。

本部分的难点是二叉树的先序、中序和后序遍历、赫夫曼编码。

（六）图

1.掌握图的定义和术语、ADT、图的存储结构、图的遍历。

2.了解图最小生成树、AOV网及拓扑排序、AOE网及关键路径、最短路问题。

本部分的重点是图的ADT、图的邻接矩阵和邻接表、图的深度优先搜索和广度优先搜索技术、最小生成树、拓扑排序、关键路径、最短路问题。

本部分的难点是图的邻接表、图的深度优先搜索和广度优先搜索、图的各种应用（最小生成树、拓扑排序、关键路径、最短路问题等等）。

（七）查找

掌握静态查找；理解哈希查找。

本部分的重点是查找表的ADT、顺序查找、折半查找和分块查找、哈希查找。

本部分的难点是顺序查找、折半查找及分块查找的算法、复杂度、比较，哈希函数的构造方法、处理冲突的方法、哈希查找算法、复杂度

（八）排序

1.掌握排序的概念、掌握插入排序、掌握交换排序、掌握选择排序、掌握归并排序。

2.掌握各种内部排序方法的比较

本部分的重点是各种内部排序方法的算法实现、算法分析。

本部分的难点是各种内部排序方法的算法实现、复杂度分析。

Ⅱ.实验课教学内容

（一）掌握表、链表的基本操作。

（二）掌握栈和队列列的基本操作。

（三）掌握二叉树的先序、中序、后序遍历。

（四）理解赫夫曼树及赫夫曼编码。

（五）掌握图的存储实现、广度优先遍历及深度优先遍历算法。

（六）理解图的应用。

（七）掌握静态查找算法。

（八）掌握各种内部排序方法。

四、各个章节学时分配

计算机程序设计基础、高级语言程序设计、离散数学

六、成绩评定

考  核 方 式：考试

成绩结构比例：期末成绩  70%

实践成绩  20%

平时成绩  10%