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

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

课程
代码课程名称数据结构与算法DataStructure课
程
基
本
情
况1、学分：4.5学时：80（理论学时：64实验学时：16）
2、课程性质：学科专业基础课
3、适用专业：计算机科学与技术专业、计算机软件工程专业
4、适用对象：本科
5、先修课程：计算机语言(C)
6、教材与参考书目：
《数据结构(C语言版)》，严蔚敏吴伟民，清华大学出版社，1997
《数据结构(用面向对象方法与C++描述)》，殷人昆，清华大学出版社，1998
《C++数据结构与程序设计（美）RobertL.Kruse/AlexanderJ.Ryba著/钱丽萍译》，
清华大学出版社，2004
《算机算法设计与分析（第2版）》，王晓东，电子工业出版社，2004
7、考核方式：考试、闭卷平时成绩30~40％、期终考试60~70％
8、教学环境：课堂、多媒体，实验室课
程
教
学
目
的数据结构是计算机程序设计的重要理论基础。也是计算机专业教学中的核心专业基础课程。它所讨论的知识内容和提倡的技术方法，对进一步学习计算机领域的其他课程、从事软件工程的开发，都有着不可替代的作用。是从事计算机科学研究及应用的科技人员必须具备的重要基础知识。课
程
内
容
、
学
时
分
配
及
教
学
基
本
要
求1绪论（4学时）
1.1什么是数据结构（理解）
1.2基本概念和术语（掌握）
1.3抽象数据类型的表示与实现（了解）
1.4算法和算法分析
1.4.1算法（掌握）
1.4.2算法设计的要求（掌握）
1.4.3算法效率的度量（掌握）
1.4.4算法的存储空间需求（理解）

2线性表（6+4学时）
2.l线性表的类型定义（掌握）
2.2线性表的顺序表示和实现（掌握）
2.3线性表的链式表示和实现
2.3.1线性链表（掌握）
2.3.2循环链表（掌握）
2.3.3双向链表（掌握）课
程
内
容
、
学
时
分
配
及
教
学
基
本
要
求2.4一元多项式的表示及相加（理解）

3栈和队列（6+2学时）
3.1栈（掌握）
3.1.l抽象数据类型栈的定义
3.1.2栈的表示和实现
3.2栈的应用举例（了解）
3.2.1数制转换
3.2.2括号匹配的检验
3.2.3行编辑程序
3.2.4迷宫求解
3.2.5表达式求值
3.3栈与递归的实现（了解）
3.4队列
3.4.1抽象数据类型队列的定义（掌握）
3.4.2链队列--队列的链式表示和实现（掌握）
3.4.3循环队列--队列的顺序表示和实现（掌握）
3.5离散事件模拟（了解）

4串（4+2学时）
4.1串类型的定义（掌握）
4.2串的表示和实现
4.2.1定长顺序存储表示（掌握）
4.2.2堆分配存储表示（了解）
4.2.3串的块链存储表示（了解）
4.3串的模式匹配算法（理解）
4.3.l求子串位置的定位函数Index（S,T,pos）
4.3.2模式匹配的一种改进算法
4.4串操作应用举例（理解）
4.4.1文本编辑
4.4.2建立词索引表

5数组和广义表（4学时）
5.1数组的定义（掌握）
5.2数组的顺序表示和实现（掌握）
5.3矩阵的压缩存储（理解）
5.3.l特殊矩阵（理解）
5.3.2稀疏矩阵（理解）
5.4广义表的定义（掌握）
5.5广义表的存储结构（理解）
5.6m元多项式的表示（了解）
5.7广义表的递归算法（了解）
5.7.1求广义表的深度
5.7.2复制广义表课
程
内
容
、
学
时
分
配
及
教
学
基
本
要
求5.7.3建立广义表的存储结构

6树和二叉树（10+2学时）
6.1树的定义和基本术语（掌握）
6.2二叉树（掌握）
6.2.1二叉树的定义
6.2.2二叉树的性质
6.2.3二叉树的存储结构
6.3遍历二叉树和线索二叉树
6.3.1遍历二叉树（掌握）
6.3.2线索二叉树（理解）
6.4树和森林（理解）
6.4.1树的存储结构
6.4.2森林与二叉树的转换
6.4.3树和森林的遍历
6.5树与等价问题（理解）
6.6赫夫曼树及其应用（掌握）
6.6.1最优二叉树（赫夫曼树）
6.6.2赫夫曼编码
6.7回溯法与树的遍历（理解）
6.8树的计数（了解）

7图（10+2学时）
7.1图的定义和术语（掌握）
7.2图的存储结构（掌握）
7.2.1数组表示法（掌握）
7.2.2邻接表（掌握）
7.2.3十字链表（理解）
7.2.4邻接多重表（理解）
7.3图的遍历
7.3.l深度优先搜索（掌握）
7.3.2广度优先搜索（掌握）
7.4图的连通性问题
7.4.1无向图的连通分量和生成树（理解）
7.4.2有向图的强连通分量（理解）
7.4.3最小生成树（掌握）
7.4.4关节点和重连通分量（了解）
7.5有向无环图及其应用（了解）
7.5.1拓扑排序