2023—2024学年高中信息技术浙教版（2019）选修1 第四章树同步作业

第四章树同步作业2023—2024学年高中信息技术浙教版（2019）选修1 1．用数组表示二叉树的示意图如下所示：（    ） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 B D A E F C 下列说法正确的是（    ） A．该二叉树的深度为3 B．该二叉树是完全二叉树 C．该二叉树有4个叶子节点 D．该二叉树后序遍历的结果为DCEFAB 2．二叉树的每个节点最多有（   ）个子节点。 A．0 B．1 C．2 D．无限 3．某二叉树从根节点开始，按从上到下、自左往右的顺序用A-G字母表示，若补全为完全二叉树后，用一维数组表示如图所示。 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 下列关于该二叉树的说法，正确的是（   ） A．该二叉树的深度为3 B．节点E的父节点是B C．该二叉树的中序遍历结果为BFDGACE D．该二叉树的叶子节点为D、E、F、G 4．队列的删除操作是在（   ） A．队首 B．队尾 C．队列中间位置 D．任意位置 5．某二叉树如图所示，下列说法正确的是（    ） A．节点D、F都是节点B的孩子节点 B．该树的度和深度分别为2和3 C．该二叉树中序遍历的结果为DBEAGCF D．若补全成高度为5的满二叉树则需增加24个节点 6．有如图所示的树。下列说法正确的是（   ） A．该树中共有3个叶子节点 B．该树的度和深度均为3 C．该树中度为2的子节点有1个，度为1的子节点有2个 D．节点e是节点f的兄弟节点 7．已知某二叉树的后序遍历为GDBEHFCA，中序遍历为DGBAECHF，下列说法正确的是（    ） A．该二叉树中叶子节点有3个 B．该二叉树的前序遍历为ABDGCEHF C．该二叉树是一棵完全二叉树，树的高度为4 D．该二叉树中度为1的节点有2个 8．已知一棵二叉树的前序遍历序列为：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 9．某二叉树的树形结构如图所示，其后序遍历结果为FABGDEC，则中序遍历结果为（    ） A．FDAGBCE B．FDABGEC C．AGBDFCE D．FDAGBEC 10．已知一棵二叉树如图所示，则下列说法正确的是（   ） A．该二叉树的后序遍历为DEGBFCA B．该树中度为2 的节点只有1个 C．若补全成高度为4的满二叉树则需增加8个节点 D．删除节点G后，该树成为一棵完全二叉树 11．运行图1所示的VB程序，出现了图2所示错误。若要纠正程序中的错误，以下叙述正确的是（    ）。 A．将变量i的数据类型改为Double B．将变量s的数据类型改为Double C．将变量s的数据类型改为String D．将变量i的数据类型改为String 12．已知一棵具有9个节点的二叉树的中序遍历序列为7%4*2+3/2，后序遍历序列为74%2*32/+，以下说法不正确的是（    ） A．用数组表示该树，叶子节点的最小下标是4 B．这是一棵完全二叉树 C．其前序遍历序列为+*7%42/32 D．这棵树叶子结点比非叶子结点数多1 13．一棵包含10个节点的完全二叉树，其叶子节点的个数为（　　） A．3 B．4 C．5 D．6 14．如图所示的二叉树，其节点的中序遍历的序列为（  ） A．ABCDEFG B．GDBEACF C．GDEBFCA D．ABDGECF 15．在算法分析中，大O符号(O-notation)主要用来描述算法的（   ） A．最好情况执行时间 B．平均情况执行时间 C．最坏情况执行时间 D．空间使用量 16．如图，下列关于该二叉树的说法正确的是（   ） A．该二叉树为完全二叉树 B．该二叉树的度为5，深度为4 C．该二叉树中，E和D都是F的兄弟节点 D．该二叉树的前序遍历为ABEGCFD 17．一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树的深度为（    ） A．6 B．5 C．4 D．3 18．一棵度为3，深度为4的树，最多有（     ）个节点。 A．31 B．32 C．40 D．42 19．下列二叉树中，中序遍历结果为BAEDFC的是（   ） A． B． C． D． 20．二叉树的遍历方式不包括以下哪一种（   ） A．前序遍历 B．中序遍历 C．后序遍历 D．逆序遍历 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题考查的是二叉树。依据题意可知二叉树为： 故其深度为4；不是完全二叉树；该二叉树有3个叶子节点；该二叉树后序遍历的结果为DCEFAB。故选D。 2．C 【详解】本题考查的是二叉树相关知识。二叉树的每个节点最多可以有两个子节点，分别称为左子节点和右子节点。故选C。 3．C 【详解】本题主要考查二叉树。该二叉树如下，由图可知，该二叉树的深度为4；节点E的父节点是C；该二叉树的中序遍历结果为BFDGACE；该二叉树的叶子节点为E、F、G，故本题选C选项。    4．A 【详解】本题主要考查队列数据类型。队列是从队尾入队，从队首出队（即删除操作），故本题选A选项。 5．D 【详解】本题考查数据结构二叉树相关内容。A选项，节点D是节点B的孩子节点，节点F是节点C的孩子节点，选项错误。B选项，该树的度和深度分别为2和4，选项错误。C选项，该二叉树中序遍历的结果为DBEGACF，选项错误。D选项，高度为5的满二叉树节点总数为：25-1=31，则需增加24个节点（31-7），选项正确。故本题答案是D选项。 6．C 【详解】本题考查树。该树中共有4个叶子节点，分别是h、e、f、g，因此A选项错误；该树的度为3，深度为4，因此B选项错误；由于节点e和节点f的父节点不是同一个，因此它们不是兄弟节点，因此D选项错误；该树中度为2的子节点有1个(b节点)，度为1的子节点有2个(d节点和c节点)，C选项正确。故答案为：C。 7．A 【详解】本题考查的是二叉数。根据题意，可以构建出如下二叉树。该二叉树的前序遍历为ABDGCEFH。不是完全二叉树，该二叉树中度为1的节点有3个。故本题应选A。 8．B 【详解】本题主要考查二叉树的遍历。已知一棵二叉树的前序遍历序列为：A- B- D- C - E可以确定根节点为A，已知后序遍历序列为:D- B- E-C- A可以确定左子树的起点为B，无法确定左子树到哪里结束，同样无法确定右子树的开始节点。所以无法确定唯一性，中序遍历序列可能为:B- D- A- E- C，故本题选B选项。 9．A 【详解】本题考查数据结构二叉树相关内容。由给定图示和后序遍历序列可知，该二叉树如图所示：    按照该图所示，其中序遍历序列为：FDAGBCE。故本题答案是A选项。 10．C 【详解】本题考查的是二叉树相关知识。该二叉树的后序遍历为DGEBFCA；该树中度为2 的节点有2个A、B；删除节点G后，C节点有右子树，无左子树，不是一棵完全二叉树。故选C。 11．B 【详解】本题考查VB编译。根据题干，出现溢出，说明数据太大，存储的变量容量不够，根据代码可知，当i=1 to 100000，s=s+1/i，s如用原来的数据量无法存储，故将变量s的数据类型变为存储量更大的变量，故本题选B。 12．C 【详解】本题主要考查二叉树的遍历。由中序和后序遍历可画出该二叉树，如下图，其前序遍历为+*%742/32，故本题选C选项。    13．C 【详解】本题考查的二叉树相关知识。一个具有n个节点的完全二叉树，其其叶子节点的个数为：n/2向上取整，或(n+1)/2向下取整。10/2=5，故选项C正确。 14．B 【详解】本题主要考查二叉树的遍历。中序遍历，即先遍历左子树、再遍历根节点、最后遍历右子树。由图可知，其节点的中序遍历的序列为GDBEACF，故本题选B选项。 15．C 【详解】本题考查算法的特征。大O符号通常用来描述算法在最坏情况下的时间复杂度，即算法执行所需的最长时间。故答案为：C。 16．D 【详解】本题考查的是二叉树相关知识。该二叉树不是完全二叉树。该二叉树的度为2，深度为4。E不是F的兄弟节点。该二叉树的前序遍历为ABEGCFD。故本题应选D。 17．B 【详解】本题主要考查二叉树的遍历。前序遍历是“根左右”，中序遍历是“左根右”，一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树如下： 由图可知，该二叉树的深度为5，故本题选B选项。 18．C 【详解】本题主要考查数据结构。一棵度为3，深度为4的树，则第一层有1个根节点，第二层最多有3个子节点，第三层最多有3*3=9个子节点，第四层最多有3*9=27个子节点，则最多有1+3+9+27=40个节点，故本题选C选项。 19．C 【详解】本题考查的是二叉树遍历相关知识。二叉树的中序遍历：先遍历左子树节点，再遍历根节点，再遍历右子树节点。选项A中序遍历结果为EDFBAC；选项B中序遍历结果为BEDFAC；选项C中序遍历结果为BAEDFC；选项D中序遍历结果为BACEDF，故本题应选C。 20．D 【详解】本题考查的是二叉树遍历。二叉树的三种基本遍历方式是前序遍历、中序遍历和后序遍历，不包括逆序遍历这一说法。逆序遍历通常指的是对一个线性结构的倒序访问，不是二叉树的标准遍历方式。故选D。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$