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

第四章 抽象数据类型 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．某完全二叉树的后序遍历为EBAGDC，则下列说法正确的是（    ） A．该树的深度为4 B．该树有2个叶子节点 C．该树的节点B、G是兄弟节点 D．删除节点E后，该树的前序遍历为CABDG 2．某二叉树的树形结构如图所示，其后序遍历结果为FBCEAD，则前序遍历结果为（    ） A．ABCDEF B．FEDCBA C．DFACBE D．FDBCAE 3．一棵有n(n>0）个结点的二叉树，其结点为0度或2度，则此树的最大高度是（   ） A．（n+1）//2 B．n//2 C．（n-1）//2 D．⌊log2n+1⌋ 4．用数组表示二叉树的示意图如下所示，则该二叉树的中序遍历序列为（   ） A．BEDFAC B．ABDEFC C．DBEAFC D．BDAECF 5．如图所示的二叉树，下列说法正确的是（   ） A．该二叉树是一个完全二叉树 B．该二叉树的深度为4，节点D的度为2 C．该二叉树的叶子节点数比非叶子节点数少一个 D．该二叉树中A是D和E的父节点 6．二叉树的中序遍历是 BAC，它的前序遍历不可能是（    ） A．ABC B．CBA C．ACB D．BAC 7．某二叉树前序遍历的结果为“ABCDEF”，后序遍历的结果为“BEFDCA”，则中序遍历的结果可能是（    ） A．CBDAEF B．CBAEDF C．BAEDFC D．BADCEF 8．已知二叉树T1前序遍历序列为A-B-D-E-C-F-H，中序遍历为D-E-B-A-F-H-C，则二叉树T1的后序遍历序列为（   ） A．E-D-B-F-H-C-A B．E-D-B-H-F-C-A C．D-E-B-H-F-C-A D．该二叉树形态不唯一，无法确定 9．某二叉树的中序遍历序列和后序遍历序列分别为DXAPBY  和DAXYBP，则其前序遍历序列是（   ） A．PXDAYB B．XPDABY C．PXDABY D．DAXPBY 10．某二叉树用一维数组存储结构如下表所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I 下列有关该二叉树的说法正确的是（   ） A．该树度为2的节点有4个 B．该树的前序遍历为A-B-D-E-G-H-C-F-I C．该树是完全二叉树，其深度为4 D．该树中共有3个叶子节点，分别是G、H、I 11．有二叉树用数组表示为：["A","B","C",None,"D","E","F",None,None,None,"G"]，则下列关于该二叉树的说法正确的是（　　） A．该二叉树度为1的节点有2个 B．该二叉树一共有3层 C．该二叉树中的叶子节点有4个 D．该二叉树的中序遍历序列是B-G-D-A-E-C-F 12．有一棵二叉树如图所示，该二叉树的后序遍历结果正确的是（    ） A．XBCDAYEF B．FEYADCBX C．DBEAFXCY D．DEFABYCX 13．树的叶子节点个数与度为2的节点数的关系是（   ） A．相等 B．多1 C．少1 D．无直接关系 14．某二叉树的树形结构如图所示，其后序遍历结果为CDAFB，则中序遍历结果为（   ） A．CDBAF B．DCBAF C．BDCFA D．ACDFB 15．某二叉树的中序遍历结果为DBEAFGC，后序遍历结果为DEBGFCA，则前序遍历结果为（   ） A．ABDECFG B．ABCDEFG C．ABEDFCG D．ABDECGF 16．如图a为一棵二叉树，其数组实现示意图(部分)如图b 所示 图 a 0      1      2      3      4      5     … A B C D E 图b 下列说法正确的是（    ） A．该二叉树的前序遍历为ABCDEFG B．该二叉树的高度为 3 C．该二叉树是完全二叉树 D．节点 G 存储在数组下标为 11 的位置 17．用一维数组表示二叉树，如下表所示： 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 下列有关该二叉树的说法正确的是（   ） A．该树中共有4个叶子节点 B．该树是完全二叉树，其深度为4 C．该树的中序遍历为B-F-D-G-A-C-E D．该二叉树的结构图为（如图所示） 18．有如下python程序段： a=[1,2,3,4,5,6];b=[0,1,1,0,0,1] top=1;sum=0;st=[0]*len(a) for i in range(len(a)):     if b[i]==1 or top==-1:         top+=1         st[top]=a[i]     elif a[i]%2==0;         top=1     else:         st[top]-=a[i]     sum+=st[top] 程序运行后变量sum的值是（   ） A．5 B．7 C．9 D．11 19．一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树的深度为（    ） A．6 B．5 C．4 D．3 20．有树结构的示意图如图所示，下列关于该树的描述正确的是（   ） A．该树的度为6 B．该树的叶子节点数量是7 C．节点I、J互为兄弟节点 D．该树的深度为5 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题考查二叉树相关内容。由于是完全二叉树，该树的模型已经确定，根据后序遍历可知该二叉树为 ，该树深度为3，有3个叶子节点，节点B、G是堂兄弟节点，不是兄弟节点，ABC选项说法错误。删除节点E后，该树的前序遍历为CABDG，D选项说法正确。故本题答案是D选项。 2．C 【详解】 本题考查二叉树的前序遍历。后序遍历规则为“左右根”，已知后序遍历结果为FBCEAD，结合题干中树形结构图可知该二叉树的树形结构应为：，前序遍历规则为“根左右”，根据完整的二叉树结构图，得出前序遍历为DFACBE。故答案为C选项。 3．A 【详解】本题考查二叉树相关内容。二叉树由根节点和其子节点组成，每个节点的度有如下可能：0，1，2，根据题干，该二叉树的节点的都为0度或2度，即除根节点外，其每个节点都有一个兄弟节点。由于题目求的为该树的最大高度，即考虑极端情况下，每一层都只有一对兄弟节点，此时除根节点外，每一层都有两个节点，则除第一层外，节点数除2为除第一层外的层数。则假设根节点有一个兄弟节点后，则对2整除，则为层数。即(n+1)//2。故本题答案是A选项。 4．A 【详解】本题考查二叉树相关内容。由二叉树存储可推知该二叉树结构，如图所示： 该二叉树的中序遍历结果为：BEDFAC。故本题答案是A选项。 5．C 【详解】本题考查的是二叉树。完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1)) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉数。图中所示的二叉树不是一个完全二叉树；该二叉树的深度为4，节点D的度为1；该二叉树的叶子节点数（3）比非叶子节点数（4）少一个；A是B和C的父节点。故本题应选C。 6．C 【详解】本题考查二叉树遍历相关内容。由二叉树前序遍历及中序遍历相关知识，推知：对比AC选项，均以A为根节点，由中序遍历是 BAC知，其左孩子为B，右孩子为C，其前序遍历序列为ABC，不可能得出序列ACB，A选项正确，C选项错误。BD选项为可能前序遍历。故本题答案是C选项。 7．C 【详解】本题主要考查二叉树的遍历。前序遍历的第一个和后序遍历的最后一个一定是树根，前序遍历的第二个不是左子树的根就是右子树的根，如果前序遍历第二个与后序遍历的倒数第二个相同则他是根的右子树否则是根的左子树，因此B是左子树的根，同理可以判断C是右子树的根。结合选项可知，只有选项C，BAEDFC符合题意，故本题选C选项。 8．B 【详解】本题考查二叉树遍历相关内容。由前序遍历序列和中序遍历序列可以唯一确定一棵二叉树。由题中二叉树前序、中序遍历序列确定的二叉树如图所示：。其后序遍历序列为：EDBHFCA。故本题答案为B选项。 9．C 【详解】本题考查的是二叉树的遍历。根据中序和后序，可以还原二叉树，见下图：    再前序遍历得到前序序列。根据定义：中序是“左中右”，后序是“左右中”，前序是“中左右”。选项C符合题意。 10．B 【详解】本题考查二叉树相关内容。分析其存储结构，得出其形态如图所示：。A选项，度为2的节点有3个，选项错误。B选项，前序遍历序列为：ABDEGHCFI，选项正确。C选项，该二叉树不符合完全二叉树的定义，选项错误。D选项，共有4个叶子节点，分别是：D、G、H、I，选项错误。故本题答案是B选项。 11．A 【详解】本题主要考查二叉树的描述。该二叉树如下，由图可知，该二叉树度为1的节点有2个；该二叉树一共有4层；该二叉树中的叶子节点有3个；该二叉树的中序遍历序列是B-D-G-A-E-C-F，故本题选A选项。    12．D 【详解】本题主要考查二叉树的遍历。二叉树的后序遍历：即先左子树、再右子树、最后根，故该二叉树的后序遍历结果正确的是DEFABYCX，故本题选D选项。 13．B 【详解】本题考查的是数的叶子和度的关系。在任何一棵二叉树中，叶子节点（度为0的节点）的数量总是比度为2的节点的数量多1。这是二叉树的一个重要性质，可以用归纳或数学证明来验证。故选B。 14．B 【详解】本题考查的是二叉树遍历。依据题意可知改二叉树为： 故其中序遍历结果为：DCBAF。故选B。 15．A 【详解】本题考查树的遍历相关知识。 已知中序遍历规则“左根右”和后序遍历规则“左右根”可知：根节点为A，左子树为DBE右子树为 FGC。以此画出二叉树如下： 故其前序遍历结果为：ABDECFG。答案选A。 16．D 【详解】本题主要考查二叉树的描述。由图可知，该二叉树的前序遍历为ABDCEGF；该二叉树的高度为 4；该二叉树是不完全二叉树；按照数组示意图，可知是逐层自左向右依次存储，没有的元素为空，可推得节点 G 存储在数组下标为 11 的位置，故本题选D选项。 17．C 【详解】 本题考查二叉树相关内容。由二叉树存储结构可以画出此二叉树的形态：。根据图可知共有3个叶子节点；此树的深度为4；是一棵不规则的二叉树；中序遍历为BFDGACE。故本题答案是C选项。 18．D 【详解】本题考查栈的应用。分3种情况，入栈、出栈、栈顶减值，如下表所示。 变量 1 2 3 4 5 6 结果=1+2+3+2-3+6 b[i] 0 1 1 0 0 1 操作 入栈 入栈 入栈 出栈 减值 入栈 栈顶 1 2 3 2 -3 6 故选择D 19．B 【详解】本题主要考查二叉树的遍历。前序遍历是“根左右”，中序遍历是“左根右”，一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树如下： 由图可知，该二叉树的深度为5，故本题选B选项。 20．B 【详解】本题主要考查树结构的描述。由图可知，该树的度为3； 该树的叶子节点数量是7； 节点I、H互为兄弟节点； 该树的深度为4，故本题选B选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$