本站原创理科计算机主干基础课
《算法与数据结构》教学大纲
1999年7月20日
课程目的和要求:
《算法与数据结构》是理科非计算机专业的一门重要的计算机必修课,是一门理论和实际紧密结合的课程.本课的主要目的是使学生较全面地理解算法和数据结构的概念,掌握各种数据结构与算法的实现方式,比较不同数据结构和算法的特点.通过学习,使学生能够提高用计算机解决实际问题的能力.
三、先修课
本课程要求学生已学过"计算概论"课程,掌握了程序设计语言C的基本知识,并且有了一些使用C语言进行程序设计的实际经验.
知识单元和学时安排
1绪论(3学时)
算法的概念,算法的分析
数据结构的概念,数据结构的分类
本课程要讨论的基本问题
2线性表(6学时)
线性表结构,
线性表的顺序存储实现(顺序表),
线性表的链接实现(链接表),
线性表的应用
3字符串*(4学时)
字符串,
字符串的基本操作,
模式匹配问题,
字符串的应用
4堆栈与队列(5学时)
堆栈的概念,堆栈的实现,堆栈的应用,
队列的概念,队列的实现,队列的应用
5.树与二叉树(6学时)
树结构的概念,树的逻辑结构
二叉树的概念,完全二叉树与满二叉树
树,树林和二叉树的相互转换
树和二叉树的实现
树和二叉树的各种遍历算法
Huffman树的概念及应用
6检索与字典(8学时)
检索问题与字典
静态字典与动态字典
顺序检索,二分检索
分块检索*,
最佳二叉排序树*
散列表,散列函数的基本概念,散列函数的选择,碰撞的处理方法,
基于属性的检索方法*,倒排表与多重表*.
平衡二叉排序树*,B树与B+树*
7排序(4学时)
排序的基本概念
选择排序,插入排序,冒泡排序,快速排序
Shell排序*,堆排序*,归并排序*,基数排序*
各种排序算法的复杂性分析
8图结构(6学时)
图的基本概念及有关术语
图的存储表示法
图遍历,
最小生成树
最短路径
拓扑排序*
关键路径*
9算法分析与设计*(2-3学时)
10稀疏矩阵和广义表*(2-3学时)
稀疏矩阵的存储
广义表的基本概念
五、上机实践
1.在课程的前12周,学生应当完成一批程序设计作业,主要内容为一些典型数据结构的实现和应用.
2.课程最后6周时间,每个学生必须独立完成一个较大的程序实习,写出相应的实习报告.(报告内容应当包括:对问题的分析,主要设计思想,实现方法,采用的数据结构,算法及其分析,调试报告等.)
六、主要参考教材
《算法与数据结构–C语言描述》,张乃孝等,北京大学教材科,2000.8
《数据结构》,许卓群张乃孝杨冬青唐世渭,高等教育出版社1987
《数据结构基础》,张乃孝等,北京大学出版社1991
《数据结构—C++与面向对象程序设计》,张乃孝裘宗燕
高教出版社1998
《数据结构》(C语言版),严蔚敏吴伟民,清华大学出版社1996
1
2