资源简介

3.2 数据与结构
第二课时
【教学目标】
一、知识与技能
1.了解树的概念和特征，特别是二叉树的概念和主要性质
2.了解图的概念和特征
3.掌握通过把图转化成树来解决问题的基本方法
二、过程与方法
1.通过探究快递配送过程，学习树结构的特点，知道树结构的概念
2.通过了解城市间的物流网络，探索图结构的特点，了解图结构的应用实例
3.规划取快递最快路线，探究树和图之间的关系，把图转化为树的作用
三、情感态度与价值观
1.该节例子与学生的日常生活密切的联系，通过对三个快递物流实例的探索，
激发学生对学习程序设计的追求和向往。
【教学重点】数据结构中的树结构和图结构。
【教学难点】二叉树的性质
【教学过程】
一、复习
复习线性数据结构——队列
二、引入
59、60 页“任务二 探究快递配送过程”之“活动 1 了解快递派送线路”，
在老师的指导下，一步一步完成第 60 页的连点成树（见下图）。引出树结构。
三、树结构
1.树结构的层次关系
2.树结构的两个条件
通过刚才的探究快递配送过程图，介绍跟节点及子树的概念
3.深入探究概念
（1）根节点
（2）以B、C、D为根节点的子树
（3）以G为根节点的子树
4.树形结构实例：
（1）组织架构树
（2）行政规划树
（3）快递公司物流配送体系
5.二叉树及其性质
作为最重要的树类型，有必要让学生了解其中几个重要性质
四、图结构
1.引入
活动2 了解城市间的物流网络，通过物流商品在城市间运输的路线，了解课
本例子中的节点之间不再是一对多的关系，而是多对多的关系。
2.图的概念
图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或弧）构成
的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数
据元素之间是多对多的关系。
子概念：顶点，边（弧）。
3.图结构实例：
（1）网络管理系统流程图（有向图）
（2）南京大学理工学院地图（带权图）
五、图结构与树结构的关系
1、规划取快递最快路线
引导学生通过枚举遍历，依次列出所有可能走法如图3.2.10。将图中每个节
点进行编号，编号互不相同：如作为根节点的“家”编号为“X”,其3个子节点
（快递门店A，快递门店B，快递门店C）分别编号为“A” “B” “C”，…，详
见下图。
六、小结
树结构和图结构，是两种比较难的数据结构。
领会树结构和图结构的本质特征，会用树结构、图结构对工作学习生活中的
具体问题进行抽象和分析，解决一些简单问题。
【练习】
1．关于二叉树的下列说法正确的是（ B）
A．二叉树的度为2 B．二叉树的度可以小于2
C．每一个节点的度都为2 D．至少有一个节点的度为2
2. 树中任意节点允许有零个或多个子节点，除根节点外，其余节点 _C__ 父
节点。
A. 没有
B. 有两个
C. 有且只有一个
D. 或许有一个
3.在树中，若节点A有4个兄弟，而且B是A的双亲，则B的度为（ C ）。
A．3 B．4
C．5 D．6
4. 只有三个节点的二叉树有多少种形态？5种
5.在下边的有向图中，从节点A到节点E的最短路径是_B_____。
A. 32
B. 34
C. 38
D. 35
6. 为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据
缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中
取出数据。该缓冲区的逻辑结构应该是( B )。
A．栈
B．队列
C．树
D．图

展开更多......

收起↑