《数据结构与算法》课程教学大纲(计
- 格式：doc
- 大小：67.00 KB
- 文档页数：6
《数据结构与算法》课程教学大纲
（Data Structures & Algorithms）
一、基本信息
课程编号：E1132107
课程类别：学科基础必修课
适用层次：本科
适用专业：计算机科学与技术、网络工程、软件工程
开课学期：3
总学分：4.5
总学时：72学时（理论课54学时，实验课18学时）
考核方式：考试
二、课程教育目标
《数据结构与算法》是计算机学科基础的一门核心课程，它对提高学生的程序设计和算法设计与分析能力具有十分重要的作用。通过本门课程的学习，使学生学会合理地组织数据、有效地表示数据和有效地处理数据，培养和训练学生能够根据实际问题的要求选择和设计合适的数据结构，编写质量高、风格好的应用程序，并具有初步的算法设计分析能力。
三、教学内容与要求
1.理论课教学内容
1） 绪论
主要包括：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型；算法、算法描述与算法分析。
基本要求：了解数据结构的重要性；了解算法分析的重要性；理解数据结构与算法的关系；掌握数据结构的基本概念和抽象数据类型。
2） 线性表
主要包括：线性表的（逻辑）定义与基本运算；线性表的顺序存储结构及基本运算的实现；线性表的链式存储结构（单链表、循环链表、双向链表）及其基本运算；一元多项式的表示及简单运算。
基本要求：掌握一般线性表的特点、存储表示、相应算法和实现方法及其典型应用。并初步掌握基本算法分析技术。
3） 栈和队列
主要包括：栈和队列的结构特性、基本操作及其在顺序存储结构和链式存储结构上基本操作的实现；栈和队列的应用、递归算法的设计。
基本要求：掌握栈和队列的特点、存储表示、相应算法和实现方法及其典型应用。
4） 字符串
主要内容：字符串的定义、基本运算、存储结构、匹配算法及其应用。
基本要求：掌握字符串的的特点、存储表示、相应算法和实现方法及其典型应用。
5） 数组和广义表
主要内容：数组的定义、运算、存储结构、特殊矩阵及稀疏矩阵的压缩存储。广义表的逻辑结构和存储结构以及广义表的遍历。
基本要求：掌握数组的特点、存储表示、相应算法和实现方法及其典型应用。了解广义表的特点及其使用。
6） 二叉树和树
主要内容：树的基本概念、存储结构；二叉树的定义、性质、存储结构；二叉树的遍历；线索二叉树；树、森林与二叉树的相互转换及遍历；哈夫曼树及其应用。
基本要求：掌握各线性表、二叉树、树、图等的特点、存储表示、相应算法和实现方法及其典型应用。
7） 图
主要内容：图的基本概念、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）；图的遍历、图的连通性问题；拓扑排序、关键路径；最短路径。
基本要求：掌握图的特点、存储表示、相应算法和实现方法及其典型应用。
8） 查找和排序
主要内容：查找表是集合类型的数据结构，其操作借助静态查找表、动态查找表、哈希表实现，包括顺序查找、二分法查找、分块查找、树表查找、Hash查找。排序分为内部排序和外部排序。内部排序介绍插入排序、快速排序（交换排序）、选择排序、归并排序、基数排序等排序的基本思想和算法分析。
基本要求：掌握查找和排序的基本方法。包括基于线性表、散列表等常见的检索技术及其时间和空间开销；包括简单排序、Shell排序、堆排序、快速排序、基数排序等常用的各种排序算法及其时间和空间开销。
9） 文件
主要内容：文件的基本概念与物理结构；顺序文件、随机文件、索引文件、倒排文件等。
基本要求：初步掌握文件组织方法。
本课程学习重点：数据的逻辑结构与存储结构；线性表的链式存储结构；栈和队的基本运算及典型应用；树的存储表示，二叉树的遍历；图的存储表示——邻接矩阵与邻接表；图的深度优先、广度优先搜索；基本的查找技术；各种排序技术及其比较；基本算法的分析方法；文件的索引技术。
本课程的难点：递归算法的设计；算法的分析和比较。
2.实验课教学内容
《数据结构与算法》是一门实践性较强的课程，学生必须完成一定数量的上机实验。通过上机实验，要求在数据结构的逻辑特性和存储表示，基本数据结构的选择和应用、算法设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法及上机操作等基本技能和编程风格方面受到比较系统的、严格的训练。
上机次数和实验内容可根据实验条件及教学情况由教师自定。上机实验课时为18学时。实验内容的选择要尽量结合基本内容的应用实例，要具有一定的典型性和方法的灵活性，但一次实验内容不宜太多、太难。
实验课教学内容及要求概述如下：
1）线性表及其应用
基本要求：掌握线性表的基本概念、线性表的顺序存储结构和链式存储结构；掌握不同存储结构下，线性表基本操作的实现；能够利用线性表的基本操作，完成相关的程序设计。
2）栈、队列及其应用
基本要求：掌握栈和队列的特性，理解栈和递归程序设计的关系。要求能够灵活运用两种结构来解决有关的应用问题，并受到递归程序设计的初步训练。
3）字符串及其应用
基本要求：结合应用实例，在掌握串的基本运算的基础上，进一步熟悉有关串的比较、插入、删除、复制、求逆等运算的实现技术。
4）树及其应用
基本要求：加深理解树的特点，掌握树的存储结构、二叉树的遍历技术。
5）图及其应用
基本要求：加深理解图的特点，掌握运用图的存储结构、图的深度优先搜索和广度优先搜索来解决有关应用问题。
6）查找与排序
基本要求：掌握查找与排序的基本方法，结合非数值应用问题，提高关于查找排序算法的运用、比较与分析能力。
四. 作业、练习的安排与要求
每章内容结束后根据讲授内容布置2~3个作业题。
五. 各个章节学时分配
主 要 内 容 各个教学环节学时分配
备 注
理论课 实验课 习题课 讨论课 小计
1 绪论 4
2 线性表 4 4
3 栈和队列 6 2
4 字符串 2 2
5 数组和广义表 4
6 二叉树和树 12 2
7 图 8 4
8 查找和排序 12 4 9 文件 2
合 计 54 18 72
六. 相关联的课程
1.预修课程
程序设计基础、离散数学（只需要集合论、图论）。
2.后续课程
数据库概论、操作系统、软件工程、编译原理、人工智能等课程。
七. 教材与教学参考书
1.建议教材：
[1] 数据结构(C++)版，王红梅、胡明、王涛编著，清华大学出版社，2005.7
[2] 自编教材
2.建议参考书目：
[1]许卓群，杨冬青，唐世渭，张铭. 数据结构与算法. 高等教育出版社，2004.7
[2] 严蔚敏, 陈文博. 数据结构及应用算法教程. 清华大学出版社, 2001.2
[3] 朱晋蜀. 数据结构(第一版). 成都: 电子科技大学出版社, 2000.1
[4] Clifford A. Shaffer著. 张铭，刘晓丹译. 数据结构与算法分析. 电子工业出版社，1998.8
[5] 殷人昆等. 数据结构（用面向对象方法与C++描述）. 清华大学出版社，1999.7
[6] Ford W., Topp W. DATA STRUCTURES with C++. 清华大学出版社（影印版），1997.3
八.成绩评定
本课程考核的方式为考试。
本课程的总成绩的组成及结构比例建议如下：平时成绩（出勤、作业）占20%+上机实验及报告占20%+期末考试成绩占60%。
编写人（签字）： 李锡祚 编写人职称： 审阅人（签字）： 审阅人职称：
审批人（签字）： 审批人职务：
本大纲启用日期：2005年8月22日
