《数据结构》课程教学大纲(1).docx

《数据结构》课程教学大纲
一、课程基本信息课程代码：05110126
课程名称：数据结构课程英文名称：Data Structure
课程所属单位：计算机与信息工程系课程面向专业：计算机科学与技术本科
课程类型：学科基础课先修课程：离散数学、C语言（或PASCAL语言）程序设计
学分：4总学时：56 （其中理论学时：56实验学时：0）
二、课程性质与目的
《数据结构》是计算机科学与技术专业的主干课程、专业基础课程之一，该课程是后续课程如数据 库系统概论、操作系统、编译原理等课程的先修课程，在整个教学体系中占据非常重要的地位。
该课程主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方 法、存储数据结构的方法以及在各种结构上执行操作的算法。通过教学要求学生掌握各种数据结构的特 点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编 写质量高、风格好的应用程序的能力，为软件开发和程序设计提供必要的技能训练，并为后续专业课程 的学习打下良好的理论基础和实践基础。
三、课程教学内容与要求（一）绪论
1、基本要求：
（1）了解非数值问题的数学模型不是数学方程，而是表、树和图之类的数据结构。
（2）理解数据、数据元素、数据对象、数据结构和数据类型等的定义。
（3）掌握数据的逻辑结构和存储结构及其种类以及算法的重要特征等。
（4）掌握算法的时间复杂度和空间复杂度的计算方法。
2、本章重难点内容：数据结构基本概念和术语以及算法的性能分析与度量方法（二）线性表
1、基本要求：
<1）了解线性表的定义和线性结构的特点。
（2）理解线性表的顺序存储和链式存储，理解数组与单链表表示表的优缺点。
（3）掌握线性顺序表中数据元素的存储位置的计算，顺序表、单向链表、循环链表和双向链表的插入、 删除等有关操作。
（4）会用单链表编写插入、删除等有关算法。
2、本章重难点内容：线性表的顺序存储结构和链式存储结构，单链表、循环链表和双向链表的表示及 实现。
（三）栈和队列1、基本要求：
<1）了解校和队列的定义。
（2）理解线性表、栈和队列特点及区别，栈对实现递归过程的作用。
<3）掌握顺序枝、链栈的入枝和出枝操作，顺序队列、链队列的入队和出队操作，循环队列的队空和 队满的判断。
（4）会编写入栈和山栈，入队和出队的有关算法。
2、本章重难点内容：栈的定义、表示和实现：队列的定义、表示和实现。
（四）串1、基本要求：
（1）了解串的有关定义。
（2）理解串的逻辑结构和存储结构。
（3）掌握串的模式匹配传统方法和KMP算法。
（4）会推出模式串的next函数值。
2、本章重难点内容：串的逻辑结构、静态存储结构、动态存储结构和串的基本操作。
（五）数组和广义表1、基本要求：
（1）了解数组、特殊矩阵和稀疏矩阵的定义，以及广义表的概念和链表表示。
（2）理解矩阵的压缩存储的概念。
（3）掌握矩阵的压缩存储的有关计算方法。
2、本章重难点内容：数组的定义和运算、数组的顺序存储结构，特殊矩阵、稀疏矩阵的定义、矩阵的 压缩存储，广义表的定义、广义表的存储结构。
（六）树和二叉树1、基本要求：
（1）了解树的定义和二叉树的定义（2）理解二叉树的性质、二叉树的存储结构。
（3）掌握遍历二叉树的方法、线索二叉树的构造，森林与二叉树的转换，最优二叉树和
哈夫曼编码（4）会利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题，会编写与二叉树有关的算法。 2、本章重难点内容：树的结构定义和基本操作；二叉树的定义、性质及存储结构；遍历二叉树和线索 二叉树；树的存储结构，森林与二叉树的转换，树的遍历；最优二叉树和哈夫曼编码。
（七）图1、基本要求：
（1）了解图的定义和术语，以及生成树和最小生成树的概念。
（2）理解邻接矩阵中元素的含义和邻接表中结点的含义。
<3）掌握深度优先搜索和广度优先搜索算法。
（4）会用Prim算法和Kruskal算法构造最小生成树，会找出图中顶点的拓扑序列等。
2、本章重难点内容：图的定义、术语及存储结构；图的遍历：深度优先搜索和广度优先搜索；无向图 的连通分量和生成树、最小生成树，拓扑排序。
（A）查找1、基本要求：
（1）了解顺序查找、二分查找和分块查找的概念，了解二叉排序树和平衡二叉树、哈希查找等的概念。
（2）理解顺序查找、二分查找和分块查找算法，理解二叉排序树的性质。
（3）掌握哈希函数的构造方法和处理冲突的方法，掌握平衡二叉树的查找、插入和删除操作算法，掌 握相关查找方法的ASL。
（4）会用哈希函数、开放地址法或拉链法建立散列表。
2、本章重难点内容：静态查找表：顺序查找、二分查找和分块查找；动态查找表：二叉排序树和平衡 二叉树；哈希查找、哈希函数的构造方法和处理冲突的方法。
（九）内部排序1、基本要求：
（1）了解排序算法的稳定性问题。
<2）理解直接插入排序、希尔排序、快速排序、简单项选择择排序、堆排序、归并排序和基数排序的基本 思想。
（3）掌握直接插入排序、希尔排序、快速排序、简单项选择择排序、堆排序、归并排序的算法和时间分析。
（4）会用希尔排序、快速排序、堆排序、二路归并排序方法写出每趟排序的结果，会编写与直接插入 排序和简单项选择择排序有关的算法。
2、本章重难点内容：直接插入排序、希尔排序、快速排序、简单项选择择排序、堆排序、归并排序和基数 排序。各种内部排序方法的比拟。
四、学时分配学时分配表
序号
教学内容（按章填写）
学时
课堂讲授
实验课
习题课
讨论课
其它
1
绪论
2

2
线性表
6

3
栈和队列
6

4
串
4

5
数组和广义表
4

6
树和二叉树
10

7
图
8

8
查找
8

9
内部排序
8

小计
56

比例
100%

合计
56
五、教学环节与教学要求：
通过教学要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应 用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，为软件开发和程序 设计提供必要的技能训练，并为后续专业课程的学习打下良好的理论基础和实践基础。
六、课程考核方法：
本课程采用闭卷考试
1、案例作业：20%
2、课堂参与：10%
3、考试： 70%七、教材与主要参考书：
教材：
严蔚敏等，数据结构（C语言版），清华大学出版社主要参考书：
1、管纪文等，数据结构，高等教育出版社
2、朱望规，数据结构，西安交大出版社
3、 E.Horowitz and Sahni, Foudamentals of Data Structures, by Pitmen Publishing Limited.
4、 D.E.Knuth, The Art of Computer Programming, by Addison-Wesley Publishing Companyjnc.