计算机科学与技术函授本科
《 数据结构》课程教学大纲
《 数据结构》课程教学大纲
课 程 名 称：数据结构 总 学 时：102（自学：80；面授：22）
专 业：计算机科学与技术 学 分：6.0
考核方式：考 试 课程性质：基础必修课
一、课程性质和教学目标
《数据结构》课程是高校计算机科学与技术专业的一门重要的专业技术基础课程。作为软件设计技术的理论基础，《数据结构》不仅仅是计算机学科的核心课程，也是所有应用计算机的其他学科所必须掌握的课程。该课程的主要任务是讨论对各种数据组织的逻辑结构，存储结构以及有关操作的算法，并初步了解对算法的时间和空间复杂性分析。通过对本课程算法设计和上机实践的训练，宁波成人高考报名应该培养学生的数据抽象能力和程序设计的能力。
二、课程教学内容和基本要求
通过学生自学、课程面授、作业等基本环节，宁波函授专升本要求学生应达到如下要求：
1、数据结构的理解与运用能力。
2、问题求解与算法设计能力。
3、算法效率初步分析的能力。
一、绪 论
教学内容：介绍数据结构中常用的基本概念和术语及学习数据结构的意义。
教学要求：熟练掌握数据结构的一些基本术语和概念，了解抽象数据类型定义和使用，了解算法的基本概念和术语，了解算法的描述方法，掌握算法的时间复杂性分析。
二、线性表
教学内容：介绍线性表的逻辑结构和存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。
教学要求：熟练掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；了解循环链表和双向链表的定义和它的插入、删除等操作方法。
三、栈和队列
教学内容：介绍栈和队列的逻辑结构定义以及在存储结构上如何实现栈和队列的基本运算。
教学要求：熟练掌握栈和队列的定义，掌握顺序和链式存储的栈和队列的各种运算的方法及程序实现，掌握表达式求值等经典问题求解方法并了解其算法。
四、递归
教学内容：介绍程序设计中重要的算法设计方法和技术——递归，简化程序设计。
教学要求：掌握递归的定义，了解一个递归算法如何借助栈转换成一个非递归的算法，并且对一些经典问题（求阶等）会用递归技术写其算法。
五、串
教学内容：介绍串的逻辑结构、存储结构及其串上的基本运算。
教学要求：掌握串的有关概念及基本运算，掌握串的存储结构，了解串的BF算法，一般了解KMP算法。
六、数组和广义表
教学内容：介绍数据的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。
教学要求：掌握数组的逻辑结构特征及其存储方式，了解特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，了解广义表的逻辑结构和存储结构。
七、树形结构
教学内容：介绍树、二叉树等的有关概念、存储结构等方面。
教学要求：掌握树的定义、性质、存储结构，熟练掌握二叉树的定义、性质、存储结构及各种遍历算法与实现，掌握树与二叉树的转换，了解线索二叉树，了解树的遍历，了解哈夫曼树的定义，一般了解其应用，了解森林与二叉树转换等。
八、图
教学内容：介绍图的概念、两种常用的存储结构、两种遍历算法以及图的应用算法。
教学要求：掌握图的定义和术语；掌握邻接矩阵和邻接表表示法；熟练掌握图两种遍历的基本思想和算法；了解求图的最小生成树的prim和kruskal算法；了解最短路径问题和拓扑排序。
九、查找
教学内容：介绍关于线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。
教学要求：理解查找的基本概念，掌握线性表的顺序查找的思想和算法；理解二叉查找树的概念以及二叉查找树上查找的基本思想和算法；理解平衡二叉树的调整方法；理解哈希表、哈希表构造的基本方法以及处理冲突的方法；以及各种查找方法的时间性能分析。
十、排序
教学内容：介绍内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。
教学要求：排序是计算机程序设计的重要运算，是数据处理的一项基本活动。掌握内部排序方法的指导思想和特点，熟悉各种内部排序算法并理解其基本思想；了解各种内排序算法的优缺点、时间和空间的性能比较以及使用场合。
三、学时分配表
| 教学基本内容 | 学时分配 | ||
| 自学 | 面授 | 习题/讨论 | |
| 第一专题 绪论 | 4 | 5 | |
| 第二专题 线性表 | 4 | ||
| 第三专题 栈和队列 | 4 | ||
| 第四专题 递归 | 4 | ||
| 第五专题 串 | 4 | 6 | |
| 第六专题 数组和广义表 | 4 | ||
| 第七专题 树形结构 | 4 | ||
| 第八专题 图 | 4 | ||
| 第九专题 查找 | 4 | ||
| 第十专题 排序 | 4 | 5 | |
| 第十一专题 逻辑结构特征及其存储方式 | 4 | ||
| 第十二专题 广义表的逻辑结构和存储结构 | 4 | 6 | |
| 第十三专题 二叉树等的有关概念 | 4 | ||
| 第十四专题 存储结构 | 4 | ||
| 第十五专题 两种遍历算法以及图的应用算法 | 4 | ||
| 第十六专题 树和哈希表的查找方法 | 4 | ||
| 第十七专题 算法实现以及各种查找方法 | 4 | ||
| 第十八专题 内部排序方法的基本思想 | 4 | ||
| 第十九专题 排序过程 | 4 | ||
| 第二十专题 时间和空间性能 | 4 | ||
| 小 计 | 80 | 22 | |
| 总 计 | 70 | ||
