《数据结构》课程教学大纲计算机.docx
《《数据结构》课程教学大纲计算机.docx》由会员分享，可在线阅读，更多相关《《数据结构》课程教学大纲计算机.docx（19页珍藏版）》请在冰点文库上搜索。
《数据结构》课程教学大纲计算机
《数据结构》课程教学大纲
一、课程基本信息
开课单位
信息与网络工程学院
课程类别
专业基础
课程名称
中文名称：
数据结构
英文名称DataStructure
课程编码
ZJ28106
开课对象
计算机科学与技术专业
开课学期
3
学时/学分
总学时72、理论课学时48、实验课学时24
先修课程
程序设计基础、离散数学
课程简介：
《数据结构》是计算机学科的专业基础课程。
本课程主要内容有线性表、堆栈、队列、串、数组、二叉树和图等典型数据结构的设计方法，各种典型排序和查找算法，以及各种典型数据结构的应用。
通过本课程的学习，能使学生熟练地掌握数据结构的内在逻辑关系及其在计算机中的表示方法，以及有关基本操作的算法实现；能培养和训练学生结合实际应用，根据求解的问题合理选择数据结构、应用高级语言编写和实现结构清晰、正确易读的有效算法的能力；并为学习《操作系统》、《数据库原理》等后续课程和研制开发各种应用软件打下扎实的理论和实践基础。
二、课程教学目标
本课程介绍软件设计中常用的线性表、栈、队列、串、数组、广义表、树、二叉树、图结构等几种基本的数据结构及其存储结构和所施加的运算与实现等。
另外，还介绍软件设计中常用的几种查找和排序算法，以及递归技术等，在介绍各项内容的同时，还涉及到算法设计与分析的基本技术和面向对象程序设计的理论与技术等内容。
通过本课程的学习，达到以下目标：
熟练掌握上述结构及其运算的实现和性能特点，
掌握各种排序和查找运算以及递归技术，
能对给定的实际问题，建立准确的问题模型，设计有效的问题求解方法，选择合理的数据结构及其运算集，设计有效的算法。
三、教学学时分配
《数据结构》课程理论教学学时分配表
章次
主要内容
学时分配
教学方法或手段
第一章
数据结构概论
2
多媒体
第二章
线性表
6
多媒体
第三章
栈和队列
8
多媒体
第四章
串
3
多媒体
第五章
数组和广义表
3
多媒体
第六章
树与二叉树
8
多媒体
第七章
图
8
多媒体
第八章
查找
4
多媒体
第九章
排序
6
多媒体
合计
48
＊理论学时包括讨论、习题课等学时。
《数据结构》课程实验内容设置与教学要求一览表
实验项目名称
实验内容
教学要求
学时
分配
实验
类别
）
实验
类型
每组
人数
1
顺序表的存储与实现
1、初始化顺序表；
2、在第I个元素前插入一个元素e；
3、删除第I个元素；
4、遍历顺序表；
5、求顺序表的长度；
6、取顺序表的第I个元素。
掌握顺序表的基本操作：
初始化、插入、删除、取数据元素等运算在顺序存储结构的程序设计方法。
2
必做
设计性
1
2
单链表的存储与实现
1、初始化单链表；
2、在第I个元素前插入一个元素e；
3、删除第I个元素；
4、遍历单链表；
5、求单链表的长度；
6、取单链表的第I个元素。
掌握单链表的基本操作：
初始化、插入、删除、取数据元素等运算在链表存储结构的程序设计方法。
2
必做
设计性
1
3
栈的基本操作与应用
1、初始化栈；
2、入栈；
3、出栈；
4、遍历栈；
5、求栈的长度；；
6、判断队列空。
掌握顺序栈和链栈的基本操作：
初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。
2
必做
设计性
1
4
队列的基本操作
1、初始化队列；
2、入队列；
3、出队列；
4、遍历队列；
5、求队列的长度；
6、判断队列空。
掌握循环队列基本操作：
初始化队列、判队列空否、入队列、出队列、取队列顶数据元素等运算以及程序实现方法。
2
必做
设计性
1
5
串的基本操作
1、串的复制；
2、判断串相等；
3、求子串；
4、串的连接；
5、插入子串；
6、删除子串；
7、串的替换。
掌握字符串基本操作：
串的复制、判断串相等、求子串、串的连接、插入子串、删除子串等运算以及程序实现方法。
2
必做
设计性
1
6
二叉树遍历
1、定义二叉树的链式存取结构；
2、二叉树的基本操作（创建二叉树、递归（先、中、后序）遍历、非递归中序遍历、求二叉树的深度、叶子结点数）
1、理解二叉树性质和存储结构；
2、掌握二叉树的遍历算法，并能在遍历算法算法的基础上实现更复杂算法设计。
2
必做
设计性
1
7
哈夫曼树的操作
建立哈夫曼树
哈夫曼编码
掌握建立哈夫曼树的算法，理解哈夫曼编码算法。
2
必做
设计性
1
8
图的遍历
1、图的邻接矩阵、邻接表存储表示；
2、图的深度和广度优先搜索算法。
1、理解图的邻接矩阵、邻接表存储表示；
2、掌握图的深度和广度优先搜索算法。
2
必做
设计性
1
9
拓扑排序
邻接表存储表示
2、拓扑排序算法
1、掌握邻接表存储表示；
2、掌握拓扑排序算法。
2
必做
设计性
1
10
查找
1、顺序查找；
2、二分查找；
3、二叉排序树的查找。
1、掌握常用查找方法的基本思想及其实现技术；
2、了解各种查找方法的优缺点和适用范围。
2
必做
设计性
1
11
排序
1、直接插入排序；
2、冒泡；
3、选择排序；
4、快速排序；
5、希尔排序；
6、堆排序。
1、掌握常用排序方法的基本思想及其实现技术；
2、了解各种排序方法的优缺点和适用范围。
4
必做
综合性
1
四、教学内容和教学要求
第一章绪论（2学时）
（一）教学要求
1．了解数据结构的各种基本概念和术语；
2．了解数据类型和抽象数据类型的概念；
3．理解算法的设计目标；
4．掌握算法的时间复杂度概念和算法的时间复杂度分析方法。
（二）教学重点与难点
教学重点：
数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系
教学难点：
算法复杂度的分析方法。
（三）教学内容
第一节什么是数据结构
1．数据结构的定义
2．逻辑结构类型
3．存储结构类型
4．数据结构和数据类型
第二节算法及其描述
1．什么是算法
2．算法描述
第三节算法分析
1．算法设计的目标
2．算法效率分析
3．算法存储空间分析
本章习题要点：
基本概念、算法复杂度的分析方法
第二章线性表（10学时）
（一）教学要求
1．理解线性表的逻辑结构和基本操作；
2．理解线性表的顺序存储结构和实现方法；
3．理解线性表的链式存储结构和实现方法；
4．了解单循环链表和双向链表的概念和插入、删除等操作方法。
（二）教学重点与难点
教学重点：
顺序表和单链表上实现的各种基本算法及相关的时间性能分析。
教学难点：
链表本质及其操作的实现算法、线性表相关的应用。
（三）教学内容
第一节线性表
1．线性表的定义
2．线性表的抽象数据类型描述
第二节线性表的顺序存储结构
1．线性表的顺序存储结构——顺序表
2．顺序表基本运算的实现
第三节线性表的链式存储结构
1．线性表的链式存储结构——链表
2．单链表基本运算的实现
3．双链表
4．循环链表
本章习题要点：
第三章栈和队列（12学时）
（一）教学要求
1．理解栈的定义、特征及在其上所定义的基本运算；
2．掌握在两种存储结构上对栈所施加的基本运算的实现；
3．了解数制转换、括号匹配、表达式运算、迷宫等几种栈的典型应用；
4．理解队列的定义、特征及在其上所定义的基本运算；
5．掌握在两种存储结构上对队列所施加的基本运算的实现。
（二）教学重点与难点
教学重点：
栈和队列在两种存储结构上实现的基本运算。
教学难点：
栈与递归过程的实现，循环队列中对边界条件的处理。
（三）教学内容
第一节栈
1．栈的定义
2．栈的顺序存储结构及其基本运算实现
3．栈的链式存储结构及其基本运算的实现
4．栈的应用举例
第二节队列
1．队列的定义
2．队列的顺序存储结构及其基本运算的实现
3．队列的链式存储结构及其基本运算的实现
4．队列的应用举例
本章习题要点：
栈和队列的基本运算的实现
第四章串（5学时）
（一）教学要求
1．掌握串的定义、存储及串的比较、求子串、连接、赋值等基本运算；
2．了解基本的串模式匹配算法和KMP匹配算法。
（二）教学重点与难点
教学重点：
串的定义及基本运算，串的模式匹配算法。
教学难点：
KMP模式匹配方法。
（三）教学内容
第一节串的基本概念
第二节串的存储结构
1．串的顺序存储结构——顺序串
2．串的链式存储结构——链串
第三节串的模式匹配
1．BruteForce算法
2．KMP算法
本章习题要点：
第五章数组和广义表（3学时）
（一）教学要求
1．掌握数组的定义及数组元素的存储方式；
2．掌握特殊矩阵的压缩存储及运算；
3．了解稀疏矩阵的三元组表、理解以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；
4．了解广义表的定义、存储和基本运算。
（二）教学重点与难点
教学重点：
多维数组的存储方式、矩阵的压缩存储方式。
教学难点：
稀疏矩阵的压缩存储表示下实现的算法。
（三）教学内容
第一节数组
1．数组的基本概念
2．数组的存储结构
3．特殊矩阵的压缩存储
第二节稀疏矩阵
1．稀疏矩阵的三元组表示
2．稀疏矩阵的十字链表表示
第三节广义表
1．广义表的定义
2．广义表的存储结构
3．广义表的运算
本章习题要点：
特殊矩阵的压缩存储及运算
第六章树（12学时）
（一）教学要求
1．掌握树和二叉树的定义及基本运算；
2．掌握二叉树的性质、存储结构和操作的实现方法；
3．掌握二叉树的先序、中序、后序、层序遍历过程及相应的遍历算法；
4．了解二叉树的线索化处理过程；
5．了解树的孩子表示法和双亲表示法，了解树的孩子－兄弟表示法；
6．掌握树与二叉树的相互转化方法；
7．掌握哈夫曼树的概念和哈夫曼树在编码方面的应用方法。
（二）教学重点与难点
教学重点：
二叉树的性质；二叉树的遍历算法和二叉树遍历算法的应用；哈夫曼树在编码方面的应用方法。
教学难点：
二叉树的遍历算法及哈夫曼树的构造算法
（三）教学内容
第一节树的基本概念
1．树的定义
2．树的逻辑表示方法
3．树的基本术语
4．树的存储结构及基本运算
第二节二叉树的概念和性质
1．二叉树的概念
2．二叉树的性质
3．二叉树与树、森林之间的转换
第三节二叉树存储结构
1．二叉树的顺序存储结构
2．二叉树的链式存储结构
第四节二叉树的基本运算及其实现
1．二叉树的基本运算概述
2．二叉树的基本运算算法实现
第五节二叉树的遍历
1．二叉树遍历的概念
2．二叉树遍历递归算法
3．二叉树遍历非递归算法
4．层次遍历算法
5．线索二叉树
第六节哈夫曼树
1．哈夫曼树概述
2．哈夫曼树的构造算法
3．哈夫曼编码
本章习题要点：
二叉树的先序、中序、后序、层序遍历过程及相应的遍历算法；
第七章图（12学时）
（一）教学要求
1．掌握图的定义以及顶点的度、连通和强连通、生成树等术语；
2．掌握图的邻接矩阵、邻接链表存储，了解图的邻接多重表和十字链表存储；
3．掌握图的深度优先遍历和广度优先遍历算法；
4．掌握求最小生成树的Prim算法和Kruskal算法；
5．掌握拓扑排序算法，了解关键路径求解算法；
6．了解求最短路径的迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。
（二）教学重点与难点
教学重点：
图的数组和邻接表存储方法；图的深度和广度优先搜索算法；图的有关应用问题及算法。
教学难点：
深度优先和广度优先遍历算法；最小生成树、关键路径、最短路径的算法思想。
（三）教学内容
第一节图的基本概念
1．图的定义
2．图的基本术语
第二节图的存储结构
1．邻接矩阵存储方法
2．邻接表存储方法
第三节图的遍历
1．图的遍历的概念
2．深度优先搜索遍历
3．广度优先搜索遍历
第四节生成树和最小生成树
1．生成树的概念
2．无向图的连通分量和生成树
3．普里姆算法
4．克鲁斯卡尔算法
第五节拓扑排序
第六节最短路径
1．路径的概念
2．从一个顶点到其余各顶点的最短路径
3．每对顶点之间的最短路径
第七节AOE网与关键路径
本章习题要点：
图的深度优先遍历和广度优先遍历算法，图的应用。
第八章查找（6学时）
教学难点：
二叉排序树的插入、删除算法。
（一）教学要求
1．掌握查找的基本概念和查找方法的评判标准；
2．理解顺序查找和有序查找的算法设计方法，理解索引查找的基本结构；
3．掌握二叉排序树定义、创建、插入、删除和查找算法及查找效率分析；
4．掌握哈希函数、哈希冲突函数和哈希表的构造方法。
（二）教学重点与难点
教学重点：
顺序查找、二分查找，二叉排序树上查找以及哈希表上查找的基本思想、算法实现、效率分析。
（三）教学内容
第一节查找的基本概念
第二节线性表的查找
1．顺序查找
2．二分查找
3．索引存储结构和分块查找
第三节树表的查找
1．二叉排序树
2．平衡二叉树
第二节哈希表查找
1．哈希表的基本概念
2．哈希函数构造方法
3．哈希冲突解决方法
本章习题要点：
各种查找的实现方法。
第九章排序（10学时）
教学重点：
基本插入排序和希尔排序算法，冒泡排序和快速排序算法，简单选择排序和堆排序算法，归并排序算法，各种排序算法的时间、空间效率分析
教学难点：
多重循环希尔排序算法、快速排序算法、堆排序算法和归并排序算法
（一）教学要求
1．掌握基本的插入排序算法、改进算法（希尔排序算法）及算法效率分析；
2．掌握冒泡排序、快速排序算法及算法效率分析；
3．掌握简单选择排序、堆排序算法及算法效率分析；
4．掌握归并排序算法及算法效率分析，了解基数排序方法。
（二）教学重点与难点
教学重点：
基本插入排序和希尔排序算法，冒泡排序和快速排序算法，简单选择排序和堆排序算法，归并排序算法，各种排序算法的时间、空间效率分析
教学难点：
多重循环希尔排序算法、快速排序算法、堆排序算法和归并排序算法
（三）教学内容
第一节排序的基本概念
第二节插入排序
1．直接插入排序
2．希尔排序
第三节交换排序
1．冒泡排序
2．快速排序
第四节选择排序
1．直接选择排序
2．堆排序
第五节归并排序
第六节基数排序
本章习题要点：
各种排序的实现方法。
五、教学方法或手段
1、教学方法，采用讲授法与自学辅导式相结合的教学方法。
2、教学手段，采用多媒体教学手段。
六、考核方式及评价要求
本课程是计算机科学与技术专业基础课，以笔试方式为主进行考试，考试内容应体现教学大纲的基本要求，笔试成绩占60%，上机实验占据20%，平时成绩占据20%。
七、教材及教学主要参考书
推荐教材：
《数据结构教程》，李春葆主编，清华大学出版社，2013年6月第4版。
《数据结构》，严蔚敏主编，清华大学出版社，2012年7月第5版。
升级会员 