第四章 抽象数据类型 2024-2025学年高中信息技术粤教版（2019）选修1

第四章 抽象数据类型2024—2025学年高中信息技术粤教版（2019）选修1 一、选择题 1．一棵深度为h的满二叉树有（   ）个叶子节点。 A．2^h B．2^(h-1) C．2^(h-1) - 1 D．2^h / 2 2．某二叉树的树形结构如图所示，其后序遍历结果为BDEFCA，则中序遍历结果为（   ） A．EDCFBA B．ECFDAB C．BFDEAC D．BFEDAC 3．如图所示二叉树的前序遍历序列是（   ） A． A-B-C-D-E-G-H-F-I B．A-B-D-E-G-H-C-F-I C．D-B-E-G-H-A-C-F-I D．B-D-G-H-E-A-F-I-C 4．如图，下列关于该二叉树的说法正确的是（   ） A．该二叉树为完全二叉树 B．该二叉树的度为5，深度为4 C．该二叉树中，E和D都是F的兄弟节点 D．该二叉树的前序遍历为ABEGCFD 5．一棵二叉树的数组形式存储如下表所示。 数组下标 0 1 2 3 4 5 6 7 8 9 10 11 数组元素 a b c d e f g 关于该二叉树，下列说法错误的是（   ） A．该二叉树的深度为4 B．该二叉树中共有3个叶节点 C．该二叉树的前序遍历序列为abdcefg D．g节点的父节点是e 6．某二叉树的前序遍历结果为ABCEDF，在该二叉树基础上添加一个节点后的中序遍历为BGCADEF，则添加节点后的后序遍历结果为（   ） A．CGBDFEA B．GCBADFE C．CGBEFDA D．GCBDFEA 7．一个数学表达式可以用一棵表达式树来表示，而一棵二叉树可以用一维数组表示。有一棵表达式树用一维数组表示如下。下列有关该表达式树的说法正确的是（    ） 0 1 2 3 4 5 6 7 8 '/' '_' '4' '*' '8' '4' '6' A．该表达式树是一棵完全二叉树 B．该表达式树的左右子树深度相差为1 C．该表达式树的叶子结点有4 D．该表达式树中序遍历的结果为4*6/8-4 8．一棵包含10个节点的完全二叉树，其叶子节点的个数为（　　） A．3 B．4 C．5 D．6 9．已知某二叉树的后序遍历为GDBEHFCA，中序遍历为DGBAECHF，下列说法正确的是（    ） A．该二叉树中叶子节点有3个 B．该二叉树的前序遍历为ABDGCEHF C．该二叉树是一棵完全二叉树，树的高度为4 D．该二叉树中度为1的节点有2个 10．树是一种什么样的数据结构（   ） A．非线性结构 B．线性结构 C．集合结构 D．网状结构 11．用数组表示二叉树的示意图如下所示：（    ） 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 12．有一棵二叉树，如图所示，下列说法正确的是（   ） A．此二叉树是完全二叉树 B．此二叉树的叶子节点有3个 C．此二叉树的后序遍历为F—D—B—E—C—A D．此二叉树用一维数组表示为[‘A’‘B’，‘C’，‘D’，‘E’，‘F’] 13．诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是（   ） A．树 B．栈 C．队列 D．链表 14．以下数据结构中不属于线性结构的是（    ） A．数组 B．链表 C．队列 D．树 15．已知一棵二叉树如图所示，下列说法正确的是（    ） A．树的高度是4，节点F是唯一的叶子节点 B．中序、后序的遍历方式，节点F先于节点D、E访问 C．前序遍历的结果为A—B—C—D—E—F D．使用数组可以表示为［’A’，’B’，’C’，’，’’，’D’，’E'，’F’] 16．某二叉树如图所示，下列说法正确的是（   ） A．该二叉树是完全二叉树 B．该二叉树共有4个叶子节点 C．节点D、F都是节点B的孩子节点 D．该二叉树后序遍历的结果为DEBFCA 17．已知一棵二叉树的后序遍历为CDAFEBG，中序遍历为CADGFBE，则该二叉树的前序遍历序列为（   ） A．GACBDFE B．GACDBFE C．GACDBEF D．GCADBEF 18．如图所示的二叉树，下列说法正确的是（   ） A．该二叉树是一个完全二叉树 B．该二叉树的深度为4，节点D的度为2 C．该二叉树的叶子节点数比非叶子节点数少一个 D．该二叉树中A是D和E的父节点 19．一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树的深度为（    ） A．6 B．5 C．4 D．3 20．现有一棵二叉树，度为2的节点有10个，度为1的节点有5个，则这棵二叉树共有节点数为（   ） A．25 B．26 C．27 D．不确定 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查的是二叉树相关知识。一棵深度为h的满二叉树的叶子节点数可以通过公式2^(h-1)计算得出。这是因为满二叉树的每一层节点数都是上一层的两倍，从根节点往下数，第一层（根节点所在层）有1个节点，第二层有2个节点，以此类推，到第h层有2^(h-1)个节点，而最后一层全是叶子节点，故叶子节点数为2^(h-1)。故选B。 2．C 【详解】本题考查二叉树相关内容。分析其后序遍历序列及给定图示，可推知，该二叉树结构为：，其中序遍历序列为：BFDEAC。对比4个选项，C选项正确。故本题答案是C选项。 3．B 【详解】本题考查二叉树遍历相关内容。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。由图可知，该二叉树的前序遍历序列是：A-B-D-E-G-H-C-F-I。故本题答案是B选项。 4．D 【详解】本题考查的是二叉树相关知识。该二叉树不是完全二叉树。该二叉树的度为2，深度为4。E不是F的兄弟节点。该二叉树的前序遍历为ABEGCFD。故本题应选D。 5．C 【详解】本题考查二叉树相关内容。该二叉树如下图所示： 该二叉树的前序遍历序列为abdcegf，因此C选项错误，故本题答案为C选项。 6．D 【详解】 本题考查二叉树相关内容。根据前序遍历确定根节点为A，由添加节点后的中序遍历判断，左子树为BC，左子树根为B，右子树为EDF，右子树根为E，二叉树结构为：。新增节点G为节点C的左孩子。添加节点G后的二叉树为：。则添加节点后的后序遍历序列为：GCBDFEA。故本题答案是D选项。 7．C 【详解】本题考查二叉树相关内容。由该二叉树的一维数组表示可知，该二叉树结构如图所示：。A选项，该二叉树不是完全二叉树，选项错误。B选项，该表达式树的左右子树深度相差为2，选项错误。C选项，该表达式树的叶子结点有4个，选项正确。D选项，该表达式树中序遍历的结果为4*6-8/4，选项错误。故本题答案是C选项。 8．C 【详解】本题考查的二叉树相关知识。一个具有n个节点的完全二叉树，其其叶子节点的个数为：n/2向上取整，或(n+1)/2向下取整。10/2=5，故选项C正确。 9．A 【详解】本题考查的是二叉数。根据题意，可以构建出如下二叉树。该二叉树的前序遍历为ABDGCEFH。不是完全二叉树，该二叉树中度为1的节点有3个。故本题应选A。 10．A 【详解】本题考查树。树是一种典型的非线性数据结构，因为它允许一个节点有多个后继节点，形成了分支结构，不同于线性结构（如数组、链表）中每个元素只有一个后继和/或前驱。故选择A。 11．D 【详解】本题考查的是二叉树。依据题意可知二叉树为： 故其深度为4；不是完全二叉树；该二叉树有3个叶子节点；该二叉树后序遍历的结果为DCEFAB。故选D。 12．C 【详解】本题考查二叉树相关知识。A选项，观察此图，结合完全二叉树的定义，发现该二叉树不是完全二叉树，A错误；该二叉树的叶子节点有2个，不是3个，B错误；C选项，按照后序遍历（左右根）规则，该二叉树后序遍历序列为：FDBECA，正确。D选项，观察一维数组可以发现，B节点的孩子为D、E节点，这不符合二叉树图示，D错误。故本题答案是C选项。 13．A 【详解】本题考查的是数据结构。树状图是一种数据结构，它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。故本题应选A。 14．D 【详解】本题主要考查数据结构的描述。线性结构是一个有序数据元素的集合，如数组、链表和队列。树结构属于非线性结构，故本题选D选项。 15．B 【详解】本题考查二叉树。二叉树的高度为4，其中叶子节点为节点B、节点F、节点E，A选项错误。中序遍历先遍历左子树，然后访问根结点，最后遍历右子树，此时遍历顺序为：BAFDCE，而后序遍历则先遍历左子树，然后遍历右子树，最后访问根节点，此时遍历顺序为：BFDECA，故节点F均先于节点D、E访问，选项B正确。前序遍历先访问根节点，再遍历左子树，最后遍历右子树，此时遍历顺序为：ABCDFE，选项C错误。使用数组可以表示为［’A’，’B’，’C’，’’，’’，’D’，’E'，’’，’’，’’，’’，’F’]，D选项错误。故答案为B选项。 16．D 【详解】本题考查二叉树。 选项A，该二叉树不是完全二叉树，如果是完全二叉树，则叶子节点F的位置应该是C节点的左孩子节点。 选项B，该二叉树共有4个叶子节点，说法错误。共有3个叶子节点，分别是D、E、F。 选项C，说法错误，F节点是节点C的孩子节点。 故正确答案为：选项D。 17．B 【详解】本题考查的是二叉树的遍历。依据题意可知该二叉树如下： 故该二叉树的前序遍历序列为：GACDBFE。选项B正确。 18．C 【详解】本题考查的是二叉树。完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1)) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉数。图中所示的二叉树不是一个完全二叉树；该二叉树的深度为4，节点D的度为1；该二叉树的叶子节点数（3）比非叶子节点数（4）少一个；A是B和C的父节点。故本题应选C。 19．B 【详解】本题主要考查二叉树的遍历。前序遍历是“根左右”，中序遍历是“左根右”，一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树如下： 由图可知，该二叉树的深度为5，故本题选B选项。 20．B 【详解】本题考查二叉树相关内容。二叉树中，总的节点个数=度为0的节点个数+度为1的节点个数+度为2的节点个数；其中，度为0的节点个数=度为2的节点个数+1；故总的节点个数=度为1的节点个数+度为2的节点个数*2+1=5+10*2+1=26，故本题答案是B选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$