中央广播电视大学

<<数据结构>>教学大纲

第一部分大纲说明

1.课程性质、任务与目的

<<数据结构>>是计算机应用专业的一门专业基础课，主要任务是讨论各种数据结构的逻辑结构，存储结构及有关操作的算法。目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

2.与其他课程的关系

<<数据结构>>的先修课主要是<<C++语言程序设计>>，本课程将以C++作为算法描述和上机实践的工具。同时，本课程又是软件开发与设计等方面课程的基础。

3.课程特点

<<数据结构>>是实践性很强的课程,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。

4.教学要求

教学要求在每章教学内容之后给出,大体分为三个层次:了解、掌握和熟练掌握。它们的含义大致为:了解就是正确理解概念,掌握就是能够理解和分析现有知识,熟练掌握就是会运用所学知识解决实际问题。

第二部分媒体使用和教学过程建议

1.学时分配

本课程共90学时,5 学分。电视、实验、大作业各占36、27、和18学时，其余为面授。建议大作业学时可以分配到实验和面授中，不必硬性规定。电视和实验学时分配如下：

(1) 录像媒体教学36学时:

章号	内容	时数
一	绪论	2
二	线性表	5
三	栈和队列	5
四	树	5
五	图	4
六	查找	5
七	排序	5
八	文件	3
九	复习	2

(2)上机实践27学时

序号	实验内容	上机学时
1	顺序表操作	3
2	单链表操作	4
3	栈和队列的应用	4
4	二叉树的操作	4
5	图的操作	4
6	各种查找算法的比较	4
7	各种排序方法的比较	4

2.多种媒体教材的说明及教学环节

文字教材、实验教材及电视讲课均由中央广播电视大学统一提供。文字教材应系统、完整而又深入浅出，适合自学，音像教材应突出重点和难点，二者可以相互补充配合，但电视讲课仍应以文字教材为主要依据。

面授应指导和帮助学生掌握重点，突破难点，分析算法的思路与方法，指出常见的错误。上机实践，应有实验教师指导和辅导。

3.考核

本课程考核包括笔试和上机两部分。笔试由中央电大统一命题，上机考核由各地方电大组织，上机合格者方可参加笔试。

第二部分教学内容和教学要求

第一章绪论

(一) 教学内容

1.数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构、算法等。

2.抽象数据类型。

3.描述算法的程序语言。

4.算法时间复杂度和空间复杂度的分析。

(二) 教学要求

掌握数据结构的基本概念，了解抽象数据类型，了解算法时间复杂度和空间复杂度的分析，了解算法的描述方法。

第二章线性表

(一) 教学内容

1.线性表的基本概念和类型定义

2.线性表的顺序存储结构

3.线性表的链接存储结构

(1) 单链表的查找、插入和删除

(2) 循环链表

(3) 双向链表

注：建议将字符串处理作例子加入教学内容。

(二) 教学要求

了解线性表的基本概念和类型定义，熟练掌握顺序存储的线性表和单链表的算法设计及其程序实现；掌握循环链表和双向链表的操作。

第三章栈和队列

(一)教学内容

1.栈的类型定义

2.栈的顺序存储和链接存储的表示和实现

3.栈的应用举例

(1)迷宫求解

(2)表达式求值

4.队列的类型定义

5.队列的顺序存储(循环队)和链接存储的表示和实现

(二) 教学要求

掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的算法设计及其程序实现，了解栈和队的各种应用。

第四章树

(一)教学内容

1.树的定义、性质、存储结构

2.二叉树

3.二叉树的遍历和线索二叉树

4.树与二叉树的转换

(二)教学要求

掌握树的定义、性质、存储结构；熟练掌握二叉树的遍历算法及其实现；了解树和二叉树的转换。

第五章图

(一)教学内容

1.图的定义和术语

2.图的存储结构

3.图的深度和广度搜索遍历

4.拓扑排序

5.最短路径

(二)教学要求

掌握图的定义和术语；熟练掌握图的存储结构及深度和广度搜索算法及其实现；了解最短路径算法；掌握拓扑排序算法。

第六章查找

(一)教学内容

1.静态查找表

(1) 顺序查找和二分查找

(2) 分块查找和索引查找

2.动态查找

(1) 二叉排序树

(2) B树和B+树

3.哈希表

(二)教学要求

熟练掌握静态查找表的查找算法及其实现，熟练掌握二叉排序树的插入和查找算法及其实现；了解B树、B+树的各种操作；掌握哈希表的造表方法；了解各种哈希函数和处理冲突的方法。

第七章排序

(一)教学内容

1.排序的概念

2.直接插入排序

2.冒泡排序和快排序

3.直接选择排序和堆排序

4.外排序

(二)教学要求

熟练掌握简单的排序方法的算法设计及其实现；掌握快排序和堆排序算法；了解外排序方法；掌握各种排序的特点、时间复杂度和空间复杂度。

第八章文件

(一)教学内容

1.文件的基本概念

2.顺序文件

3.索引文件和索引顺序文件

4.哈希文件

5.倒排文件

(二)教学要求

掌握各种文件的组织方式和操作方法。

第四部分实验条件的要求

1.必须保证学生上机时能人手一机;

2.必须保证满足课程要求的上机时数;