《数据结构（本科）》课程设计方案导学方案刘鹏《数据结构（本科）》课程设计方案导学方案一、课程基本说明课程对象：全国电大系统开放教育试点计算机科学与技术专业（专科起点本科）学生课程学时：72学分课程学分：4学分开课情况：从2000年春开始，一直开设至今。

课程主讲和主编一直是清华大学殷人昆教授。

课程的基本特点：是计算机科学与技术专业的基础必修课，对学生进行基础性的、数据结构分析和算法设计能力的，为后续的操作系统、计算机网络、数据库、软件工程等课程奠定基础。

先修课程：面向对象程序设计二、课程的内容体系及教学要求第一部分有关数据结构和算法分析的基本知识教学知识点：数据逻辑结构和存储结构的定义和分类；数据类型与抽象数据类型的概念；面向对象的概念；算法的特性；算法的性能分析与度量，时间复杂度，空间复杂度，时间复杂度和空间复杂度的渐进表示法。

教学要求：理解：有关数据结构的基本概念，抽象数据类型及面向对象的概念，算法的定义及算法的特性。

应用：算法的性能分析与度量方法。

第二部分数组教学知识点：作为抽象数据类型的数组：数组类的定义和初始化，相关操作的实现。

顺序表：顺序表类的定义；顺序表的查找、插入和删除算法。

稀疏矩阵：稀疏矩阵的抽象数据类型和压缩表示。

字符串：字符串类的定义和有关操作的实现。

教学要求：理解：数组类的定义和操作实现，顺序表类的定义及操作实现，字符串类的定义及操作实现，稀疏矩阵的定义和表示。

应用：能够分析和设计带有数组类、顺序表类、字符串类的成员函数并分析其时间和空间复杂度，会把三角矩阵、对称矩阵、三对角矩阵等特殊矩阵用一维数组存储起来，并进行相应元素地址的计算。

第三部分链接表教学知识点：单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；静态链表。

循环链表：循环链表的类定义。

多项式及其相加：多项式的类定义；多项式的加法。

双向链表及其操作。

教学要求：理解：单链表、循环链表及双向链表的定义及实现，多项式类的定义及其加法运算。

应用：针对单链表的各种插入、删除等运算的算法及性能分析。

第四部分栈与队列教学知识点：栈：栈的抽象数据类型；栈类的顺序存储表示和运算；栈类的链接存储表示和运算；利用栈进行表达式的计算。

队列：队列的抽象数据类型；队列类的顺序存储表示和运算；队列类的链接存储表示和运算。

优先级队列：优先级队列的定义；优先级队列的存储表示和操作实现。

教学要求：理解：栈的定义及操作的实现，队列的定义及操作的实现，优先级队列的定义及操作的实现。

应用：表达式的各种表示法、相互转换和求值过程，按层次输出二项展开式的系数（杨辉三角形），利用栈和队列进行算法的分析和设计。

第五部分递归与广义表教学知识点：递归概念：递归的定义、递归的数据结构、递归问题的解法。

迷宫问题：递归求解思路。

递归过程与递归工作栈：递归过程实现的机制及递归工作栈的引用。

广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现。

教学要求：理解：递归的概念、递归问题的递归求解方法，递归过程的机制与利用递归工作栈实现递归的方法，广义表的定义及其存储表示。

应用：利用递归的思想进行递归求解的算法设计。

第六部分树与森林教学知识点：树和森林：树和森林的概念；树的定义和性质；树的抽象数据类型。

二叉树：二叉树的定义、性质和抽象数据类型。

二叉树的存储结构：数组表示；链表存储表示。

二叉树遍历：中序遍历、前序遍历、后序遍历、层次遍历等的方法与算法。

二叉树的其他运算的方法与算法：如建立二叉树、查找二叉树、求叶子结点数、求二叉树深度等。

堆：堆的定义；堆的建立过程；堆的插入与删除运算的算法。

树与森林：树的存储表示，森林与二叉树的转换，树的先根、后根和按层遍历方法与算法，森林的遍历方法。

霍夫曼树：霍夫曼树的概念和建立过程，霍夫曼编码。

教学要求：理解：树和森林的概念，二叉树的概念、性质及二叉树的表示，霍夫曼编码的概念，堆的概念，堆的建立方法；哈夫曼树的概念，构造哈夫曼树的过程，进行哈夫曼编码的方法。

应用：二叉树的各种遍历算法及有关其它运算的算法，树的各种遍历算法，利用二叉树的遍历结果确定二叉树的方法与过程，霍夫曼树的带权路径长度的计算。

综合应用：运用二叉树、堆的知识解决较复杂的应用问题。

第七部分集合与搜索教学知识点：集合：集合的概念，位向量表示和链表表示，对集合并、交、差等运算的算法。

搜索：搜索的概念，顺序搜索方法和算法，折半搜索的方法和算法。

二叉搜索树：二叉搜索树的定义和特性，在二叉搜索树上进行查找、插入、删除等运算的方法和递归及非递归算法。

A VL树：A VL树的定义，各种平衡化旋转的方法，在A VL树上插入和删除元素的过程。

教学要求：理解：集合的概念和表示，顺序和折半搜索的方法，在二叉搜索树上进行各种运算的过程，A VL树的构造，插入和删除元素时的调整方法及其性能分析，分析和设计对集合的各种运算的算法。

应用：基于数组的顺序搜索和折半搜索的算法分析与设计，二叉搜索树的查找、插入、删除等算法的分析与设计。

第八部分图教学知识点：图的基本概念：图的基本概念，图的抽象数据类型。

图的存储表示：图的邻接矩阵、邻接表、邻接多重表、边集数组等表示图的简单运算：如求邻接顶点，求顶点出度和入度等。

图的遍历与连通性：深度优先搜索和广度优先搜索的方法与算法，求连通分量及关节点的方法，重连通分量的概念。

最小生成树：Kruskal算法和Prim算法求图的最小生成树的过程。

最短路径：Dijkstra算法求图中一顶点到其余各顶点的过程。

活动网络：求AOV网的拓扑序列的方法和算法，求AOE网的关键路径的方法。

教学要求：理解：图的基本概念和存储表示，图的深度优先搜索和广度优先搜索的过程，求图的最小生成树、最短路径、拓扑排序、关键路径的方法和过程，求图的连通性的方法，求图的关节点及构造重连通图的方法。

应用：图的两种遍历的算法，求AOV网的拓扑排序的算法描述。

第九部分排序教学知识点：概念：排序的概念，排序的时间和空间复杂度，排序方法的稳定性。

插入排序：直接插入排序，链表插入排序，希尔排序等。

交换排序：起泡排序；快速排序。

选择排序：直接选择排序，链表选择排序，堆排序。

归并排序：两有序表合并，一躺归并，在顺序表上进行归并排序的非递归算法，在链表上进行归并排序的递归算法。

外排序：外排序的基本过程，k路平衡归并的过程和趟数计算。

基数排序：基数排序的方法。

教学要求：理解：排序的基本概念和性能分析方法，各种排序的方法和过程，它们的时和和空间复杂度分析及稳定性分析，多路平衡归并的过程。

应用：直接插入排序、直接选择排序、快速排序、堆排序、归并排序等的算法描述。

综合应用：对顺序表或链表，综合运用搜索、排序、插入、删除等运算方法解决数据处理问题的能力。

第十部分索引与散列结构教学知识点：静态索引结构：索引的概念，线性索引，倒排表，m路静态搜索树。

动态索引结构：B树的结构特点，B树的查找、插入和删除的方法。

散列：散列的概念，散列表与散列方法，散列函数，装填因子，处理冲突的闭散列方法，处理冲突的开散列方法，散列存储的性能分析。

教学要求：理解：索引与散列的概念，线性索引与B树索引的方法，散列存储的方法。

应用：B树的查找、插入和删除元素的方法与过程，散列函数的构造，解决冲突的方法，在散列表上进行查找、插入、删除元素的过程与算法描述。

三、教学媒体资源文字主教材《数据结构》殷人昆编著清华大学出版社出版实验教材《数据结构实验（本科）》徐孝凯等编中央广播电视大学出版社出版录象教材10讲殷人昆主讲中央广播电视大学音像出版社出版直播课堂4讲殷人昆主讲中央广播电视大学音像出版社出版复习资料《数据结构（本科）期末复习指导》中央电大教育杂志社出版发行作业练习《数据结构（本科）形成性考核作业册》中央电大教育杂志社出版发行网上辅导在电大在线计算机科学与技术《数据结构》课程网页上发表文字主教材是课程教学内容的最基本和最主要的载体，按照该课程教学大纲编写，是制作其他所有配套教学媒体的依据。

实验教材是学生做课程实验的依据，学生应按照要求完成每个实验，从而巩固所学的理论教学知识，提高动手能力和解决实际问题的能力。

课程教学总学时数为72学时，4学分，其中讲授学时48，实验24，教学和实验学时如下表所示。

录象教材是配合主教材的辅助教学媒体，讲授教学的基本内容，讲解根据问题进行程序设计的思路和方法，能够发挥主讲老师的讲课艺术和良好的视听教学效果，能够更好地启发和引导学生自学，帮助学生更好地掌握课程内容体系和教学要求。

录象课共10讲，每章一讲，每讲50分钟。

直播课堂给出阶段性的学习辅导和小结，帮助学生整理学习思路，解答学生在学习过程中可能遇到的共性问题。

直播课堂共4讲，每讲50分钟，前三讲为对教学重点、难点，对教学过程中反映的共性问题和有代表性的问题进行辅导，后一讲为复习辅导和有关考试说明。

各讲内容如下表所示：复习资料是学生进行期末复习的依据，给出了较丰富的课程综合练习题，能够全面提高学生掌握和运用综合知识的能力，争取能够在课程考试中取得良好成绩。

作业练习是课程形成性成绩的主要参考，通过阶段性作业练习，能够自检学习效果，看到差距和不足，督促学习。

网上辅导是教学补充媒体，有利于学生进行网上学习。

给出了一些教学辅导文章、练习题等内容。

同时在网页上还给出了教学大纲、考核说明、教师介绍等信息，有利于学生进行自主学习。

四、教学过程的组织、监督与管理中央电大按照教学计划要求，提供必要的课程教学资源供办学实体选用。

我们提倡各教学管理点，按5-8人分为若干学习小组，经常开展（至少两周一次）学习交流和讨论，互帮互助，共同进步，每个小组要有指定的专业联系教师，解答学生的问题和批改作业，必要时进行面授辅导。

五、教学安排建议面授辅导次数：15次面授辅导内容：因电视录像课较少，不能够讲解全部教学内容，所以，使用面授辅导是完全必要的，是保证教学进度、提高教学质量的有力保证，建议尽可能地安排较多的面授辅导课，最好每周能够安排一次，同时，有些应在机房连同实验一起上。

六、教学联系方式通过电子邮件方式、传真或电话联系。