教育材料《数据结构》-单元设计

《数据结构》课程教学单元设计单元一：绪论授课教师：数据结构课程组授课班级:单元总学时：2教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标设计知识目标：理解数据结构的基本概念；逻辑结构、物理结构的概念及相互关系；掌握四种基本结构的特点；掌握算法及其特性；了解算法分析的一般概念。能力目标：初步掌握什么是数据结构，数据结构的应用领域。理解逻辑结构和物理结构的概念。能理解算法与算法特性。能够进行基本的算法分析。教学内容数据结构基本概念和术语；抽象数据类型的表示与实现；算法与算法分析。重点：数据结构应用领域；算法与算法特性；四种基本结构的特点。难点：逻辑结构与物理结构的差异；算法复杂度分析。作业简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型；试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。教学过程设计数据结构基本概念（学时数：1）主要步骤教学内容教学方法教学手段师生活动知识引入数据结构概念引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解数据结构基本概念和应用；逻辑结构与物理结构；四种基本结构及其特点。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练基本数据结构分析任务；逻辑结构与物理结构分析任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践练习完成情况；实践练习存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：阅读程序代码并指出程序里使用了那些数据结构。操作演示多媒体教师：布置作业提出要求教学过程设计算法概念及特性（学时数：1）主要步骤教学内容教学方法教学手段师生活动知识引入算法应用引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解算法的特点与示例；算法的理解与复杂度；算法分析；算法实现。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练算法复杂度分析任务；算法实现任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：在程序设计中，常用下列三种不同的出错处理方式：用exit语句终止执行并报告错误；以函数的返回值区别正确返回或错误返回；设置一个整型变量的函数参数以区别正确返回或某种错误返回；试讨论这三种方法各自的优缺点。操作演示多媒体教师：布置作业提出要求

单元二：线性表授课教师：数据结构课程组授课班级:单元总学时：4教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标知识目标：理解线性表的定义及两种存储结构；理解线性表顺序存储的特点、实现方法和应用；理解顺序表的基本操作；理解链表的基本操作（包括建立链表、遍历链表、删除、插入、查找）和应用；了解双向链表、循环链表的原理和相关操作。能力目标：能用两种结构定义线性表；掌握线性表顺序存储结构特点与应用；掌握链表的特点与应用；能编程实现建立链表、遍历链表、删除、插入和查找等操作理解双向链表、循环链表原理。教学内容线性表原理；线性表的顺序表实现；线性表的链表实现；线性表应用。重点：线性表两种结构定义方法；顺序存储结构实现线性表；链式存储结构实现线性表。难点：链表操作方法包括建立链表、遍历链表、删除、插入、查找；双向链表与循环链表。作业描述以下三个概念的区别：头指针、头结点、首元结点；已知顺序表La中数据元素按非递减有序排列。试写一个算法，将元素x插到La的合适位置上，保持该表的有序性；试写一个算法，对带头结点的单链表实现就地逆置。教学过程设计线性表概念与应用（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入顺序存储结构引例；链式存储结构引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解线性表结构基本概念和应用；顺序表结构、特点与应用；顺序表实现线性表结构；链表结构、特点与应用；链表实现线性表结构；链表基本操作；其它链表结构原理与展示。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练顺序表数据结构实践任务；链表数据结构实践任务；链表应用实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。操作演示多媒体教师：布置作业提出要求

单元三：栈和队列授课教师：数据结构课程组授课班级:单元总学时：2教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标知识目标：理解栈和队列的基本概念；理解顺序栈、顺序队列的基本操作；了解在实际编程中栈和队列的不同应用；理解循环队列的概念、实现方法与循环队列判空、判满的条件；理解递归程序设计技术实现相关算法。能力目标：掌握栈和队列原理与概念；能完成顺序栈、顺序队列的基本操作；能在软件项目中合理应用栈与队列；掌握循环队列的操作与实现，能够进行循环队列判空、判满；理解递归，掌握递归程序设计方法。教学内容栈的原理与应用；顺序栈实现；队列的原理与应用；队列的实现；递归程序设计。重点：栈和队列的基本概念；顺序栈、顺序队列的基本操作；软件项目中栈与队列的应用。难点：循环队列的操作与实现，能够进行循环队列判空、判满；递归程序设计方法。作业简述栈和线性表的差别；试推导求解n阶梵塔问题至少要执行的move操作的次数；试将下列递推过程改写为递归过程；简述队列和堆栈这两种数据类型的相同点和差异处；试写一个判别表达式中开、闭括号是否配对出现的算法。教学过程设计栈和队列的概念与应用（学时数：2）主要步骤教学内容教学方法教学手段师生活动知识引入栈结构应用引例；队列结构引例；递归引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解栈与队列结构基本概念和应用；顺序栈实现；顺序栈基本操作；顺序队列实现；顺序队列基本操作；循环队列原理、实现方法与判空判满条件；递归原理与程序实现。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练栈结构实践任务；队列结构实践任务；递归实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。操作演示多媒体教师：布置作业提出要求单元四：串授课教师：数据结构课程组授课班级:单元总学时：2教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标知识目标：理解串的定义和存储方法；了解串的基本操作了解串的算法设计和应用；了解用C语言处理字符串的语法规则。能力目标：能够定义串；掌握串的存储；能够编程实现串的基本操作；能熟练应用串；熟练掌握字符串编程处理方法。教学内容串的基本理论；串的操作；字符串编程方法。重点：串的定义方法；串的存储；串的基本操作。难点：软件项目中串的使用；字符串编程处理方法。作业描述以下概念的区别：空格串与空串；设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？教学过程设计串的概念与应用（学时数：2）主要步骤教学内容教学方法教学手段师生活动知识引入串结构应用引例；串结构实现引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解串基本概念和定义；串的存储实现；串的基本操作；软件项目中串的应用；字符串原理与概念；字符串通用编程处理方法。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练串结构实践任务；字符串实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：已知：s＝“（xyz）＋＊”，t＝“（x＋z）＊y”。试利用联结、求子串和置换等基本运算，将s转化为t。操作演示多媒体教师：布置作业提出要求

单元五：数组和广义表授课教师：数据结构课程组授课班级:单元总学时：4教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标知识目标：了解数组的存储结构；了解特殊矩阵进行压缩存储的下标转换公式；理解稀疏矩阵的压缩存储原理；了解利用三元数组表示稀疏矩阵的方法；了解广义表的概念和存储结构。能力目标：掌握数组存储结构；能够在软件项目中合理选择和使用数组能够编程实现特殊矩阵压缩存储；掌握稀疏矩阵的压缩存储原理；能用三元数组表示稀疏矩阵；掌握广义表概念与存储结构。教学内容数组的概念；数组存储结构与方法；广义表概念；数组与广义表的编程应用。重点：数组存储结构；数组的实际应用；三元数组表示稀疏矩阵。难点：实现特殊矩阵压缩存储；稀疏矩阵的压缩存储原理；广义表概念与存储结构。作业已知多维数组A[2][2][3][3]按行优先方式存储。试按存储位置的先后次序，列出所有数组元素A[i][j][k][l]序列（为了简化表达，可以只列出形如“i,j,k,l”的序列，如元素A[0][0][2][1]可表示为“0,0,2,1”）。假设有一个二维数组A[0..5][0..7]，每个元素占6个字节，首元素A[0][0]的地址为1000，求A的体积与最后一个元素A[5][7]的地址。教学过程设计数组与广义表的概念和应用（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入数组结构应用引例；矩阵压缩引例；广义表引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解数组结构基本概念；数组的实际应用；矩阵压缩存储原理；矩阵压缩存储实现；稀疏矩阵表示方法；稀疏矩阵应用；广义表概念。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练数组应用实践任务；矩阵压缩存储实践任务；稀疏矩阵实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出计算矩阵相加C＝A＋B的算法，其中，C是另设的、存放结果的三元组表（提示：可用类似于两个有序顺序表归并的处理方法）。操作演示多媒体教师：布置作业提出要求

单元六：树授课教师：数据结构课程组授课班级:单元总学时：6教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标知识目标：了解树和二叉树的定义；掌握二叉树的基本性质，能利用相关性质解决简单计算问题；了解二叉树的顺序存储结构；掌握二叉树的链式存储结构、相关操作；掌握二叉树的有关算法并能编程实现；掌握利用遍历构造二叉树的规则和具体步骤；掌握哈夫曼树的定义、性质和构造方法；了解哈夫曼树的应用。能力目标：掌握二叉树的定义与基本性质；能利用二叉树解决简单计算问题；能用顺序存储结构编程实现二叉树；能用链式存储结构编程实现二叉树；能在软件项目中合理使用二叉树；掌握二叉树遍历方法；能以遍历方式构造二叉树；掌握哈夫曼树的定义与构造。教学内容树的概念；二叉树的定义；二叉树的存储结构；二叉树遍历理论；二叉树编程实现；二叉树构造；哈夫曼树的概念和应用。重点：二叉树的定义与基本性质；二叉树的顺序存储结构；二叉树的链式存储结构；二叉树操作。难点：遍历二叉树；构造二叉树；哈夫曼树的定义与构造。作业试分别绘出具有3个结点的树和3个结点的二叉树的所有不同形态；设结点X是二叉树上一个度为1的结点，X有几个子树；已知某二叉树的中序序列为DCBGEAHFIJK，后序序列为DCEGBFHKJIA。请画出该二叉树。教学过程设计树的概念与性质（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入树的遍历引例；哈夫曼树引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解树结构基本概念；树的性质与实际应用示例；二叉树的概念；二叉树的遍历；二叉树的存储结构。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练树的应用实践任务；二叉树的遍历实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践任务完成情况；实践任务存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：描述满足下列条件的二叉树形态：先序遍历序列与中序遍历序列相同；后序遍历序列与中序遍历序列相同；先序遍历序列与后序遍历序列相同。操作演示多媒体教师：布置作业提出要求教学过程设计树的应用（学时数：2）主要步骤教学内容教学方法教学手段师生活动知识引入树结构应用引例；哈夫曼树引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解树的顺序表存储方法；树的链表存储方法；树的构造方法；树的遍历方法；哈夫曼树的原理与应用示例。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练二叉树的顺序表存储实践任务；二叉树的链表存储实践任务；二叉树的遍历实践任务；树的构造与应用实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：试编写算法，实现将二叉树所有结点的左右子树互换。操作演示多媒体教师：布置作业提出要求

单元七：图授课教师：数据结构课程组授课班级:单元总学时：6教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标知识目标：了解图的基本概念掌握图的存储方法（邻接矩阵、邻接表）掌握图的深度优先和广度优先遍历的规则和步骤理解在连通图中求最小生成树的方法。了解求图的最短路径等相关算法及其应用能力目标：掌握图的概念；能利用邻接矩阵存储图结构；能用邻接表存储图结构；能用深度优先方式遍历图；能用广度优先方式遍历图；能在连通图中求最小生成树；会求图的最短路径；能在软件项目中合理使用图结构。教学内容图的概念；图结构在编程中的应用；图的遍历规则；图的基本算法；编程实现图结构。重点：图的定义与基本性质；图的邻接矩阵存储结构；图的邻接表存储结构；图的遍历。难点：求图的最短路径；最小生成树。作业已知有向图，给出该图的：邻接矩阵示意图；邻接表示意图；逆邻接表；所有强连通分量；已知图G的邻接矩阵，写出该图从顶点1出发的深度优先搜索序列和广度优先搜索序列，并画出相应的深度优先生成树和广度优先生成树；已知有向图，试写出其所有可能的拓扑序列。教学过程设计图的基本概念（学时数：2）主要步骤教学内容教学方法教学手段师生活动知识引入图应用引例；最短路径应用引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解图结构基本概念；图的性质与实际应用示例；求最短路径方法；连通图最小生成树。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练图的遍历实践任务；最小生成树实践任务；最短路径实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践练习完成情况；实践练习存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：已知无向带权图，(1)画出它的邻接矩阵，并按Prim算法求其最小生成树；画出它的邻接表，并按Kruskal算法求其最小生成树。操作演示多媒体教师：布置作业提出要求教学过程设计图的应用（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入图遍历引例；最短路径应用引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解图的邻接矩阵存储方法；图的邻接表表存储方法；图的遍历方法；求最短路径方法；连通图最小生成树。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练图的存储实践任务；图的遍历实践任务；最小生成树实践任务；最短路径实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：以邻接表作为存储结构，实现求单源最短路径的Dijkstra算法。操作演示多媒体教师：布置作业提出要求

单元八：查找授课教师：数据结构课程组授课班级:单元总学时：6教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标知识目标：了解查找的相关概念；掌握顺序表的查找方法、步骤、程序实现、时间复杂度和平均查找长度；掌握在有序的顺序表上进行折半查找的方法、步骤、程序实现；掌握折半查找的判定树的构造方法；掌握二叉排序树的确切定义；掌握建立二叉排序树的步骤和方法；理解在二叉排序树中进行输入、删除操作的规则；了解哈希表的相关概念和原理；了解常用哈希函数的构造和处理冲突的方法。掌握哈希函数和哈希表的关系及在查找中的应用。能力目标：能完成顺序表查找并能分析时间复杂度；能编程实现折半查找；能掌握折半查找判定树的构造；掌握二叉排序树的定义；能建立二叉排序树；能实现对二叉排序树的输入和删除；掌握哈希表的概念与原理；掌握哈希函数的构造与冲突处理方法；能在软件项目中熟练使用各种查找算法。教学内容查找的概念；查找的时间复杂度计算；折半查找原理与实现；二叉排序树概念；二叉排序树的创建与操作；哈希表概念；哈希表构造与冲突处理；哈希表在查找中的应用。重点：顺序表查找；折半查找方法；建立二叉排序树；索引查找方法；哈希表的概念。难点：二叉排序树的输入与删除；哈希函数的构造与冲突处理方法；哈希函数和哈希表的关系及在查找中的应用。作业对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗；用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?如果要求时间复杂度更小,你采用什么方法，此方法的时间复杂度是多少；画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度；选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。教学过程设计查找概念与常用查找算法（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入查找应用引例；哈希表应用引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解顺序表查找方法；查找时间复杂度分析；顺序表折半查找方法；哈希表的概念与原理；哈希函数的构造与冲突处理；启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练顺序表查找分析任务；顺序表折半查找分析任务；二叉排序树操作分析任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践练习完成情况；实践练习存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：试分别写出在对有序线性表(a,b,c,d,e,f,g)中进行折半查找，查值等于e、f和g的元素时，先后与哪些元素进行了比较。操作演示多媒体教师：布置作业提出要求教学过程设计查找算法实现（学时数：2）主要步骤教学内容教学方法教学手段师生活动知识引入查找实现引例；哈希表实现引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解顺序表折半查找方法；折半查找判定树构造方法；二叉排序树的定义与建立；哈希函数的构造与冲突处理；哈希函数与哈希表的关系及其在查找中的应用。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练顺序表查找实践任务；顺序表折半查找实践任务；建立二叉排序树实践任务；二叉排序树操作实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：已知如下所示长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。操作演示多媒体教师：布置作业提出要求

单元九：排序授课教师：数据结构课程组授课班级:单元总学时：6教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标知识目标：理解各种排序算法的基本原理、步骤；理解各种排序算法的规则；能正确理解相关排序算法的程序实例，并重点掌握算法中的关键步骤和关键语句；理解堆和特殊的完全二叉树的对应关系；掌握建堆、“筛选”完全二叉树相关操作的方法。能力目标：掌握各种排序算法的基本原理、步骤；掌握相关排序算法的规则人工完成排序；能通过分析排序的中间结果判断所用的排序算法；能正确编写排序算法的程序实例，并理解算法中的关键步骤和关键语句；掌握堆和特殊的完全二叉树的对应关系；掌握建堆和完全二叉树相关操作；能在软件项目中正确选择和应用排序算法。教学内容排序概念；排序复杂度判断；基本排序规则；排序算法实现；堆的概念；堆与完全二叉树；创建堆与操作完全二叉树。重点：各种排序算法；堆和特殊的完全二叉树；建堆操作；排序方法的比较。难点：深入理解排序算法；根据排序算法人工排序并能从中间步骤推断排序算法；筛选算法和完全二叉树操作。作业以关键字序列（5，1，6，0，9，2，8，3，7，4）为例，手工执行下列排序算法，写出每一趟排序结束时关键字序列状态：直接插入排序；希尔排序（取增量为5，3，1）；快速排序；冒泡排序；归并排序；堆排序；上题中哪些排序方法是稳定的，哪些是不稳定的？并为每种不稳定的排序方法举一个不稳定的实例；试以单链表为存储结构，实现简单选择排序算法。教学过程设计排序基本概念与常用算法（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入排序应用引例；堆应用引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解插入排序方法；交换排序方法；选择排序方法；归并排序方法；排序方法的比较与复杂度分析；堆的概念与原理；堆与完全二叉树。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练插入排序分析任务；交换排序分析任务；选择排序分析任务；归并排序分析任务；完全二叉树操作分析任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践练习完成情况；实践练习存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：判别以下序列是否为堆（小顶堆或大顶堆），若不是，则吧它调整为堆：(96,86,48,73,35,39,42,57,66,21)；(12,70,33,65,24,56,48,92,86,33)。操作演示多媒体教师：布置作业提出要求教学过程设计排序算法应用（学时数：2）主要步骤教学内容教学方法教学手段师生活动知识引入排序算法实现引例；堆实现引例。引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解插入排序实现；交换排序实现；选择排序实现；归并排序实现；筛选完全二叉树。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练插入排序实践任务；交换排序实践任务；选择排序实践任务；归并排序实践任务；完全二叉树操作实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。操作演示多媒体教师：布置作业提出要求

单元十：文件授课教师：数据结构课程组授课班级:单元总学时：2教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件、授课录像教学目标知识目标：了解文件概念；了解顺序文件操作方法；了解索引文件操作方法；掌握各类文件的数据读写方法；了解多关键字文件。能力目标：掌握文件概念；能读写顺序文件数据；能读写索引文件数据；掌握多关键字文件；能利用文件存储和读取程序中的数据。教学内容文件基本概念；顺序文件操作；随机文件操作；文件数据读写；多关键字文件概念。重点：顺序文件概念；索引文件概念；各类文件数据读写操作。难点：多关键字文件概念；多关键字文件操作。作业什么是索引顺序文件；试比较顺序文件，索引非顺序文件，索引顺序文件，散列文件的存储代价，检索，插入，删除记录时的优点和缺点。教学过程设计文件概念与应用（学时数：2）主要步骤教学内容教学方法教学手段师生活动知识引入文件应用引例引例演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解顺序文件概念；顺序文件读写方法；索引文件概念；索引文件读写方法；多关键字文件概念；多关键字文件示例。启发讲解操作演示分组讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练顺序文件读写实践任务；索引文件读写实践任务。讲练结合一体化学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结引导创新作业布置拓展练习：利用文件存放全班学生所有科目的期末考试成绩，并能随机读取数据。操作演示多媒体教师：布置作业提出要求

模块一：了解C开发环境授课教师：数据结构课程组授课班级:单元总学时：4教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件教学目标知识目标：掌握C语言程序开发过程；掌握TurboC和VC++的编程环境；了解算法的评价标准。能力目标：能够使用TurboC及JDK6.0开发环境；能够编写简单的C程序；能够进行简单的算法评价。教学内容使用TurboC开发简单的C程序；使用JDK6.0开发控制台类型的简单C程序。重点：开发环境的使用及C程序开发过程。难点：算法的评价标准。作业简单算法设计的练习。教学过程设计任务1使用TurboC开发简单的C程序（学时数：2）主要步骤教学内容教学方法教学手段师生活动知识引入系统演示。系统演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解C语言开发过程；系统开发环境；算法的分析设计思路；流程图的表示方法；算法的评价标准。启发讲解操作演示课堂讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练算法设计及程序实现。讲练结合一体化独立开发多媒体软件演示学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结任务布置思考：怎样评价算法的优劣。启发思考多媒体教师：布置任务教学过程设计任务2使用JDK6.0开发控制台类型的简单C程序（学时数：2）主要步骤教学内容教学方法教学手段师生活动知识引入系统演示。系统演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解JDK6.0开发环境；算法的评价标准。启发讲解操作演示课堂讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论整理笔记实践训练算法设计及程序实现。讲练结合一体化独立开发多媒体软件演示学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结任务布置思考：怎样评价算法的优劣。启发思考多媒体教师：布置任务

模块二：求出约瑟夫环的出列——链表应用授课教师：数据结构课程组授课班级:单元总学时：4教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件教学目标知识目标：熟练定义并实现链表；熟练使用链表常用操作。能力目标：能够定义并实现链表；能够实现链表常用操作。教学内容链表建立、初始化；链表的操作；根据用户输入的值得出符合条件的序列。重点：链表的基本算法实现。难点：链表与顺序表的区别。作业链表的应用练习。教学过程设计任务1链表建立、初始化及操作（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入系统演示。系统演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解线性表的链式存储结构；链式存储结构的常用操作；约瑟夫环出列的算法分析；算法实现及评价。启发讲解图示讲解操作演示课堂讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论实践训练算法设计及程序实现。讲练结合一体化独立开发多媒体软件演示学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结任务布置总结链式存储结构和顺序存储结构的区别。启发思考多媒体教师：布置任务

模块三：模拟手机短信功能——队列应用授课教师：数据结构课程组授课班级:单元总学时：4教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件教学目标知识目标：掌握队列的定义；熟练掌握队列的实现；熟练掌握的队列常用操作。能力目标：能够定义并实现队列；能够实现队列常用操作。教学内容设计链式存储结构的队列；队列的操作。重点：队列的基本算法实现。难点：队列的应用算法实现。作业队列应用的练习。教学过程设计任务1链式队列的操作（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入系统演示。系统演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解队列的定义；队列的操作特点；队列的存储结构（顺序存储、链式存储）；队列的应用；算法实现及评价。启发讲解图示讲解操作演示课堂讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论实践训练算法设计及程序实现。讲练结合一体化独立开发多媒体软件演示学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结任务布置总结队列的不同应用。启发思考多媒体教师：布置任务

模块四：文本编辑——字符串处理授课教师：数据结构课程组授课班级:单元总学时：4教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件教学目标知识目标：掌握控制台应用程序菜单的实现掌握使用串的常用操作；熟练掌握串的查询。能力目标：能够定义并实现串；能够使用串的各种函数。教学内容文本的输入、查找；文本的修改、删除；文本的输出。重点：串类型的定义。难点：串的表示和实现。作业字符串的应用练习。教学过程设计任务1文本编辑（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入系统演示。系统演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解串的基本概念；串的存储结构；串的基本运算及其实现；文本编辑；算法实现及评价。启发讲解图示讲解操作演示课堂讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论实践训练算法设计及程序实现。讲练结合一体化独立开发多媒体软件演示学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结任务布置总结串的不同应用。启发思考多媒体教师：布置任务

模块五：学生成绩信息管理系统——结构体与程序逻辑授课教师：数据结构课程组授课班级:单元总学时：4教学条件实训室、JDK6.0、投影设备、广播软件、互联网络教学素材参考教材、教学课件教学目标知识目标：掌握控制台应用程序多级菜单的实现；掌握结构体变量的定义和使用方法；掌握串的链式存储结构；掌握文件的读写操作；掌握结构化程序设计方法。能力目标：能够实现控制台应用程序多级菜单；能够使用结构体处理数据；能够灵活运用串的链式存储结构进行数据操作；能够进行文件的读写操作。教学内容设计学生成绩信息管理系统的图形界面；学生基本信息的输入、修改、删除、查询；学生成绩的输入、修改、删除、查询。重点：串类型的定义。难点：利用串的链式存储结构，对学生的各项记录动态的存储。作业结构体的应用练习。教学过程设计任务1结构体与程序逻辑（学时数：4）主要步骤教学内容教学方法教学手段师生活动知识引入系统演示。系统演示启发引入多媒体软件演示教师：操作演示学生：观察思考知识讲解串的存储结构；串的基本运算及其实现；控制台应用程序多级菜单的实现；串的动态存储；算法实现及评价。启发讲解图示讲解操作演示课堂讨论多媒体软件演示教师：启发讲授操作演示学生：交流互动分组讨论实践训练算法设计及程序实现。讲练结合一体化独立开发多媒体软件演示学生：实践操作教师：巡视指导归纳总结实践训练完成情况；实践训练存在的问题；知识要点。汇报展示师生点评归纳总结多媒体学生：汇报展示集体点评教师：组织总结任务布置总结串的不同应用。启发思考多媒体教师：布置任务

模块六：求二叉树上结点的路径的应用——二叉树的