浙教版（2019）选修一 4.1 树与二叉树

4.1树与二叉树 一、选择题 1．已知一棵二叉树如图所示，则下列说法正确的是（   ） A．该二叉树的后序遍历为DEGBFCA B．该树中度为2 的节点只有1个 C．若补全成高度为4的满二叉树则需增加8个节点 D．删除节点G后，该树成为一棵完全二叉树 2．有一棵完全二叉树具有100个结点，下列说法正确的是（   ） A．树的深度为8 B．有1个节点只有非空左子树 C．此完全二叉树有49个叶子结点 D．有50个度为2的节点 3．在满二叉树中，第i层的节点数最多是（   ） A．2^(i-1) B．2^i C．2^(i+1) D．(2^i)-1 4．已知一棵二叉树的后序遍历为CDAFEBG，中序遍历为CADGFBE，则该二叉树的前序遍历序列为（   ） A．GACBDFE B．GACDBFE C．GACDBEF D．GCADBEF 5．已知一棵具有9个节点的二叉树的中序遍历序列为7%4*2+3/2，后序遍历序列为74%2*32/+，以下说法不正确的是（    ） A．用数组表示该树，叶子节点的最小下标是4 B．这是一棵完全二叉树 C．其前序遍历序列为+*7%42/32 D．这棵树叶子结点比非叶子结点数多1 6．某二叉树的中序遍历序列和后序遍历序列分别为DXAPBY  和DAXYBP，则其前序遍历序列是（   ） A．PXDAYB B．XPDABY C．PXDABY D．DAXPBY 7．有二叉树的前序遍历序列为A-B-C-E-F-G-D，中序遍历序列为A-E-C-F-G-B-D，则关于该二叉树的说法正确的是（   ） A．该二叉树根节点的度为1 B．该二叉树的高度为4 C．该二叉树中节点G是节点C的左孩子 D．该二叉树中叶子节点的个数为4 8．有如图所示的二叉树，下列说法正确的是（ ） A．该树度为2的节点数为1 B．该树的深度为3 C．该树的中序遍历序列为B-A-C-E-D-F D．该树可以用一维数组['A','B','C','','D','','E','F']存储 9．已知7个结点的二叉树的前序遍历是 A B D E F C G（字母为结点的编号，以下同），中序遍历是D B F E A G C，则该二叉树的后序遍历是（   ） A．D F E B G C A B．D F E B A C G C．F B C G E D A D．D F E C A G B 10．已知某二叉树的前序遍历序列为ABCDEF，中序遍历序列为BCAEFD，则该二叉树的后序遍历序列为（    ） A．CBFEDA B．BCDEFA C．CBEFDA D．BCFEDA 11．某二叉树如图所示，下列说法正确的是（    ） A．该二叉树共有5个叶子节点 B．该二叉树是一棵完全二叉树 C．对该二叉树进行中序遍历后的计算结果是32 D．该二叉树的后序遍历序列为731+*426+/- 12．一棵二叉树的高度为h，所有节点的度为0或2，则此二叉树的节点数最少为（   ） A．2h-1 B．2h+1 C．h+1 D．2h-1 13．树的度指的是（   ） A．树中边的数量 B．树中节点的最大子节点数 C．树的深度 D．树的广度 14．某公司内部管理的组织关系如图所示。通过观察可知，该组织形式是一种树形结构，下列说法不正确的是（   ） A．该树的根节点是“总经理室” B．“销售部”节点的父节点是“业务部”节点 C．“技术部”节点是“项目部”节点和“运维部”节点的父节点 D．该树中，数据元素之间是多对多的关系 15．某二叉树的树形结构如图所示，其前序遍历结果为BADCFGE，则字符“G”所在的位置为（    ） A．① B．② C．③ D．④ 二、填空题 16．由a，b，c3个不同的数字组成一个N位数，要求不出现两个a相邻，也不出现两个b相邻，这样的N位数的个数为AN，用AN-1和AN-2表示AN的关系式为:AN= 。 17．设树T有17条边，12片树叶，4个4度内部节点，1个3度内部节点。则T的树根的度数为 。 三、操作题 18．什么是二叉树？请简述其特点。 四、简答题 19．解释什么是二叉树的遍历，并简述其常见的遍历方法。 20．请描述什么是二叉树，并简述其在计算机科学中的应用。 21．描述什么是二叉树，并解释二叉搜索树的特点。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．B 3．B 4．B 5．C 6．C 7．A 8．C 9．A 10．A 11．D 12．A 13．B 14．D 15．C 16．AN=2AN-1+AN-2（N>=2），且A0=1，A1=3 17．3 18．二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。其特点是每个节点都有序，左子节点的值小于或等于父节点的值，右子节点的值大于或等于父节点的值。 19．二叉树的遍历是指按照某种顺序访问树中的所有节点。常见的遍历方法包括前序遍历（Pre-order）、中序遍历（In-order）、后序遍历（Post-order）和层序遍历（Level-order）。 20．二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树在计算机科学中有广泛应用，如在搜索算法（二叉搜索树）、表达式求值、数据压缩等领域。 21．二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$