数据结构教学大纲
数据结构教学大纲
(56学时)
一、课程性质、适用专业及层次
本课程是我院计算机专业的一门综合性的专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。
本大纲适用于三年制专科层次。适用专业——计算机应用相关专业。
二、课程教学目标
本课程的教学目标是：使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。在教学中注重综合应用能力培养，切实提高学生的综合素质。
(一) 知识教学目标
1、了解数据结构及其分类、数据结构与算法的密切关系。
2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。3、掌握设计算法的步骤和算法分析方法。
4、掌握数据结构在排序和查找等常用算法中的应用。5、初步掌握文件组织方法和索引技术。(二) 能力培养目标
培养基本的、良好的程序设计技能，编制高效可靠的程序。(三) 思想教育目标
1、注重培养学生独立思考能力，学会科学地分析和解决问题。2、培养学生的团结协作能力。
3、培养学生求真务实、讲求时效和一丝不苟的学习态度。4、为学生形成良好的职业道德打下基础。
三、教学内容和要求理论教学模块
(一) 数据结构基本概念及简单的算法分析
教学内容：1. 什么是数据结构
2. 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言
3. 数据结构的抽象层次4. 算法定义
5. 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂.
教学要求：
1. 了解数据结构基本概念及数据结构的抽象层次2. 了解抽象数据类型及面向对象概念3. 了解算法的定义及算法的特性4. 掌握算法的性能分析与度量方法(二) 数组教学内容：
1. 作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式
2. 顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例
3. 字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配教学要求：
1. 解作为抽象数据类型的数组的定义
2. 熟练掌握顺序表的数组定义方式及实现3. 熟练掌握字符串的定义及实现(三) 链表教学内容：
1. 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表
2. 循环链表：循环链表的类定义；用循环链表解约瑟夫问题；多项式及其相加：多项式的类定义；多项式的加法
3. 双向链表教学要求：
1. 熟练掌握单链表、循环链表及双向链表的定义及实现2. 掌握链表的游标类定义及其应用方法(四) 栈和队列教学内容：
1. 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示
2. 队列：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；3. 队列的应用举例
4. 优先级队列：优先级队列的定义；优先级队列的存储表示教学要求：
1. 熟练掌握栈的定义及实现2. 熟练掌握队列的定义及实现
3. 掌握优先级队列的定义及链表实现(五) 递归教学内容：
1. 递归的概念2. 迷宫问题
3. 递归过程与递归工作栈
4. 利用栈实现的迷宫问题非递归解法
5. 广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广义表的访问算法；广义表的递归算法
教学要求：
1. 掌握递归的概念
2. 掌握递归过程的机制与利用递归工作栈实现递归的方法3. 了解利用栈如何实现迷宫问题的非递归解法4. 掌握广义表的定义及其实现方法5. 掌握广义表的递归算法(六) 树与森林教学内容：
1. 树和森林的概念：树的定义；树的术语；树的抽象数据类型
2. 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型3. 二叉树的表示：数组表示；链表存储表示
4. 二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；二叉树遍历的游标类；不用栈的二叉树中序遍历算法
5. 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6. 堆：堆的定义；堆的建立；堆的插入与删除
7. 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历；二叉树的计数
8. 霍夫曼树：路径长度；霍夫曼树；霍夫曼编码教学要求：
1. 了解树和森林的概念
2. 掌握二叉树的概念、性质及二叉树的表示
3. 熟练掌握二叉树的遍历方法及树的游标类定义
4. 掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法。
5. 熟练掌握堆的定义及其实现的方法，以及用来实现优先级队列的方法6. 掌握树与森林的实现和遍历方法
7. 掌握二叉树的计数方法及从二叉树遍历结果得到二叉树的方法8. 掌握霍夫曼树的实现方法及霍夫曼编码的概念(七) 集合与搜索教学内容：
1. 集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量实现集合抽象据类型；用有序链表实现集合的抽象数据类型
2. 等价类：等价关系与等价类；确定等价类的链表方法；并查集
3. 简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的对分搜索
4. 二叉搜索树：定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除；与二叉搜索树相关的中序游标类
5. AVI 树：AVI 树的定义；平衡化旋转；AVI 树的插入和删除；AVI 树的高度教学要求：
1. 掌握集合及其表示方法
2. 掌握等价类的链表实现与利用并查集实现的方法3. 熟练掌握静态搜索表的顺序搜索和折半搜索方法
4. 熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法5. 掌握avl 树的构造、性能分析方法(八) 图教学内容：
1. 图的基本概念：图的基本概念；图的抽象数据类型2. 图的存储表示：邻接矩阵；邻接表；邻接多重表
3. 图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；重连通分量4. 最小生成树：克鲁斯卡尔算法；普里姆算法
5. 活动网络：用顶点表示活动的网络；用边表示活动的网络教学要求：
1. 掌握图的基本概念和图的存储表示
2. 熟练掌握图的两种遍历方法与求解连通性问题的方法3. 掌握构造最小生成树的prim 和kruskal 方法4. 熟练掌握活动网络的拓扑排序方法5. 掌握求解关键路径的方法(九) 排序教学内容：1. 概述
2. 插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序3. 交换排序：起泡排序；快速排序
4. 选择排序：直接选择排序；锦标赛排序；堆排序
5. 归并排序：归并；迭代的归并排序算法；递归的表归并排序6. 基数排序：多关键码排序；链式基数排序
7. 外排序：外排序的基本过程；k 路平衡归并；初始归并段的生成；最佳归并树教学要求：
1. 掌握排序的基本概念和性能分析方法
2. 掌握插入排序、交换排序、选择排序、归并排序等内排序的方法及其性能分析方法3. 了解基数排序方法及其性能分析方法
4. 掌握多路平衡归并等外排序方法及败者树构造方法5. 掌握生成初始归并段及败者树构造方法6. 掌握最佳归并树的建立方法(十) 索引与散列结构教学内容：
1. 静态索引结构：线性索引；倒排表；m 路静态查找树
2. 动态索引结构：动态的m 路查找树；b_树；b_树的插入；b_树的删除；b+树
3. 散列：词典的抽象数据类型；散列表与散列方法；散列函数；处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析
教学要求：
1. 熟练掌握静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法2. 熟练掌握：动态索引结构，包括b_树、b+树的搜索和构造方法3. 熟练掌握：散列法，包括散列函数的构造、解决冲突的方法
实践教学模块
实验一链表基本操作实验二栈的应用实验三队列的应用实验四二叉树的操作实验五图的操作实验六查找实验七排序
四、说明
1、本课程教学内容采用模块结构，包括理论教学模块、实践教学模块，应严格按照规定的课时授课。
2、教学建议（1）教学组织
本课程以班级形式组织教学，班级人数以40人左右为宜。（2）教学方法和手段
①教学中应将理论教学与实践教学紧密结合，使之相互辅助，提高教学效果。②实践教学采用一人一机上机操作、任课教师跟班辅导的方式，使学生有充分的机会在计算机上练习，既培养学生自己动手解决问题的能力，又可以及时解决上机操作时所遇到的疑难问题。
④为加强和落实动手能力的培养，应保证上机机时不少于本教学大纲规定的实验学时。⑤对关键性概念、整体实现思想方面的问题可辅以课堂讨论的形式。3．考核方式
要注意改革考核手段与方法，可通过课堂提问、学生作业、平时测验、实验及考试情况综合评定学生成绩。根据本课程实践性较强的特点，可采用笔试与机试相结合的形式。
学时分配建议(56学时)
学
课程内容
模块
（一）引论理论教学模块
（六）树和二叉树
4
4
（二）线性表（三）栈和队列（四）串
（五）数组和广义表
2444
2444
2讲授
时实践教学
2数
合计
（七）图（八）查找（九）排序（十）递归（十一）文件实验一链表基本操作实验二栈的应用实践模块
实验六查找实验七排序实验三队列的应用实验四二叉树的操作实验五图的操作
44224
222222
[1**********]
22
机总
动计
440
216
656