第一篇：《数据结构》课程教学大纲
《数据结构》课程教学大纲
Data Structure 执笔人：
编写日期：
一、课程基本信息
1.课程编号：
2.课程性质/类别： 必修课 / 专业主干课
3.学时/学分： 48 学时（另实验16学时）/ 4 学分
4.适用专业：计算机科学与技术、软件工程、网络工程、信息管理与信息系统等专业
二、课程教学目标及学生应达到的能力
数据结构课程是计算机相关专业的专业基础课、必修课程，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。通过本课程的学习，要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，培养学生分析问题、解决问题的能力，并为后续课程的学习打下良好的理论基础和实践基础。
三、课程教学内容与基本要求
（一）绪论（3 学时）1．主要内容：
（1）介绍什么是数据结构；
（2）基本概念和术语: 数据、数据元素、数据对象，以及数据结构的定义、逻辑结构、物理结构（理解）数据类型、抽象数据类型；
（3）抽象数据类型的表示与实现；
（4）算法和算法分析: 算法的概念、算法设计的要求以及算法效率的度量。2．基本要求
（1）了解学习数据结构的重要性；
（2）掌握数据结构的定义及相关概念和术语；（3）了解抽象数据类型的定义、表示与实现方法；（4）理解算法的概念、特点并掌握度量其效率的基本方法。3．自学内容：
类C语言的书写规范。
（二）线性表（6 学时）1．主要内容：
（1）线性表的抽象数据类型定义和相关概念：数据项、记录、文件等；（2）线性表顺序存储表示和基本操作的实现；（3）线性表的链式存储表示和基本操作的实现；
（4）稀疏多项式的抽象数据类型定义、表示和加法的实现。2．基本要求
（1）掌握线性表的定义和特点；
（2）熟练掌握线性表的顺序存储表示和插入、删除、查找等实现算法；
（3）熟练掌握单链表、循环链表、双向链表三种链表的表示，以及单链表的查找、插入、删除、创建等实现算法。
3．自学内容：
静态链表。
（三）栈和队列（5 学时）1．主要内容：
（1）栈和队列的结构特性和抽象数据类型定义；（2）栈和队列的顺序存储表示和实现；（3）栈和队列的链式存储表示和实现；（4）栈和队列在程序设计中的应用。2．基本要求
（1）掌握栈和队列两种抽象数据类型的特点；
（2）掌握栈的两种存储表示和实现，特别注意栈满栈空的条件；（3）掌握队列的两种存储表示和实现，特别注意队满队空的条件；（4）了解递归算法与栈的关系。3．自学内容：
链栈，离散事件模拟
（四）串（3 学时）1．主要内容：
（1）串的抽象数据类型定义；
（2）串的表示和实现: 定长顺序存储结构和堆分配存储结构；（3）串的各种基本操作的实现及其应用；（4）串的模式匹配操作。2．基本要求
（1）熟悉串的一些基本操作的定义，并能利用基本操作实现串的其它操作；（2）掌握串的定长顺序存储结构以及基本操作的实现；（3）掌握串的堆分配存储结构以及基本操作的实现；（4）掌握串的简单模式匹配算法，理解KMP算法。3．自学内容：
串操作的应用实例。
（五）数组和广义表（4 学时）1．主要内容：
（1）数组的抽象数据类型定义及其顺序表示和实现；（2）特殊矩阵和稀疏矩阵的压缩存储；（3）广义表的抽象数据类型定义和存储结构。2．基本要求
（1）了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；（2）掌握对特殊矩阵进行压缩存储时的下标变换公式；
（3）熟悉稀疏矩阵的三元组顺序表存储结构下的一般转置和快速转置算法；了解十字链表等存储结构；
（4）掌握广义表的结构特点、取表头表尾操作，及其存储表示方法。3．自学内容：
采用十字链表存储结构创建稀疏矩阵。
（六）树和二叉树（10 学时）1．主要内容：
（1）树的抽象数据类型定义和基本术语；
（2）二叉树的抽象数据类型定义、性质和存储结构；（3）二叉树的遍历；
（4）线索二叉树的定义、遍历及线索化二叉树；
（5）树的存储结构、树和森林的遍历以及与二叉树的转换；（6）Huffman树及其应用。2．基本要求
（1）掌握树型结构的特点和基本术语；
（2）熟练掌握二叉树的性质，了解相应的证明方法；
（3）了解二叉树的顺序存储结构和链式存储结构，熟练掌握二叉链表存储结构；（4）熟练掌握二叉树三种遍历的递归算法和中序遍历非递归算法，能灵活运用遍历算法实现二叉树的其他操作；
（5）熟练掌握二叉树的线索化过程，以及在中序线索二叉树上找结点的前驱与后继的方法；
（6）熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法；（7）了解Huffman树的特性，掌握建立Huffman树和Huffman编码的方法。3．自学内容：
先序、后序遍历二叉树非递归算法，层次遍历二叉树算法。
（七）图（9 学时）1．主要内容：（1）图的定义和术语；
（2）图的四种存储结构：数组表示法（邻接矩阵）、邻接表、十字链表和邻接多重表；（3）图的两种遍历策略：深度优先遍历和广度优先遍历；（4）图的连通性和最小生成树；
（5）有向无环图及其应用：拓扑排序和关键路径；（6）最短路径问题。2．基本要求
（1）熟悉图的定义和术语；
（2）了解图的存储结构，熟练掌握数组表示法（邻接矩阵）和邻接表存储表示；（3）熟练掌握图的深度优先遍历和广度优先遍历算法；（4）掌握无向连通带权图的最小生成树求解算法；
（5）了解有向无环图、AOV网、AOE网及其在实际中的应用，熟悉拓扑排序算法和关键路径算法；
（6）熟悉两种最短路径问题求解算法。3．自学内容：
树的先根遍历算法与图的深度优先遍历算法比较；
树的层次遍历算法与图的广度优先遍历算法比较。
（八）查找（4 学时）1．主要内容：
（1）查找的基本概念和相关术语；
（2）静态查找表：顺序查找、折半查找和索引顺序表查找；（3）动态查找表：二叉排序树的查找、插入和删除；（4）哈希表。2．基本要求
（1）了解查找的作用，熟悉相关术语；
（2）熟练掌握顺序查找、折半查找和索引顺序表查找；（3）熟练掌握二叉排序树的特性、构造和查找方法；
（4）熟练掌握哈希表的构造方法，特别是哈希函数和处理冲突方法的选取；（5）通过分析等概率下的平均查找长度来衡量各种查找方法的效率。3．自学内容：
平衡二叉树。
（九）内部排序（4 学时）1．主要内容：
（1）排序的基本概念和相关术语；
（2）插入排序：直接插入排序、折半插入排序和希尔排序；（3）交换排序：起泡排序和快速排序；（4）选择排序：简单选择排序和堆排序；（5）归并排序：二路归并排序；（6）基数排序：链式基数排序；（7）各种内部排序方法的比较讨论。2．基本要求
（1）了解排序作用，熟悉相关术语；
（2）掌握多种排序的基本思想、算法特点和排序过程，分析它们的时间复杂度、空间复杂度和稳定性。
3．自学内容：
二路插入排序、表插入排序和树形选择排序。
四、教学安排建议
1.作业练习 完成每章的教学后进行布置习题，使用教材配套的《数据结构题集（C语言版）》。尽量选择基础的并且加注了标记的题，应注重于精，而不要求多。要求积极独立完成所布置的习题，建议安排至少六次。
2.案例分析
可参考选择以下一些案例：（1）学生通讯录管理系统，（2）表达式求值问题（3）交通咨询系统，等。3.专题研讨
可参考选择以下一些：（1）最小生成树问题（2）航班信息查询与检索系统，（3）内部排序算法比较，等。
4.实验安排
为了达到理论与实际应用的结合，让学生能将所学知识应用于实际问题的求解中，培养学生的实际动手能力，从而加深对概念及所学知识的理解，灵活、牢固掌握教材内容，提高程序设计及解决实际问题的能力，实验环节的安排非常重要。
建议实验安排为八次，共16学时，分别如下：
实验1 线性表的顺序存储结构的实现(2学时)
实验2 线性表的链式存储结构的实现(2学时)
实验3 栈的算法实现(2学时)
实验4 队列的算法实现(2学时)
实验5 串类型及操作(2学时)
实验6 二叉树的建立与遍历(2学时)
实验7 图的建立与遍历(2学时)
实验8 查找与排序(2学时)注：教师可根据教学实际情况（如：学生情况及学时情况等），适当调整实践教学内容及学时分配。
五、课程考核
1.考核形式及成绩评定办法
本课程考核形式为：平时成绩占40%，期末考试成绩占60%。其中平时成绩的结构分包括：课堂表现10%、平时作业10%和实验20%，期末考试为闭卷笔试考试：120分钟，卷面分满分100分。期末考试成绩低于50分者，本课程成绩按不及格论处。
2.本课程考核的基本要求
课堂表现10%：包括课堂考勤和课堂提问，如果缺课课时达到本课程教学时数的1/3，则取消考试资格。
平时作业10%：根据上交次数及完成情况进行评定。
实验20%：根据各次实验完成情况及实验报告成绩进行评定。
期末考试60%：本课程的期末考试考核内容主要包括线性表、栈与队列、串、数组与广义表、树与二叉树、图、查找和内部排序。其中，线性表、二叉树、图、查找和内部排序内容为考核的重点。
六、本课程与其它课程的先行后续关系
先行课程：《高级程序设计语言》、《离散数学》
后续课程：《操作系统》、《编译原理》、《数据库理论》、《算法分析与设计》等
七、建议教材及教学参考书
1.教材：
严蔚敏，吴伟民编著，《数据结构（C语言版）》，清华大学出版，2012.5 严蔚敏，吴伟民编著，《数据结构题集（C语言版）》，清华大学出版，2012.5 2.参考书：
[1] 许卓群，张乃孝，杨冬青，唐世渭，《数据结构》，高等教育出版社，2004.[2] 徐孝凯，《数据结构简明教程》，清华大学出版社，1995 [3] 陈文博，朱青，《数据结构与算法》，机械工业出版社，1996 [4] 李云清，杨庆红，揭安全编著，《数据结构》（C语言版），人民邮电出版社，2007.[5] 杨秀金主编，《数据结构》，西安电子科技大学出版社，2002.[6] 李廉治，姜文清，郭福顺，《数据结构》，大连理工大学出版社，1989
[7] Aho A V, Hopcroft J E, Ullman J D.Data Structures and Algorithms.Addison-Wesley Publishing Company,Inc.,1983
[8] Baron R J, Shapiro L G.Data Structures and their Implementation.Van Nostrand Reinhold Company, 1980
[9] Esakov J, Weiss T.Data Structures: An Advanced Approach Using C.Prentice-Hall, Inc.,1989
[10] [美]S巴斯《计算机算法：设计和分析引论》朱洪等译，复旦大学出版社，1985
第二篇：数据结构课程教学大纲
数据结构课程教学大纲
一、课程基本概况
课程名称：数据结构
课程名称（英文）： Data Structures
课程编号：B09042
课程总学时：60（其中，讲课48，实验12）
课程学分：3
课程分类：专业选修课
开设学期：4
适用专业：计算机网络工程本科
先修课程：集合论，图论，高级语言（结构或记录，指针）
后续课程：数据库，编译原理，操作系统等
二、课程的性质、目的和任务
数据结构是计算机专业的一门核心专业课程，是软件课程中非常重要的一门课程，在整个专业教学中占有十分重要的地位，是一门理论性非常强的课程。通过课堂教学、课外练习和上机实习，使学生了解数据对象的特性，数据组织的基本方法，并初步具备分析和解决现实世界问题在计算机中如何表示和处理的能力以及培养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。
三、主要内容、重点及深度
本门课程共60学时，其中理论教学48学时，实验教学12学时。其中，理论教学部分：
第一章
绪论
（一）目的要求
了解数据结构的意义与发展过程、数据结构在计算机科学中的作用、学习本课程的目的、任务及要求。理解数据结构的基本概念；算法设计；掌握算法的时间和空间复杂度。
（二）教学内容 本章知识点：
1.相关的基本概念(掌握)；
2.算法五大要素(掌握)；
3.计算语句频度和估算算法时间复杂度的方法（掌握）。
（三）重点与难点
重点：数据结构的定义；算法的描述方法。
难点：数据结构的定义；算法与程序的区别；时间复杂度及其计算。
第二章
线性表
（一）目的要求
掌握线性表的逻辑结构；线性表的存储结构及操作的实现；理解一元多项式的表示；
（二）教学内容 本章知识点：
1.线性表的逻辑结构(掌握)；2.线性表的存储结构(掌握)；
3.线性表在顺序结构和链式结构上实现基本操作的方法(掌握)；
4.从时间和空间复杂度的角度比较线性表两种存储结构的不同特点及其适用场合(掌握)。
（三）重点与难点
重点：线性表的概念；线性表的顺序存储结构、链式存储结构及其常用算法。难点：链式存储结构及其常用算法；双向循环链表。
第三章 栈和队列
（一）目的要求
掌握栈的定义，表示及实现；表达式求值；栈与递归过程；队列的定义、表示及实现。
（二）教学内容 本章知识点： 1.栈和队列的特点(掌握)；
2.在两种存储结构上栈的基本操作的实现(掌握)； 3.循环队列和链队列的基本运算(熟练掌握)； 4.递归算法执行过程中栈状态的变化过程(掌握)。
（三）重点与难点
重点：堆栈和队列的概念；递归的定义；循环队列和链队列的基本运算。难点：递归的编程实现；循环队列和链队列的基本运算。
第四章 串
（一）目的要求
了解串的逻辑结构，存储结构；掌握串操作的实现(重点难点BF和KMP算法)串的应用。
（二）教学内容 本章知识点：
1.串的七种基本运算的定义（了解）；
2.利用这些基本运算来实现串的其它各种运算的方法(掌握)； 3.在顺序存储结构上实现串的各种操作的方法(掌握)；
4.KMP算法，熟悉NEXT函数和改进NEXT函数的定义和计算(掌握)； 5.串名的存储映象和在堆存储结构实现串操作的方法(理解)。
（三）重点与难点 重点：串定义和存储方法；串的操作 难点：串操作实现方法
第五章 数组和广义表
（一）目的要求
掌握数组的存储结构；稀疏矩阵的表示及操作的实现；广义表的定义和存储结构；广义表的递归算法。
（二）教学内容 本章知识点：1.数组在以行为主的存储结构中的地址计算方法(掌握)； 2.矩阵实现压缩存储时的下标变换(掌握)；
3.理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法(掌握)；
4.广义表的定义及其存储结构，学会广义表的表头，表尾分析方法(掌握)； 5.学习编制广义表的递归算法(掌握)。
（三）重点与难点
重点：多维数组元素存储地址的计算；稀疏矩阵的三元组表示；广义表的存储定义、操作。难点：稀疏矩阵的三元组表示；广义表的存储定义、操作。
第六章 树和二叉树
（一）目的要求
了解树的基本概念；理解二叉树的性质和存储结构；遍历二叉树和线索二叉树；理解树的存储结构和遍历；集合的一种表示方法；掌握哈夫曼树及其应用；
（二）教学内容 本章知识点： 1.二叉树的结构特点(理解)；
2.二叉树的各种存储结构的特点及适用范围(掌握)； 3.按各种次序遍历二叉树的递归和非递归算法(掌握)；
4.二叉树的线索化，在中序线索树上找给定结点的前驱和后继的方法(掌握)； 5.树的各种存储结构及其特点(掌握)； 6.编写树的各种运算的算法(掌握)；
7.建立最优二叉树和哈夫曼编码的方法(掌握)。
（三）重点与难点 重点：二叉树的概念、性质；二叉树的遍历方式；构造二叉排序树。难点：二叉树的遍历方式；二叉排序树的构造方法；二叉树的线索化。
第七章 图
（一）目的要求
理解图的基本概念；图的存储结构；掌握图的遍历及应用{最小生成树，最短路径等}；拓扑排序和关键路径。
（二）教学内容 本章知识点： 1.熟悉图的各种存储结构；
2.了解实际问题与采用何种存储结构和算法有密切联系(掌握)； 3.遍历图的递归和非递归算法(掌握)；
4.应用图的遍历算法求各种简单路径问题（比如，最小生成树、最短路径、拓扑排序、关键路径等）(掌握)。
（三）重点与难点
重点：图的存储结构；图的遍历 难点：图遍历的算法；
第八章
动态存储管理
（一）目的要求
了解边界标识法和伙伴系统；无用单元收集和紧缩；
（二）教学内容 本章知识点：
1.存储器分配策略和算法（了解）；
2.无用单元收集时的标志算法（了解）。
（三）重点与难点
存储器分配策略和算法、无用单元收集时的标志算法
第九章
查找
（一）目的要求
了解静态查找表(顺序表，有序表，索引顺序表)；动态查找表(二叉排序树，平衡二叉树，B-树和B+树)的建立和查找；掌握哈希表的建立，查找及分析；
（二）教学内容 本章知识点：
1.顺序查找、折半查找和索引查找的方法、应用(掌握)；
2.二叉排序树的构造方法(掌握)；
3.二叉平衡树的建立方法(掌握)；
4.B-树，B+树和键树的特点以及它们的建立过程（理解）；
5.哈希表的构造方法(掌握)；
6.按定义计算各种查找方法在等概率情况下查找成功时和失败时的平均查找长度；
7.哈希表在查找不成功时的平均查找长度的计算方法(掌握)。
（三）重点与难点
重点：二叉排序树的构造方法、二叉平衡树的建立方法；哈希表的构造、应用；
难点：二叉排序树的构造及应用；哈希表的构造方法；查找的平均长度。
第十章
内部排序
（一）目的要求
掌握插入排序、交换排序(起泡排序，快速排序)、选择排序(简单选择，树形选择，堆)、归并排序、基数排序等算法。
（二）教学内容 本章知识点：
1.各种排序方法的特点并能灵活应用(掌握)； 2.各种方法的排序过程(掌握)；
3.各种排序方法的时间复杂度分析(掌握)。
（三）重点与难点
重点：各种排序方法的特点及其应用；实现排序的各种算法。难点：各种排序算法的时间复杂度分析。
十一章
外部排序
（一）目的要求
理解外部排序的基本方法；掌握败者树和多路平衡归并的实现；置换--选择排序；最佳归并树。
（二）教学内容 本章知识点：
1.外部排序的两个过程(理解)；
2.外排过程中所需进行外存读/写次数的计算方法(掌握)；
3.败者树的建立过程(掌握)；
4.实现多路归并的算法(掌握)；
5.置换-选择排序的过程(掌握)；
6.最佳归并树的构造方法（熟悉）；
7.按最佳归并树的归并方案进行平衡归并时，外存读/写次数的计算方法(掌握)。
（三）重点与难点
重点：外部排序过程和实现方法；多路并归算法及其实现； 难点：最佳并归树的构造方法及其应用。
实践教学部分：上机实验分4个专题，每个专题可提供2~4个难度不等的题目供选。
实验一
停车场管理系统
（一）实验内容 以栈模拟车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现。
（二）实验过程 编程实现实验内容。
（三）实验教学基本要求
通过实例，使学生掌握栈和队列两种特殊的线性结构，掌握栈和队列的特点。实验后学生提交实验报告。
（四）实验设备和材料 计算机。
（五）实验学时 4学时
实验二
教学计划编制问题
（一）实验内容
假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。编制一个教学计划程序。
（二）实验过程编程实现实验内容。
（三）实验教学基本要求
通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。实验后学生提交实验报告。
（四）实验设备和材料 计算机。
（五）实验学时 2学时
实验三
最小生成树问题
（一）实验内容
利用克鲁斯卡尔算法求最小生成树。以文本形式输出树中各条边以及他们的权值。
（二）实验过程 编程实现实验内容
（三）实验教学基本要求
通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。实验后学生提交实验报告。
（四）实验设备和材料 计算机。
（五）实验学时 2学时
实验四
哈希表设计
（一）实验内容
假设人名为中国人的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。
（二）实验过程 编程实现实验内容
（三）实验教学基本要求 掌握索引技术的使用。
（四）实验设备和材料 计算机
（五）实验学时 4学时
五、课程教学的基本要求和主要环节
本课程可采用课堂讲授、课堂讨论、习题课等进行课堂教学;条件允许可采用CAI、电子教案、幻灯片、参观等进行辅助教学;每章布置3~6道习题以巩固教学;在课程后半程，安排3~4个上机实验，让学生应用数据结构的理论、方法，分组设计几个较大的软件，使理论与实际相结合。
考试采用闭卷方式。总成绩由平时成绩和考试成绩组成。平时成绩占30%，考试成绩占70%。
六、本课程与其它课程的联系与分工
先修课包括：集合论，图论，高级语言（结构或记录，指针）；
后续课包括：数据库，编译原理，操作系统等。
七、建议教材与参考教材
《数据结构》（C语言版）
严蔚敏等
清华大学出版社
1997 《数据结构题集》
严蔚敏等
清华大学出版社
1999
《数据结构习题与解析》
李春葆
清华大学出版社
2004
八、负责人
撰稿人：刘景汇、李玉香
审稿人：
系（院）领导：
第三篇：《数据结构 A》课程教学大纲
《数据结构 A》课程教学大纲
Data Structure A
课程代码：
适用专业：信息计算、信息安全 总学时数：72
编写年月：2003年7月
执
笔：高学军、刘科峰、李小英
一、课程的性质和目的
数据结构是信息与计算科学专业的一门重要专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在信息与计算科学专业中具有举足轻重的作用。
课程性质：专业基础理论课/必修 开课学期：5 总学分数：4.5 修订年月：2007年7月
二、课程教学内容及学时分配
第1章 绪论（4学时）
理解数据、数据元素和数据项的概念及其相互间的关系。理解数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现。掌握简单的算法分析方法。
本章知识点为：数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。
第2章 线性表（10学时，2个学时实验上机）
理解线性表的定义及其运算。理解顺序表和链表的定义、组织形式、结构特征和类型说明，掌握在这两种表上实现的插入、删除和按值查找的算法。了解循环链表、双向(循环)链表的结构特点和在其上施加的插入、删除等操作。掌握稀疏多项式在线性表的两种存储结构上的实现方法。
本章知识点为：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构(顺序的和链式的)上实现基本操作；稀疏多项式的抽象数据类型定义、表示和加法的实现。
第3章 栈和队列（6学时，2个学时实验上机）
理解栈和队列的定义、特征及在其上所定义的基本运算。掌握在两种存储结构上对栈和队列所施加的基本运算的实现。熟练掌握循环队列和链队列的基本操作实现算法，尤其是队满和队空的描述方法。
本章知识点为：抽象数据类型栈的定义；栈的表示和实现；栈的应用；抽象数据类型队列的定义；链队列；循环队列。第4章 串（4学时，2个学时实验上机）
熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。掌握串的堆存储结构以及在其上实现串操作的基本方法。
本章知识点为：串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现及其应用；
第5章 数组和广义表（6学时，2个学时实验上机）
了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。掌握对特殊矩阵进行压缩存储时的下标变换公式。了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。掌握广义表的结构特点及其存储表示方法。
本章知识点为：数组的类型定义和表示方式；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现；广义表的逻辑结构和存储结构和广义表的操作。
第6章 树和二叉树（12学时，2个学时实验上机）
深刻理解树的定义、性质及其存储方法，熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义，并能画出给定二叉树的二叉链表的结构示意图；理解并掌握二叉树的三种遍历方法，并能写出该三种遍历的算法；会完成树、森林与二叉树间的相互转换；理解哈夫曼树的构造方法，并能对给定的数据集合构造出哈夫曼树。
本章知识点为：二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式；树和森林的定义、存储结构、与二叉树的转换、遍历；树的多种应用。
第7章 图（12学时，2个学时实验上机）
理解图的基本概念及术语，掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算法构造最小生成树；了解并掌握拓扑排序、关键路径、最短路径的算法思想。
本章知识点为：图的定义和术语；图的四种存储结构：数组表示法、邻接表、十字链表和邻接多重表；图的两种遍历策略：深度优先搜索和广度优先搜索；图的连通性：连通分量和最小生成树；拓扑排序和关键路径；两类求最短路径问题的解法。
第8章 查找（10学时，2个学时实验上机）
了解查找的基本思想及查找成功和不成功的概念，掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查找长度。
本章知识点为：讨论查找表(包括静态查找表和动态查找表)的各种实现方法：顺序表、有序表、树表和哈希表；平均查找长度的讨论。
第9章 内部排序（8学时，2个学时实验上机）了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤及算法。
本章知识点为：讨论比较各种内部排序方法，插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。在每类排序方法中，又从简单方法入手，重点讨论性能先进的高效方法。
三、课程教学的基本要求
本课程是信息与计算科学专业的重要专业基础课，计算机科学各领域及有关的系统和应用软件都要用到各种数据结构。在教学方法上采用课堂讲授，课后自学，课堂讨论等教学形式。
(一)课堂讲授
本课程属于基础理论课程。在传授知识原理的前提下，配合实际应用例子，由浅入深善于诱导，使学生从被动吸收知识的状态下，转化到主动索取知识的状态中来，并采用多媒体辅助教学，加大课堂授课的知识含量。注重培养学生的学习兴趣，提高学生的基本素质。
（二）课后自学
为了培养学生整理归纳，综合分析和处理问题的能力，每章都安排一部分内容，课上教师只给出自学提纲，不作详细讲解，课后学生自学。
（三）课堂讨论
课堂讨论的目的是活跃学习气氛，开拓思路。教师应认真组织，安排重点发言，充分调动每一名同学的学习积极性，做好总结。
（四）课外作业
为了让学生巩固所学的知识，每章都布置一定数量课外作业。
（五）实验
用C语言或C++语言完成一些算法设计题。培养学生的算法设计能力和程序设计能力。总评成绩：平时作业占30%，闭卷考试占70%。
四、本课程与其它课程的联系与分工
先修课程：离散数学，C++面向对象程序设计等。后续课程：操作系统，数据库原理等。
五、建议教材与教学参考书
[1] 严蔚敏 吴伟民编著，数据结构(C语言版)，北京:清华大学出版社, 2004 [2] 严蔚敏 吴伟民编著，数据结构题集(C语言版)，北京:清华大学出社，2004 [3] Willan Ford,Willian Topp.Data Structures with C++.New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company，1996(数据结构——C++语言描述.北京:清华大学出版社，1997)
[4] 徐孝凯，数据结构实用教程（C/C++描述），北京:清华大学出版社，1999 [5] 陈慧南.数据结构（使用C++语言描述），南京:东南大学出版社，2001 [6] 殷人昆,陶永雷,谢若阳等.数据结构（用面向对象方法与C++描述），北京:清华大学出版社，1999
第四篇：数据结构与算法课程教学大纲
教学大纲
数据结构与算法（Data Structures）
计算机技术已成为现代化发展的重要支柱和标志，并逐步渗透到人类生活的各个领域。随着计算机硬件的发展，对计算机软件的发展也提出了越来越高的要求。由于软件的核心是算法，而算法实际上是对加工数据过程的描述，所以研究数据结构对提高编程能力和设计高性能的算法是至关重要的。
非数值计算问题的数学模型不再是传统的数学方程问题，而是诸如表、树、图之类的数据结构。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题的学科，主要研究数据的逻辑结构、存储结构和算法。
一、教学目的与要求---了解数据的逻辑结构和物理结构；
教学要求在每章教学内容给出，大体上为三个层次：了解、掌握和熟练掌握。他们的含义大致为：了解是正确理解概念，掌握是学会所学知识，熟练掌握就是运用所学知识解决实际问题。
教学目的为：了解算法对于程序设计的重要性 ； 学习掌握基本数据结构的描述与实现方法，熟练掌握典型数据结构及其应用算法的设计。了解算法分析方法。
二、教学重点与难点--数据结构中基本概念和术语，算法描述和分析方法。
1、链表插入、删除运算的算法。算法时间复杂度
2、后缀表达式的算法，数制的换算
利用本章的基本知识设计相关的应用问题
3、循环队列的特点及判断溢出的条件
利用队列的特点设计相关的应用问题
4、串的模式匹配运算算法
5、二叉树遍历算法的设计
利用二叉树遍历算法，解决简单应用问题 哈夫曼树的算法
6、图的遍历
最小生成树
最短路径
7、二叉排序树查找
平衡树二叉树
8、堆排序
快速排序 归并排序
三、教学方法与手段-充分利用多媒体教学工具，配合黑板上的教学内容较难部分的算法实现过程演义
四、教学内容、目标与学时分配
教学内容 教学目标 课时分配
1、绪论
数据结构的内容
逻辑结构与存储结构
算法和算法分析
2、线性表
线性表的定义与运算
线性表的顺序存储
线性表的链式存储
3、栈
栈的定义与运算
栈存储和实现
栈的应用举例
4、队列
队列的定义与基本运算
队列的存储与实现
队列的应用举例
5、串
串的定义与基本运算
串的表示与实现
串的基本运算
6、树和二叉树
树的定义和术语
二叉树树的基本概念和术语 遍历二叉数和线索二叉树
二叉树的转换
二叉树的应用
哈夫曼树及其应用
7、图
图的定义和术语
图的存储结构
图的遍历算法
图的连通性
8、查找
查找的基本概念与静态查找 动态查找
哈希表
了解
了解
掌握
熟练掌握顺序表存储地址的计算
掌握单链表的结构特点和基本运算
掌握双链表的结构特点和基本运算
掌握栈的定义与运算
掌握栈的存储与实现
熟练掌握栈的各种实际应用
掌握队列的定义与基本运算
熟练掌握队列的存储与实现
掌握循环队列的特征和基本运算
了解串的逻辑结构
掌握串的存储结构
熟练掌握串的基本运算
了解
了解二叉树
熟练掌握二叉树定义和存储结构
了解二叉树的遍历算法
掌握
掌握哈夫曼的建立及编码
了解
了解
熟练掌握
熟练掌握
了解
熟练掌握
了解哈希表与哈希方法
4学时
1学时
1学时
2学时
8学时
2学时
2学时
4学时
8学时
2学时
2学时
4学时
6学时
2学时
2学时
2学时
6学时
2学时
2学时
2学时
12学时
2学时
2学时
2学时
2学时
2学时
2学时
8学时
2学时
2学时
2学时
2学时
8学时
4学时
2学时
2学时
9、排序
12学时 插入排序
熟练掌握基本思想
3学时 快速排序
了解各种内部排序方法和特点
3学时 选择排序
掌握
2学时 各种排序方法比较
掌握
2学时
实验内容 实验目标 课时分配 算法编程实验：
1、用指针方式编写程序 复习C（C++）语言指针、结构体等的用法
2、对单链表进行遍历
链表的描述与操作实现
3、栈及其操作
描述方法及操作
4、编写串子系统1 串的特点及顺序定长存储、操作、查找
5、编写串子系统 2 串的特点及顺序定长存储、操作、查找
6、编写树子系统1 二叉树的特点及存储方式、创建、显示、遍历等
7、编写树子系统2 二叉树的特点及存储方式、创建、显示、遍历等
8、图子系统
图的邻接矩阵的存储、遍历、广度/深度优先搜索
9、查找子系统
理解查找基本算法、平均查找长度、静态、动态查找等
五、考试范围与题型
1、考试范围与分数比例
1)绪论
12% 2)线性表
17% 3)栈
7% 4)队列
6% 5)串
4% 6)树和二叉树
14% 7)图
15% 8)查找
4% 9)排序
21%
2、考试题型与分数比例
1)名词解释
18% 2)判断对错
16% 3)填空
16% 4)单项选择
18% 5)应用
32%
六、教材与参考资料
1、教材： 实用数据结构基础（谭浩强）中国铁道出版社
2、参考资料： 数据结构（严蔚敏）清华大学出版社
数据结构实用教程（徐孝凯）清华大学出版社
（撰写人：
，审核人： 2学时 2学时 2学时 2学时 2学时 2学时 2学时 2学时 2学时）
第五篇：数据结构教学大纲(参考)
数据结构 Data Structure 课程代码：
学 时 数：64（讲课50 实验14 研讨0 实习实践1周）
学 分 数：
3、4 课程类别：学科基础课
开课学期：4 主讲教师：
编写日期： 2011年7月1日
一、课程性质和目的课程性质：数据结构A是计算机科学与技术、数字媒体艺术、信息管理与信息系统专业的一门重要学科基础课，是必修课。
教学目的：通过本课程的学习，一方面，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。
二、课程教学内容、学时分配和课程教学基本要求
1.绪论（理论2学时）
教学内容：
(1)数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构等。(2)抽象数据类型的表示和实现。(3)算法的概念和特性。
(4)算法时间复杂度和空间复杂度的分析。基本要求：
掌握数据结构的基本概念，了解抽象数据类型，掌握算法时间复杂度和空间复杂度的分析方法。
2.线性表（理论8学时，实验4学时）
教学内容：
(1)线性表的类型定义。(2)线性表的顺序表示和实现。(3)线性表的链式表示和实现。
(4)线性表的应用，包括无序表和有序表的合并、多项式的加法运算等。基本要求：
理解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。掌握顺序表的查找、插入和删除算法，掌握链表的查找、插入和删除算法。能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。掌握无序表和有序表的合并算法，了解多项式的加法运算。
实验：
实验内容：单链表的基本操作。实验要求：以单链表形式创建一个学生表或图书表，并能实现相关的查找、插入和删除等算法。3.栈和队列（理论6学时，实验4学时）
教学内容：
(1)栈的类型定义，栈的顺序存储和链接存储的表示和实现。(2)栈的应用举例，如迷宫求解和表达式求值。
(3)栈与递归的实现，递归程序转换为非递归程序的方法。
(4)队列的类型，队列的顺序存储(循环队)和链接存储的表示和实现。(5)队列的应用举例，如打印杨晖三角形，模拟汽车加油站等问题。基本要求：
掌握栈和队列的特点，并能在相应的应用问题中正确选用。熟练掌握栈的顺序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件。掌握利用栈实现表达式求值的算法，了解迷宫求解算法。理解递归算法执行过程中栈的状态变化过程，了解将递归程序转换为非递归程序的方法。熟练掌握循环队列和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况。了解队列的应用。
实验：
实验内容：栈的应用。实验要求：借助栈来解决某些实际应用问题，如表达式求值、迷宫问题等。
4.串、数组和广义表（理论2学时）
教学内容：
(1)串的表示和实现，包括顺序存储和链式存储表示。古典的模式匹配算法。(2)数组的存储方法。
(3)特殊矩阵和稀疏矩阵的压缩存储，稀疏矩阵的转置运算。(4)广义表的逻辑结构和存储结构。基本要求：
了解串的顺序存储结构和堆存储结构。掌握串的古典的模式匹配算法。掌握数组的地址计算方法。了解稀疏矩阵的两种压缩存储方法的特点和适用范围。了解广义表的结构特点及其存储方法。5.树和二叉树（理论8学时，实验2学时）
教学内容：
(1)二叉树的定义和术语，二叉树的性质，特殊的二叉树。(2)二叉树的存储结构，顺序存储和二叉链表。
(3)二叉树的的前序、中序、后序、层次遍历方法。线索化二叉树。(4)树和森林的定义，树的存储，树、森林与二叉树的转换。(5)树的应用，哈夫曼树及哈夫曼编码。基本要求：
了解树和森林的概念，包括树的定义、树的术语。掌握二叉树的概念、性质及二叉树的表示。熟练掌握二叉树的遍历算法，并且能灵活运用遍历算法实现二叉树的其他操作。掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法。了解树的存储、树和森林与二叉树的转换方法。掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算。
实验：
实验内容：二叉树的基本算法。实验要求：利用二叉链表方法建立二叉树，实现二叉树的前、中、后序三种遍历算法，并运用遍历算法实现二叉树的其他操作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等。6.图（理论8学时，实验2学时）
教学内容：
(1)图的定义和术语。
(2)图的存储结构两种存储结构：邻接矩阵和邻接表表示法。(3)图的两种遍历策略：深度优先搜索和广度优先搜索。(4)构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法。(5)拓扑排序和关键路径。
(6)两类求最短路径问题的算法，迪杰斯特拉算法和弗洛伊德算法。基本要求：
掌握图的基本概念及相关术语和性质，掌握图的邻接矩阵和邻接表表示法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。熟练掌握图的两种搜索路径的遍历：深度优先搜索和广度优先搜索的算法。掌握构造最小生成树的两种算法及拓扑排序算法的思想，掌握迪杰斯特拉算法。了解关键路径的概念和求解方法，了解弗洛伊德算法。
实验：
实验内容：图的建立和搜索。实验要求：使用邻接矩阵或邻接表表示法存储一个图，实现图的深度优先搜索和广度优先搜索的算法。7.查找（理论6学时）
教学内容：(1)查找的基本概念，平均查找长度。(2)基于线性表的查找：顺序查找、折半查找。
(3)基于树表的查找：二叉排序树、平衡二叉树、B-树和B+树。
(4)散列表：散列表的基本概念，散列函数的构造方法、处理冲突的方法、散列表的查找与分析。
基本要求：
熟练掌握顺序表和有序表的查找方法及其实现，掌握二叉排序树的插入和查找算法及其实现，了解平衡二叉树、B-树和B+树的各种操作。熟练掌握散列表的构造方法、处理冲突的方法，深刻理散列表与其他结构的表的实质性的差别，了解各种散列函数的特点。掌握描述折半查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
8.排序（理论8学时，实验2学时）
教学内容：
(1)排序的基本概念，包括正序，逆序，稳定性，排序方法的分类。(2)插入排序：直接插入排序、折半插入排序和希尔排序。(3)交换排序：冒泡排序和快速排序。(4)选择排序：简单选择排序和堆排序。(5)归并排序：2-路归并排序。
(6)基数排序：多关键字的排序和链数基数排序。
(7)排序算法分析：各种排序算法的比较和移动次数，时间复杂度和空间复杂度的分析。基本要求：
明确排序的基本概念，排序方法的分类。深刻理解排序算法的过程、特点及其依据的原则，并能加以灵活应用。掌握各种排序方法的时间和空间复杂度的分析方法。能从关键字间的比较次数和移动次数分析算法的平均情况和最坏情况的时间性能。理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。快速排序、堆排序和归并排序等高效排序方法是本章的学习重点和难点。
实验：
实验内容：综合性实验。实验要求：选取一个合适的数据结构存储数据，能对数据进行插入、删除，用不同查找算法进行查找、用不同的排序算法进行排序等。9.实习（1周）
教学内容：
(1)设计准备：理解实习任务，明确相关算法，搜集可用资源，熟悉实习环境。(2)方案设计：完成设计目标、设计路线的确定，并进行模块设计和任务分工。(3)代码编写：各模块代码编写，模块测试。(4)代码测试：模块组装，整体测试。(5)设计报告：完成设计文档，制作设计报告。基本要求：
能将数据结构课程中所学的基本知识融会贯通，综合运用所学的知识解决相关的实际问题，能够把所学知识（包括算法和结构）在计算机上用编程语言加以实现，并且能够根据实际需求创建自己的数据结构和实现自己的算法。
本课程的教学环节包括：课堂讲授、实验、实习、作业、答疑、小测验等。其中，课堂讲授以教师讲授为主，授课时将电子教案和板书相结合，充分发挥各自的优点。采用启发式教学，鼓励学生自学，培养学生的自学能力，以“少而精”为原则，精选教学内容，调动学生学习的主观能动性。实验针对相应单元所学的内容，能够采取合适的数据结构和算法解决有关问题。实验重点培养学生的动手能力。实习针对较为复杂的应用问题，能够综合运用所学的各种数据结构进行算法设计和实现，注重学生数据抽象能力和算法设计能力的培养。
三、本课程与其它课程的联系和分工
本课程的先修课为程序设计基础和离散数学，本课程可以C/C++或Java语言作为算法描述和上机实践的工具。同时，本课程又是软件开发与设计等方面课程的基础，如数据库、操作系统、编译原理、软件工程等课程。
四、本课程的考核方式
期末考试采用笔试形式，考试题型为：选择、填空、判断、应用题和算法设计题。总评成绩由平时成绩和期末成绩组成，其中平时成绩占30%--40%，期末考试占70%--60%。
课程实习的成绩由平时成绩和实习作业两部分组成，其中平时成绩占30%，实习作业占70%。
五、建议教材与教学参考书
建议教材：
1.严蔚敏，李冬梅，吴伟民．数据结构（C语言版）．北京：人民邮电出版社． 2.严蔚敏主编．数据结构（C语言版）．北京：清华大学出版社．
3.殷人昆主编．数据结构（用面向对象方法与C++描述）．北京：清华大学出版社． 建议教学参考书：
1.[美]Bruno R.Preiss著，胡广斌，王崧等译．数据结构与算法－面向对象的C++设计模式．北京：电子工业出版社．
2.殷人昆主编．数据结构与习题解析（用面向对象方法与C++描述）．北京：清华大学出版社．
六、课程简介
数据结构是一门专业基础课，是学习其他软件开发与设计等方面课程的基础。主要内容包括：线性表、栈和队列、串、数组和广义表、树、图、查找算法和排序算法。数据结构研究数据的组织方式，内容丰富、学习量大，隐含在各部分内容中的方法和技术多，旨在让学生掌握计算机软件系统所必需的数据结构的算法。要求学生掌握贯穿全课程的动态链表存储结构，掌握算法设计的动态性和抽象性。要求学生学会分析研究计算机加工的数据对象的特征，以便在实际应用中选择适当的数据结构、存储结构和相应算法，初步掌握算法的时间与空间性能分析技巧，并培养复杂程序设计的技能。
执笔人：
审核人：
教学院长：
院学术委员会：
院长：
点击咨询 