高效作业13 第13课 树与二叉树-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

高效作业13[第13课　树与二叉树](见学生用书P221) 学科网（北京）股份有限公司 【A级　新教材落实与巩固】 1．在流行病学的溯源调查中，要表示某个传染源下所有患者的传染关系，比较合适的数据组织形式是(　D　) A．数组　　B．栈　　C．队列　　D．树 【解析】 某个传染源下所有患者的传染关系是分层级的，要表示这种关系，比较合适的是用树的形式，选项D正确。 2． 树可以构造出不同的结构形态，以下形态不属于树状结构的是(　C　) A．　　　　B．　　　　C．　　　　D． 【解析】 根据树的定义以及相关性质可知，n个节点的树通过n－1条边相连接，选项C，节点数为2，边数也为2，与树的定义和性质不符，选项错误。 3．2023·杭二中检测下列有关数据结构的说法中，正确的是(　B　) A．数组是一种适合用于组织、存储涉及频繁插入与删除的数据结构 B．链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的 C．链表在访问、插入和删除元素时，算法效率比数组高 D．树结构中，每个子节点的可以有多个父节点 【解析】 选项A，数组不适合用于组织、存储涉及频繁插入与删除的数据结构，选项错误；选项C，链表在插入和删除元素时，算法效率比数组高，链表的访问效率低于数组，选项错误；选项D，树结构中，每个子节点的父节点只能有1个，选项错误。 4． 下列关于二叉树的高度和树中可以容纳的节点数之间的关系说法中，正确的是(　C　) A．非空二叉树的第1层上的节点个数为2 B．二叉树的第10层上的节点个数为256 C．深度为10的二叉树最多有1023个节点 D．一个具有1025个节点的二叉树的深度为11 【解析】 根据二叉树的性质可知，树中节点的层数从根开始计算，非空二叉树第一层上的节点个数为1；第10层上的节点个数最多为210－1＝512，节点个数范围是1～512；深度为10的二叉树最多有210－1＝1023个节点；具有1025个节点的二叉树的深度范围为11～1025，选项C正确。 5．下列关于树的根节点说法中，正确的是(　A　) A．树的根节点没有前驱 B．树的根节点没有后继 C．树的根节点层数为0 D．树的根节点是所有树节点的父节点 【解析】 树形结构中的根节点没有前驱节点、只有后继节点，根的层数为1，与边直接相连的上端节点是父节点，选项A正确。 6．下列关于二叉树的说法中，正确的是(　D　) A．空树不属于二叉树 B．二叉树的根节点的孩子节点个数一定是2 C．二叉树中除了叶子节点，其他所有节点的度数均为2 D．二叉树中所有节点的度一定小于或者等于2 【解析】 二叉树是n个节点的有限集合，当n＝0时，二叉树是一棵空树，二叉树的一个重要特征是它的所有节点的度都小于或者等于2，选项D正确。 7．“猜数字”游戏是从一个数据范围内猜出指定数的游戏。具体的猜数过程可以抽象为一棵二叉树，如图所示，这是在1～10之间的猜数字游戏对应的二叉树，下列说法正确的是(　A　) A．4次以内肯定能猜中对应的数字 B．猜数对应的二叉树有3个叶子节点 C．游戏对应的二叉树是完全二叉树 D．从对应的二叉树可知，猜中一个数至少需要猜2次 【解析】 因为1～10之间的“猜数字游戏”对应的二叉树的深度为4，所以4次以内肯定能猜对结果；度为0的节点称为叶子节点，所以该二叉树的叶子节点数为4。由于二叉树最下面一层不满，且缺少的节点不靠在一边，不是完全二叉树；猜中一个数可能最少1次就可以，如“5”，选项A正确。 8．2023·龙游中学检测观察如图所示的二叉树示意图，下列说法正确的是(　C　) A．这是一棵完全二叉树 B．这棵二叉树的叶子节点数为3 C．这棵二叉树的深度是4 D．这棵二叉树的度为4 【解析】 完全二叉树的最下面一层叶子节点都依次排列在该层的最左边位置，题目中最后一层的节点不在最左边位置，叶子节点为3，5，11，4，9共有5个，该二叉树的度为2，选项C正确。 9．深度为5的二叉树的节点个数最多为(　C　) A．16 B．32 C．31 D．10 【解析】 根据二叉树的性质，深度为k的二叉树最多有2k－1个节点，故深度为5的二叉树最多有31个节点，选项C正确。 10．下列关于二叉树的说法中，正确的是(　A　) A．只有一个节点的二叉树的度为0 B．二叉树的度为2 C．二叉树的左右子树可任意交换 D．完全二叉树的所有节点的度均为2 【解析】 节点所拥有的子树个数称为该节点的度，只有一个节点的二叉树的度为0，二叉树的度小于等于2，完全二叉树最下面两层的节点度数小于2，二叉树的左右子树交换会改变数据的层次关系，选项A正确。 11．若一棵二叉树具有10个叶子节点，则树形结构中度为2的节点个数为(　B　) A．8 B．9 C．10 D．11 【解析】 根据二叉树的性质可知，任意一棵二叉树中，若度为2，节点数量为n2，叶子节点数为n0，则n0＝n2＋1，故题目中度为2的节点数是9个，选项B正确。 12．若一棵二叉树具有10个度为2的节点和5个度为1的节点，则该树形结构的总边数是(　B　) A．14 B．25 C．23 D．不能确定 【解析】 根据题目已知度为2的节点为10个，则叶子节点为11个，所以总的节点数为10＋5＋11＝26。在二叉树的所有节点中，除了根节点没有前驱外，每个节点均有且只有一个前驱节点，因此26个节点的二叉树的总边数为25条，选项B正确。 【B级　素养形成与评价】 13．若一棵二叉树共有10个节点，其中4个是叶子节点，则度为1的节点数量为(　A　) A．3 B．4 C．5 D．6 【解析】 二叉树的所有节点的度都小于或者等于2，题目中已知叶子节点数为4，则度为2的节点数是4－1＝3，因此度为1的节点数是10－4－3＝3，选项A正确。 14．将一棵有1000个节点的完全二叉树按照从上到下、从左到右的顺序依次进行编号，根节点的编号为1，则编号为35的节点的右孩子编号为(　D　) A．36 B．70 C．72 D．71 【解析】 在一棵完全二叉树中，若父节点的编号为n，则它的左孩子编号为2×n，右孩子的编号为2×n＋1，则编号为35的节点的右孩子编号为71，选项D正确。 15．如图所示，一个数学表达式可以用一棵表达式树来表示。关于该表达式的树，说法不正确的是(　C　) A．该表达式树不是完全二叉树 B．若表达式树中只有四则运算，则对应的表达式树的每个节点都有两个子节点 C．表达式树的根节点左右子树深度差不会超过1 D．该表达式树对应的表达式为“(3＋4)*6－8＋4/(3*2)” 【解析】 表达式树根节点左右子节点的深度差可以超过1，*节点的左、右子树深度分别为3和1，选项C错误。 16．2023·黄岩中学检测猜数游戏。计算机程序从1～31中随机产生一个数字，玩家可以随机猜测一个数字，根据玩家猜测的数字，计算机会给出“太大”“太小”或“正确”的提示，玩家由此提示修改自己的猜测，直到猜中为止。为了尽快地猜出随机数是多少，小明绘制了如图所示的二叉树： 按照该二叉树规律玩猜数游戏，则其最少和最多的猜测次数分别为(　B　) A．1和31 B．1和5 C．5和31 D．5和32 【解析】 由图中的二叉树可知树的深度为5，因此猜测的最多次数是5，猜测16则一次会猜中，因此最少的猜测次数是1，选项B正确。 17．一棵度为 3、深度为 4的树，其节点个数最多为(　C　) A．31 B．32 C．40 D．42 【解析】 第1层数量为1；第2层数量为3；第3层数量为9；第4层数量为27，总共有40个，选项C正确。 18．已知一棵完全二叉树，其第4层有3个叶子节点，这棵二叉树的节点数量不可能是(　C　) A．25 B．24 C．11 D．10 【解析】 如果总共4层，则前3层满，前3层节点数为：23－1＝7，7＋3＝10，节点为11个不可能，选项D不符合题意，选项C符合题意；如果是5层，则前4层点数为：24－1＝15，第4层节点数为2(4－1)＝8，有3个叶子节点，另外5个是第5层的父节点，第5层可以有10或9个节点，选项A、B不符合题意。 19． 2023·东海中学检测一棵包含10个节点的完全二叉树，其叶子节点的个数为(　C　) A． 3 B． 4 C． 5 D．6 【解析】 n0＋n1＋n2＝10，n0＝n2＋1，由于是完全二叉树，n1＝0或1。若n1＝1，则推出n2＝4，n0＝5；若n1＝0，则不成立，选项C正确。 20． 有如图所示的二叉树，圈中数字表示叶子节点的权，则该二叉树的带权路径长度WPL为(　C　) A．23 B．29 C．44 D．67 【解析】 本题主要考查的是二叉树的带权路径长度WPL的计算。WPL＝9×1＋7×2＋(5＋2)×3＝44，选项C正确。 21．2023·春晖中学检测树的表达方式有很多种，可以采用如下简便的方法：若在树中，节点x是节点y的父节点时，可以用(x，y)来表示．已知一棵树用这种方式表示的集合为{(E，K)，(E，L)，(B，E)，(B，F)，(A，B)，(C，G)，(C，H)，(A，C)}。 (1)__A__是根节点，它的孩子节点是__BC__。 (2)节点C的父节点是__A__，兄弟节点是__B__，孩子节点是__GH__。 (3)节点A 的度是__2__，节点F的度是__0__，整棵树的度为__2__。 (4)节点F的层数是__3__，树的深度是__4__，叶子节点的数量是__5__。 【解析】 尝试绘制出题目中的树形结构图，如图所示。根据树的概念及特性得出答案。 学科网（北京）股份有限公司 $$