资源简介

(共35张PPT)
高一—教科版—信息技术—必修一第三单元
3.2 数据与结构（第2课时）
学习目标
1.了解树的概念和特征
2.了解图的概念和特征
3.掌握通过把图转化成树（枚举路径）
来解决问题的基本方法
基础知识回顾
数据结构是存在特定关系的数据元素的集合。在解决有些问题时，一些相关联的数据将集中在一起，形成一个数据的集合，这种集合能够单独或作为一个整体被访问和处理。
线性数据结构又称为线性表。在线性数据结构中，除首元素没有前趋元素、尾元素没有后继元素外，其他元素都只有一个前趋元素和一个后继元素，如图3.2.2所示。线性表中数据元素之间是一对一的关系。
基础知识回顾
典型的线性数据结构——队列
典型的线性数据结构——栈
任务二 探究快递配送过程
每个快递员只负责固定的派送范围。
快递员从快递派送点领取到快件以后，分别送到各自负责的快递领取点。
快递派送点
学校收发室
A同学
B同学
某单位传达室
职工小王
职工小李
树结构
树结构是一种具有层次关系的非线性结构。树是由n (n≥0)个节点组成的有限集合。若n= 0，则称为空树。
(1)仅有一个称为根的节点;
(2) 当n>0时，其余节点可分为m ( m≥0)个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。
树结构的两个条件
在图3.2.3中， A为唯一的根节点，B、C、D为A的子节点，同时A的子树的根节点。同理，E、F、G是B的子树的根节点，B是E、F、G的父节点。在树结构中，数据元素之间是一对多的关系。
组织架构树
快递到达目的地城市后，物流图的结构呈树状
活动2 了解城市间的物流网络
由于需要综合考虑运营成本，商品在城市间运输的路线是需要计算和规划的。请你查看图3.2.5 中的物流过程，尝试用圆圈表示城市，用线段表示城市之间的送达关系，将图3.2.6补充完整，了解商品配送的路线特点。
图3.2.5
图结构
图结构是由一组节点和一组节点间的连线(称为边或弧)构成的一种数据结构。图结构中的每个节点都可以与其他节点有边相连，图结构中数据元素之间是多对多的关系。
右图是一个图结构，其中，节点A与两条边相连，连接节点B和E；节点E与节点A、D、F相连。
网络管理系统流程图（有向图）
图片来自互联网
南京大学
理工学院地图
（带权图）
图片来自互联网
四纵四横是中华人民共和国铁道部《中长期铁路网规划（2008年调整）》 ，中国规划建设“四纵四横”客运专线，客车速度目标值达到每小时200公里以上（宜万铁路时速160公里）。 四纵四横已完美收官。
图片来自新华网
2016年7月，国家发展改革委、交通运输部、中国铁路总公司联合发布了《中长期铁路网规划》，勾画了新时期“八纵八横”高速铁路网的宏大蓝图。
图片来自互联网
活动3 规划取快递最快路线
某同学网购的书已经到达家附近的快递门店，需要他自己去取。不巧的是，这次购买的三本书是三个不同的物流公司派送的。
我们可以将该同学家和快递门店的位置抽象成顶点，两个位置间的步行线路抽象成边，边上的值表示步行时间。
家
快递门店A
2min
快递门店B
4min
快递门店C
4min
家
10min
共20min
快递门店C
6min
快递门店B
4min
家
5 min
共17min
快递门店B
5 min
快递门店A
4min
快递门店C
6min
家
10min
共25min
利用树结构，我们能够更清晰地实现不重复、不遗漏地列举所有方案，更利于通过比较得到最优解。
小结
1对1
排队
1对多
行政区域、书本目录、磁盘文件存储
多对多
地图、电话网络、互联网
谢谢观看！
3.2 数据与结构 答疑
高一—教科版—信息技术—必修一第三单元
1. 树中任意节点允许有零个或多个子节点，除根节点外，其余节点 ___ 父节点。
A. 没有
B. 有两个
C. 有且只有一个
D. 或许有一个
答案：C
2. 在树中，若节点A有4个兄弟，而且B是A的父节点，则B的有（ ）个孩子。
A．3 B．4
C．5 D．6
A
B
答案：C
3.二叉树是一种重要的树结构，他每个节点最多有两个子结点，请问只有三个节点的二叉树，共有多少种形态？
五种，具体如下图：
4. 有一树如右图所示，回答下面的问题
这棵树的根节点是________
这棵树的叶子节点是________
节点C的度是________
整棵树的度是________
树有______层
A
FGHIJ
2
3
4
5. 为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。
A．栈
B．队列
C．树
D．图
答案：B
6.如右图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距是 _______ 。
A .12 B.14 C.10 D.11
答案：D
A-B-C-F-D-E
谢谢观看！

展开更多......

收起↑