3.2数据与结构（第2课时）-学案 2021-2022学年高中信息技术教科版（2019）必修1

3.2《数据与结构》（第2课时）任务单 学习目标： 1.掌握树结构的定义和特点。 2.掌握图结构的定义和特点。 3.理解队列、树、图结构的区别。 活动1.家谱中“隐藏”的数据结构 同学们对于四大名著之一的《红楼梦》并不陌生，里面主要讲述了四大家族的兴衰历程。在《红楼梦》中，主要的故事情节都是以贾家作为主线贯穿的。贾家的人物关系也是错综复杂。 但是，如果用我们所学的知识，将贾家的家谱稍作整理，立马变得清晰明确…… 思考. 《红楼梦》中贾家的人物关系显然不能用线性结构来表示，那这是一种什么数据结构呢？它具备什么特点？ 温故知新：线性数据结构 结构类型 数据节点之间的关系 生活中相应结构应用举例 栈（线性） 队列（线性） 知识点1：树结构 树结构是一种具有____________________________________________。 树是由n个节点组成的有限集合。n=0为空树。 任何一个非空树均满足以下两个条件： 1.仅有一个称为根的节点； 2.当n>0时，其余节点可分为m个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。 树结构中，数据元素之间是_____________的关系。 如上图，节点A为____________；BCD为A的子树的根节点；EFG是B子树的根节点；B是EFG的______________。 活动2 清明节旅游路线规划 清明节假期临近，小明想利用其中一天假期去几个景点旅游，由于景点分布于不同位置，为了节约时间，减少在路上时间浪费，请你帮他规划一下最优旅游路线。 思考. 下图是各景点的分布位置图，如果小明从家里出发，选择哪条路线是最佳旅游路线呢？ 1. 丽正园 1. 家 1. 嗡嗡乐园 1. 古 城 1. 浮来山 知识点2：图结构 图结构是由一组节点（称为顶点）和一组节点间的连线（称为边）构成的一种数据结构。 图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是______________的关系。 如上图，标号是1的顶点与两条边相连，顶点4与2,8,9相连。 思考. 在旅游路线图中，我们如何根据路线选择最优路径呢？ 比一比：数据结构的比较 结构类型 数据节点之间的关系 生活中相应结构应用举例 队列（线性） 树 图 上机练习：人、狼、羊、菜过河问题 有