高中信息技术浙教版(2019)选修一 4.1树与二叉树

高中信息技术浙教版(2019)4.1树与二叉树 一、选择题 1．某二叉树前序遍历的结果为“ABCDEF”，后序遍历的结果为“BEFDCA”，则中序遍历的结果可能是（    ） A．CBDAEF B．CBAEDF C．BAEDFC D．BADCEF 2．某二叉树如图所示，下列说法正确的是（   ） A．该二叉树是完全二叉树 B．该二叉树共有4个叶子节点 C．节点D、F都是节点B的孩子节点 D．该二叉树后序遍历的结果为DEBFCA 3．用一维数组表示二叉树，如下表所示： 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 下列有关该二叉树的说法正确的是（    ） A．该树中共有4个叶子节点，度为2的节点有2个 B．该树的中序遍历为B-F-D-G-A-C-E C．该树是完全二叉树，其深度为4 D．该树有7条边 4．某二叉树的中序遍历序列和后序遍历序列分别为DXAPBY  和DAXYBP，则其前序遍历序列是（   ） A．PXDAYB B．XPDABY C．PXDABY D．DAXPBY 5．已知某二叉树的前序遍历是cdaefh，中序遍历是adechf，则下列说法正确的是（　　） A．该二叉树是完全二叉树 B．该二叉树的数组实现示意图如下 C．该二叉树的高度为4 D．该二叉树的后序遍历是aedfhc 6．若一棵二叉树中序遍历序列为BIGDHAECF，后序遍历序列为IGHDBEFCA，则该二叉树的前序遍历序列为（    ） A．ABCDEFGHI B．ABDGHICEF C．ABDHGICEF D．ABDGIHCEF 7．已知一棵完全二叉树共有6个节点，前序遍历为ABCDEF，下列说法正确的是（    ） A．该二叉树的后序遍历为CDBFEA B．该二叉树中只有1个度为2的节点 C．节点F的父节点是C D．该二叉树共有4个叶子节点 8．已知一棵二叉树的后序遍历为CDAFEBG，中序遍历为CADGFBE，则该二叉树的前序遍历序列为（   ） A．GACBDFE B．GACDBFE C．GACDBEF D．GCADBEF 9．某公司内部管理的组织关系如图所示。通过观察可知，该组织形式是一种树形结构，下列说法不正确的是（   ） A．该树的根节点是“总经理室” B．“销售部”节点的父节点是“业务部”节点 C．“技术部”节点是“项目部”节点和“运维部”节点的父节点 D．该树中，数据元素之间是多对多的关系 10．一棵有n(n>0）个结点的二叉树，其结点为0度或2度，则此树的最大高度是（   ） A．（n+1）//2 B．n//2 C．（n-1）//2 D．⌊log2n+1⌋ 11．某二叉树用一维数组存储结构如下表所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H 下列有关该二叉树的说法正确的是（   ） A．该二叉树是完全二叉树 B．度为2的节点有3个 C．前序遍历为A-B-D-F-G-C-H-E D．节点C是节点E的父节点 12．某二叉树按从上而下、自左往右的顺序，对节点进行编号，数组存储示意图如下： 0 1 2 3 4 5 6 7 8 A B C D E F G 下列关于该二叉树，说法正确的是（   ） A．该二叉树的叶子节点有4个，分别是C，E，F，G B．该二叉树后序遍历结果为FGDBECA C．该二叉树共有4层，E和F位于同一层 D．该二叉树共有3对兄弟节点 13．一个具有1025个结点的二叉树的高h为（   ） A．11 B．10 C．11至1025之间 D．10至1024之间 14．某二叉树如图所示，下列说法正确的是（    ） A．该二叉树共有5个叶子节点 B．该二叉树是一棵完全二叉树 C．对该二叉树进行中序遍历后的计算结果是32 D．该二叉树的后序遍历序列为731+*426+/- 15．树是一种什么样的数据结构（   ） A．非线性结构 B．线性结构 C．集合结构 D．网状结构 二、填空题 16．设树T有17条边，12片树叶，4个4度内部节点，1个3度内部节点。则T的树根的度数为 。 17．由a，b，c3个不同的数字组成一个N位数，要求不出现两个a相邻，也不出现两个b相邻，这样的N位数的个数为AN，用AN-1和AN-2表示AN的关系式为:AN= 。 三、操作题 18．什么是二叉树？请简述其特点。 四、简答题 19．请简述什么是二叉树，并说明其特点。 20．描述什么是二叉树，并解释二叉搜索树的特点。 21．解释什么是二叉树的遍历，并简述其常见的遍历方法。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．D 3．B 4．C 5．A 6．D 7．A 8．B 9．D 10．A 11．D 12．B 13．C 14．D 15．A 16．3 17．AN=2AN-1+AN-2（N>=2），且A0=1，A1=3 18．二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。其特点是每个节点都有序，左子节点的值小于或等于父节点的值，右子节点的值大于或等于父节点的值。 19．二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。其特点是每个节点只有一个父节点，可以高效地进行数据的插入、删除和查找操作。 20．二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。 21．二叉树的遍历是指按照某种顺序访问树中的所有节点。常见的遍历方法包括前序遍历（Pre-order）、中序遍历（In-order）、后序遍历（Post-order）和层序遍历（Level-order）。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$