2023-2024学年高二上学期浙教版(2019)选修一4.1树与二叉树

2023-2024学年高二上学期浙教版(2019)选修一4.1树与二叉树 一、选择题 1．某二叉树使用一维数组存储结构进行存储 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F 则该二叉树的中序遍历结果为（   ） A．BAEDFC B．ECFDAB C．BFDEAC D．EDFCBA 2．已知一棵二叉树如图所示，下列说法正确的是（    ） A．树的高度是4，节点F是唯一的叶子节点 B．中序、后序的遍历方式，节点F先于节点D、E访问 C．前序遍历的结果为A—B—C—D—E—F D．使用数组可以表示为［’A’，’B’，’C’，’，’’，’D’，’E'，’F’] 3．一棵包含10个节点的完全二叉树，其叶子节点的个数为（　　） A．3 B．4 C．5 D．6 4．已知一棵二叉树的中序遍历序列为9–4+2*3/1+4，后序遍历序列为94–23*+14+/，以下说法正确的是（   ） A．这棵树叶子结点比非叶子结点数多1 B．这是一棵满二叉树 C．其前序遍历序列为/+-94*231+4 D．这棵树有5层 5．某完全二叉树，中序遍历结果为“甲乙丙丁”，则后序遍历结果是（   ） A．甲乙丁丙 B．丙乙甲丁 C．甲丁丙乙 D．乙丁丙甲 6．已知某二叉树的前序遍历序列为ABCDEF，中序遍历序列为BCAEFD，则该二叉树的后序遍历序列为（    ） A．CBFEDA B．BCDEFA C．CBEFDA D．BCFEDA 7．有一棵二叉树，如图所示,下列说法正确的是（   ） A．此二叉树是完全二叉树 B．此二叉树的深度是3 C．此二叉树的中序遍历为H-D-B-E-A-C-F D．此二叉树用一维数组表示为['A','B',' ','C','D','E',' ','F',' ','H'] 8．诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是（   ） A．树 B．栈 C．队列 D．链表 9．下列二叉树中，中序遍历结果为BAEDFC的是（   ） A． B． C． D． 10．某二叉树对应的一维数组表示如下图所示： 下列关于该二叉树的说法正确的是（   ） A．这是一棵完全二叉树 B．节点F是节点D的孩子节点 C．该二叉树有1个叶子结点 D．该二叉树中序遍历的结果是DBEACF 11．某二叉树前序遍历的结果为“ABCDEF”，后序遍历的结果为“BEFDCA”，则中序遍历的结果可能是（    ） A．CBDAEF B．CBAEDF C．BAEDFC D．BADCEF 12．树的叶子节点个数与度为2的节点数的关系是（   ） A．相等 B．多1 C．少1 D．无直接关系 13．一棵有n(n>0）个结点的二叉树，其结点为0度或2度，则此树的最大高度是（   ） A．（n+1）//2 B．n//2 C．（n-1）//2 D．⌊log2n+1⌋ 14．有二叉树的前序遍历序列为A-B-C-E-F-G-D，中序遍历序列为A-E-C-F-G-B-D，则关于该二叉树的说法正确的是（   ） A．该二叉树根节点的度为1 B．该二叉树的高度为4 C．该二叉树中节点G是节点C的左孩子 D．该二叉树中叶子节点的个数为4 15．有如图所示的树。下列说法正确的是（   ） A．该树中共有3个叶子节点 B．该树的度和深度均为3 C．该树中度为2的子节点有1个，度为1的子节点有2个 D．节点e是节点f的兄弟节点 二、填空题 16．二叉树是一种每个节点最多有 个子节点的树结构。 17．由a，b，c3个不同的数字组成一个N位数，要求不出现两个a相邻，也不出现两个b相邻，这样的N位数的个数为AN，用AN-1和AN-2表示AN的关系式为:AN= 。 18．设树T有17条边，12片树叶，4个4度内部节点，1个3度内部节点。则T的树根的度数为 。 三、操作题 19．什么是二叉树？请简述其特点。 四、简答题 20．描述什么是二叉树，并解释二叉搜索树的特点。 21．解释什么是二叉树的遍历，并简述其常见的遍历方法。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 2．B 3．C 4．A 5．A 6．A 7．C 8．A 9．C 10．D 11．C 12．B 13．A 14．A 15．C 16．两 17．AN=2AN-1+AN-2（N>=2），且A0=1，A1=3 18．3 19．二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。其特点是每个节点都有序，左子节点的值小于或等于父节点的值，右子节点的值大于或等于父节点的值。 20．二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。 21．二叉树的遍历是指按照某种顺序访问树中的所有节点。常见的遍历方法包括前序遍历（Pre-order）、中序遍历（In-order）、后序遍历（Post-order）和层序遍历（Level-order）。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$