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

课程名称：算法与数据结构/Algorithms and Data Structure

课程代码：020106

学时：    学分：4　　 讲课学时：50     上机/实验学时：14     考核方式：考试

先修课程：高级语言程序设计

适用专业：计算机科学与技术

开课院系：电子电气工程学院计算机系

教材：蔡子经,施伯乐. 数据结构教程. 复旦大学出版社. 1994

主要参考书：

[1] 黄国瑜,叶乃菁. 数据结构（C语言版）. 清华大学出版社. 2001

[2] 严蔚敏,吴伟民. 数据结构（C语言版）. 清华大学出版社. 1997 

一、课程的性质和任务

数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。

通过本课程的学习，使学生理解如何合理组织数据、有效存储和处理数据，正确设计算法以及对算法的分析和评价。培养基本的、良好的程序设计技能和编制高效可靠的程序。

二、教学内容和基本要求

教学内容

第一章 线性表

1 线性表及其基本运算

2 顺序存贮的线性表

3 顺序存贮的栈和队列

4 链接存贮的线性表

5 链式栈和链式队列

6 线性表的其他存贮方式

7 线性表的查找

第二章 串

1 串的基本概念及存贮结构

2 串的运算

3 模式匹配

第三章 内部排序

1 插入排序

2 选择排序

3 冒泡排序

4 希尔排序

5 合并排序

6 快速排序

7 基数排序

第四章 数组

1 数组的顺序存储

第五章 树

1 树的基本概念

2 树的存贮结构

3 树的遍历

4 树的线性表示

5 二叉树

6 二叉树的遍历

第六章 树的查找和树的应用

1 查找树（二叉排序树）

2 满树、拟满树和丰满树

3 堆和堆排序

4 哈夫曼树

第七章 图

1 图的基本概念

2 图的存贮结构

3 图的遍历

基本要求

了解与熟悉：数据结构的概念和术语，线性表的定义，线性表的存储结构，栈和队列的概念，数组的存储结构，树和二叉树的定义，树和二叉树的存储结构，树和二叉树的性质，图的存储结构。

掌握：线性表的应用，栈和队列的应用，字符串的处理方法，数组的应用，树和二叉树的各种遍历方法及应用，图的遍历方法，各种数据的查找方法和各种内部排序的方法。

三、实验（上机、习题课或讨论课）内容和基本要求

实验内容

实验一、栈的应用

实验二、单向线性链表的基本操作

实验三、字符串与数组的应用

实验四、用递归方法实现快速排序

实验五、一般树的各种操作

实验六、查找树的操作

实验七、图的遍历

基本要求

1. 用C++/C完成程序设计并上机调试通过。

2. 按实验指导书要求完成实验。

3．提供实验报告与源程序清单。

四、教学时数分配

通过本课程的学习，使学生理解如何合理组织数据、有效存储和处理数据，正确设计算法以及对算法的分析和评价。培养基本的、良好的程序设计技能和编制高效可靠的程序。

六、说明

1．本课程与其它课程的联系与分工

高级语言程序设计是本课程的先修课程。本课程是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。

2．课程内容的重点、难点

课程内容的重点

线性表的应用，栈和队列的应用，字符串的处理方法，数组的应用，树和二叉树的各种遍历方法及应用，图的遍历方法，各种数据的查找方法和各种内部排序的方法。

课程内容的难点

线性表的栈和队列的应用，树和二叉树的各种遍历方法，图的遍历方法，各种数据的查找方法和各种内部排序的方法。

3．有关课程考核问题

期中书面考试，期末书面考试。

4．其它需要说明的问题