浙教版（2019）选修一4.2二叉数的基本操作同步练习（含解析）

浙教版（2019）选修一4.2二叉数的基本操作同步练习 学校:_____姓名：_____班级：_____考号：_____ 一、选择题 1．某二叉树的中序遍历序列为DEBAFCGH，后序遍历序列为EDBFHGCA，则该二叉树的前序遍历序列为（ ） A．ABDECGHF B．ABCDEFGH C．ABCDFGEH D．ABDECFGH 2．有一棵8个节点的二叉树，下列说法正确的是（ ） A．叶子节点可能为4个 B．第3层最多6个节点 C．度为1的节点最多4个 D．该树的层数可能为3层 3．若一棵二叉树的中序遍历序列为ABCDE，则该二叉树不可能是（ ） A． B． C． D． 4．一个数学表达式可以用一棵表达式树来表示，而一棵二叉树可以用一维数组表示。有一棵表达式树用一维数组表示如下。下列有关该表达式树的说法正确的是（ ） 0 1 2 3 4 5 6 7 8 '/' '_' '4' '*' '8' '4' '6' A．该表达式树是一棵完全二叉树 B．该表达式树的左右子树深度相差为1 C．该表达式树的叶子结点有4 D．该表达式树中序遍历的结果为4*6/8-4 5．某二叉树如图所示，下列说法正确的是（ ） A．若补全成高度为5的满二叉树则需增加24个节点 B．该树的度和深度分别为2和3 C．该二叉树中序遍历的结果为DBEAGCF D．节点D、F都是节点B的孩子节点 6．某完全二叉树的后序遍历为EBAGDC，则下列说法正确的是（ ） A．该树的深度为4 B．该树有2个叶子节点 C．该树的节点B、G是兄弟节点 D．删除节点E后，该树的前序遍历为CABDG 7．有如下Python程序段: def search(x): ans="" if a[2 *x]!="": ans= ans+search(2 *x) if a[2*x+1]!="": ans= ans+search(2*x+1) ans= ans+a[x] return ans a=["" for i in range(32)] a[1]="A";a[2]="B";a[3]="C";a[4]="D";a[7]="E";a[9]="F" print(search(1)) 运行该程序段后，输出的结果是（ ） A．FDBECA B．ACEBDF C．ABCDEF D．FEDCBA 8．某最优二叉树如下图所示。 则该二叉树的带权路径长度之和为（ ） A．74 B．104 C．126 D．178 9．一棵二叉树的数组形式存储如下表所示。 数组下标 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 10．已知6个节点的二叉树的先序遍历是abdcef，中序遍历是dbaecf，则该二叉树的后序遍历为（ ） A．dbaefc B．dbacef C．dbefca D．bdefca 11．完全二叉树的节点个数为4*N+3，则它的叶子节点个数为（ ） A．2*N B．2*N-1 C．2*N+1 D．2*N+2 12．完全二叉树的节点个数为13，则它的叶子节点个数为（ ） A．9 B．8 C．7 D．6 13．满二叉树的叶子节点个数为N，则它的节点总数为（ ） A．N B．2N C．2N-1 D．2N-1 14．一个高度为h的二叉树最少节点数为（ ） A．2h+1 B．2h-1 C．h D．2h-1 15．表达式(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 / - 试卷第1页，共3页 试卷第1页，共3页 参考答案： 1．D 【详解】本题考查二叉树遍历。中序遍历序列为DEBAFCGH，后序遍历序列为EDBFHGCA，可还原二叉树的形状。 最终二叉树的前序遍历为ABDECFGH，选项D为正确答案。 2．A 【详解】本题考查数据结构二叉树相关内容。A选项，叶子节点可能为4个，选项说法正确。B选项，依据二叉树性质，第三层节点数最多为：23-1=4，选项说法错误。C选项，度为1的节点最多7个（该二叉树共8层，每层1个节点，度为1的有7个），选项说法错误。D选项，该树的层数不可能为3层（3层二叉树最多有7个节点），选项说法错误。 3．B 【详解】本题考查二叉树的遍历。选项B对应的中序遍历是ABCED。故选B。 4．C 【详解】本题考查二叉树相关内容。由该二叉树的一维数组表示可知，该二叉树结构如图 ... ...