4.1树与二叉树 学案 - 浙教版2019 高中 信息技术 选修1 学案

4.1树与二叉树 导学案 学科 高中信息技术 教材版本 浙教版2019选修1 课题 4.1树与二叉树 一、【学习目标】 1.理解树和二叉树的概念和特征。（重点）（学科核心素养：信息意识、计算思维） 2.能够区别树和二叉树，并了解它们在计算机科学中的应用。（学科核心素养：信息意识、计算思维） 3.掌握树和二叉树的基本操作和遍历算法。（难点）（学科核心素养：信息意识、计算思维） 二、【自主探究】 任务一：学生自主学习课本，完成下列题目： 1.树是一种 的数据结构。是有n(n>=0)个节点的有限集合。当n=0的树称为 树， 2.树的一个节点所拥有的 个数称为该节点的度（Degree），最大的节点的度称为树的 。 3.二叉树（Binary Tree）是一个具有n（n≥0）个节点的有限集合。当n=0时，二叉树是一棵 ；当n≠0时，则是一棵由根节点和两棵互不相交的、分别称作这个根节点的 左子树和右子树组成的 ，二叉树具有一个重要的特征，就是它的所有节点的度都小于 或者等于 。 任务二：根据二叉树的第k层上最多有2^k（k≥1）个节点， （1）画仅有一个节点的二叉树 （2）画一颗高度大于3的非满二叉树 （3）画一果满二叉树 任务三：分别找出这颗树共有多少条边？树的度？树的深度？根节点，叶子节点。B节点的父节点，兄弟节点，孩子节点？ 任务四：满二叉树和完全二叉树的相同点和不同点？ 三、课后练习题 1.如下左图为一棵二叉树，其数组实现示意图(部分)如下右图所示： 下列说法正确的是( ) A.该二叉树的度为4 B.该二叉树的高度为3 C.该二叉树是完全二叉树 D.节点G存储在数组下标为11的位置 2.已知一棵完全二叉树，其第4层有3个叶子节点，这棵二叉树的节点数量不可能是( ) A. 25 B. 24 C. 11 D. 10 3. 如图所示，有如下二叉树，关于此二叉树的说法中，描述正确的是( ) A.该二叉树的前序遍历为ABDGJCEFHI B.该树中共有3个叶子节点 C.若有前序遍历和后序遍历可以推导出唯一的二叉树 D.该树的深度为4 4.已知二叉树T2的后序遍历序列为 G-D-H-E-B-I-F-C-A，中序遍历序列是 D-G-B-E-H-A-C-I-F， 则二叉树 T2 的前序遍历序列为( ) A.A-B-D-G-E-H-C-I-F B.A-B-D-G-E-H-C-F-I C.A-B-D-G-E-H-F-C-I D.该二叉树形态不唯一，无法确定 5.已知一棵二叉树的前序遍历序列为：A-B-D-C-E，后序遍历序列为：D-B-E-C-A，则该二叉树是否能唯一确定？中序遍历序列是？( ) A. 能唯一确定，中序遍历序列为：B-D-A-E-C B. 不能唯一确定，中序遍历序列可能为：B-D-A-E-C C. 能唯一确定，中序遍历序列为：D-C-B-A-E D. 不能唯一确定，中序遍历序列可能为：D-C-B-A-E 6.表达式（3+5）*4-8/2的后缀表达式为( ) A. 3 5 + 4 * - 8 2 / B. 3 5 + 4 * 8 - 2 / C. 3 5 + 4 * 8 2 - / D. 3 5 + 4 * 8 2 / - 7.某棵二叉树用数组存储后如图所示, 则节点D的左孩子节点为( ) 数组下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 数组元素 F C A D E H G B A. H B. 空 C. G D. E 8.有如图所示的二叉树。用list表示该二叉树为( ) A. [‘a’,’b’,’d’,’c’,’e’] B. [‘a’,[‘b’,[‘c’,None,None],None],[‘d’,[‘e’]]] C. [‘a’,[‘b’,[‘c’]],[‘d’,[‘e’,None,None]]] D. [‘a’,[‘b’,[‘c’,None,None]],[‘d’,[‘e’,None,None]]] 9.如图所示的二叉树用数组表示为( ) A.[‘A’,‘D’,‘F’,‘C’,‘G’,‘E’, None ,‘Q’, None ,‘K’,‘R’] B.[‘A’,‘D’,‘F’,‘C’,‘G’,‘E’, None , None ,‘Q’, None ,‘K’,‘R’] C.[‘A’,‘D’,‘F’,‘C’,‘G’,‘E’, None ,‘E’, None , None ,‘Q’,‘K’,‘R’] D. [‘A’,‘D’,‘F’,‘C’, None ,‘Q’,‘G’, None ,‘K’,‘E’,‘R’, None , None ] 10.已知某计算式的逆波兰表达式为ab+c*ab+e/-，则该计算式为( ) A.(a+b)-(c*a+b)/e B.(a+b)*c-(a+b)/e C.(a+b*c+a)/b-e D.(a+b*c)-(a+b/e) 课后练习答案 1 2 3 4 5 6 7 8 9 10 D C A B B D A D B A 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 $$