数据结构教学大纲44-20.doc

数据结构课程教学大纲

课程名称 数据结构 (Data structure)
课程编码
学时/学分 64/3.5
适用专业（层次） 适用工学学科、管理学学科的本专科教学
课程简介
《数据结构》是计算机程序设计的重要理论技术基础，是计算机学科的核心课程，是一门专业基础课。数据结构课程主要包括：（1）数据结构的基本概念；（2）线性表﹑栈﹑队列﹑字符串﹑数组﹑广义表﹑树﹑二叉树﹑图﹑查找表等基本数据结构的概念、操作及应用；（3）查找、排序的实现方法等重要内容。在学习数据结构课程之前，必须具备高等数学、离散数学、计算机基本操作技术和一门设计语言（C或C++）等知识，后续课程为相关专业课程。数据结构课程主要是为了培养学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。通过学习课程的过程，也是对学生进行复杂程序设计的训练过程，培养了数据抽象能力。
教学重点和难点
《数据结构》的教学重点和难点有：数据的存储结构、运算及算法的分析。
课程内容
教学安排和学时分配表
章
次
教学内容
总
学
时
数
讲
授
学
时
实
验
学
时
设
计
学
时
作
业
学
时
讨
论
学
时
实
习
学
时
教
学
条
件
教
学
要
求
1
绪论
2
2

1.1
什么是数据结构

C
1.2
基本概念和术语

C
1.3
抽象数据类型的表示与实现

D
1.4
算法和算法分析

C
1.4.1
算法

C
1.4.2
算法设计的要求

C
1.4.3
算法效率的度量

C
1.4.4
算法的存储空间需求

C
2
线性表
8
4
4

2.1
线性表的类型定义
1
1

C
2.2
线性表的顺序表示和实现
3
1
2

A
2.3
线性表的链式表示和实现
3
1
2

A
2.3.1
线性链表

A
2.3.2
循环链表

A
2.3.3
双向链表

A
2.4
一元多项式的表示及相加
1
1

C
3
栈和队列
8
4
4

章
次
教学内容
总
学
时
数
讲
授
学
时
实
验
学
时
设
计
学
时
作
业
学
时
讨
论
学
时
实
习
学
时
教
学
条
件
教
学
要
求
3.1
栈
3
1
2

A
3.1.1
抽象数据类型栈的定义

A
3.1.2
栈的表示和实现
1
1

A
3.2
栈的应用举例
1
1

B
3.2.1
数制转换

B
3.2.2
括号匹配的检验

B
3.3
栈与递归的实现

C
3.4
队列
3
1
2

A
3.4.1
抽象数据类型队列的定义

A
3.4.2
链队列—队列的链式表示和实现

A
3.4.3
循环队列—队列的顺序表示和实现

A
3.5
离散事件模拟

C
4
串
2
2

4.1
串类型的定义
1
1

C
4.2
串的表示和实现
1
1

A
4.2.1
定长顺序存储表示

A
4.2.2
堆分配存储表示

C
4.2.3
串的块链存储表示

C
4.3
串的模式匹配算法

B
4.4
串操作应用举例

C
4.4.1
文本编辑

C
5
数组和广义表
2
2

5.1
数组的定义

C
5.2
数组的顺序表示和实现

A
5.3
矩阵的压缩存储

B
5.3.1
特殊矩阵

B
5.3.2
稀疏矩阵

B
5.4
广义表的定义
1
1

C
5.5
广义表的存储结构
1
1

A
5.6
m元多项式的表示

B
5.7
广义表的递归算法

C
6
树和二叉树
10
8
2

6.1
树的定义和基本术语
1
1

C
6.2
二叉树
1
1

A
6.2.1
二叉树的定义

章
次
教学内容
总
学
时
数
讲
授
学
时
实
验
学
时
设
计
学
时
作
业
学
时
讨
论
学
时
实
习
学
时
教
学
条
件
教
学
要
求
6.2.2
二叉树的性质

A
6.2.3
二叉树的存储结构

A
6.3
遍历二叉树和线索二叉树
1
1
2

A
6.3.1
遍历二叉树

A
6.3.2
线索二叉树

A
6.4
树和森林
1
2

B
6.4.1
树的存储结构

B
6.4.2
森林与二叉树的转换

B
6.4.3
树和森林的遍历

B
6.5
树与等价问题

C
6.6
赫夫曼树及其应用
2
1

A
6.6.1
最优二叉树

A
6.6.2
赫夫曼编码

B
6.7
回溯法与树的遍历

1

C
6.8
树的计数

1

C
7
图
8
8

7.1
图的定义和术语
1
1

C
7.2
图的存储结构
1
1

A
7.2.1
数组表示法

A
7.2.2
邻接表

A
7.2.3
十字链表

A
7.2.4
邻接多重表

A
7.3
图的遍历
1
1

A
7.3.1
深度优先搜索

A
7.3.2
广度优先搜索

A
7.4
图的连通性问题
1
2

B
7.4.1
无向图的连通分量和生成树

B
7.4.2
有向图的强连通分量

B
7.4.3
最小生成树

B
7.5
有向无环图及其应用
1
2

B
7.5.1
拓扑排序

B
7.5.2
关键路径

B
7.6
最短路径
1
1

C
7.6.1
从某个源点到其余各顶点的最短路径

C
7.6.2
每一对顶点之间的最短路径

C
章
次
教学内容
总
学
时
数
讲
授
学
时
实
验
学
时
设
计
学
时
作
业
学
时
讨
论
学
时
实
习
学
时
教
学
条
件
教
学
要
求
8
查找
10
6
4

8.1
静态查找表
4
2
2

C
8.1.1
顺序表的查找

B
8.1.2
有序表的查找

B
8.1.3
静态数表的查找

D
8.1.4
索引顺序表的查找

B
8.2
动态查找表
4
2
2

B
8.2.1
二叉排序树和平衡二叉树

B
8.2.2
B-和B+树

B
8.2.3
键树

D
8.3
哈希表
1
2

B
8.3.1
什么是哈希表

B
8.3.2
哈希函数的构造方法

B
8.3.3
处理冲突的方法

B
8.3.4
哈希表的查找及其分析

B
9
内部排序
8
6
2

9.1
概述
0.5
0.5

C
9.2
插入排序
1
1

A
9.2.1
直接插入排序

A
9.2.2
其他插入排序

A
9.2.3
希尔排序

A
9.3
交换排序
1
1

A
9.4
选择排序
1.5
1.5

A
9.4.1
简单选择排序

A
9.4.2
树形选择排序

A
9.4.3
堆排序

A
9.5
归并排序
0.5
0.5

B
9.6
基数排序
0.5
0.5

B
9.6.1
多关键字的排序

B
9.6.2
链式基数的排序

B
9.7
各种内部排序方法的比较讨论
3
1
2

A
教学要求：重点（A）、掌握（B）、理解（C）、了解（D）
考核方式及成绩评定
考核方式：闭卷、机试。
成绩评定：考核成绩70%、平时考核30%。平时考核由平时考勤(10%）、实习成绩(20%）构成。
教材及参考书目
教 材: 《数据结构》（C语言版） 严蔚敏 吴伟民编著 清华大学出版社 2003年
参考书目：
1、《数据结构》 刘振鹏 张晓莉 郝杰编著 中国铁道出版社 2003年
2、《数据结构》 杨正宏编著 中国铁道出版社 2003年
3、《数据结构简明教程》 徐孝凯编著 清华大学出版社 2002年
执行课程教学大纲的几点说明
1、在教学过程中，应重点讲授基本概念、物理结构、运算及实现的算法。
2、理论部分实验部分设置了综合课程设计实验，安排时间为4学时。