《算法与数据结构》.doc

文档介绍：理科计算机主干基础课
《算法与数据结构》教学大纲
1999年7月20日
课程目的和要求:
《算法与数据结构》是理科非计算机专业的一门重要的计算机必修课,是一门理论和实际紧密结合的课程。本课的主要目的是使学生较全面地理解算法和数据结构的概念、掌握各种数据结构与算法的实现方式,比较不同数据结构和算法的特点。通过学习,使学生能够提高用计算机解决实际问题的能力。
三, 先修课
本课程要求学生已学过“计算概论”课程,掌握了程序设计语言C的基本知识,并且有了一些使用C语言进行程序设计的实际经验。
知识单元和学时安排
1 绪论(3学时)
算法的概念,算法的分析
数据结构的概念、数据结构的分类
本课程要讨论的基本问题
2 线性表(6学时)
线性表结构,
线性表的顺序存储实现(顺序表),
线性表的链接实现(链接表),
线性表的应用
3 字符串*(4学时)
字符串,
字符串的基本操作,
模式匹配问题,
字符串的应用
4 堆栈与队列(5学时)
堆栈的概念,堆栈的实现,堆栈的应用,
队列的概念,队列的实现,队列的应用
(6学时)
树结构的概念,树的逻辑结构
二叉树的概念,完全二叉树与满二叉树
树、树林和二叉树的相互转换
树和二叉树的实现
树和二叉树的各种遍历算法
Huffman树的概念及应用
6 检索与字典(8学时)
检索问题与字典
静态字典与动态字典
顺序检索,二分检索
分块检索*,
最佳二叉排序树*
散列表、散列函数的基本概念,散列函数的选择,碰撞的处理方法,
基于属性的检索方法*,倒排表与多重表*。
平衡二叉排序树*,B树与B+树*
7 排序(4学时)
排序的基本概念
选择排序,插入排序、冒泡排序、快速排序
Shell排序*、堆排序*、归并排序*、基数排序*
各种排序算法的复杂性分析
8 图结构(6学时)
图的基本概念及有关术语
图的存储表示法
图遍历、
最小生成树
最短路径
拓扑排序*
关键路径*
9 算法分析与设计*(2-3学