第4章  树（单元检测卷）-高中信息技术选修1数据与数据结构 单元检测卷

第4章  树-综合与评价（分层作业） 【夯实基础】 1. 若一棵二叉树的中序遍历序列为ABCDE，则该二叉树不可能是（ ） 2. 某二叉树如图所示，下列说法正确的是（       ） A．若补全成高度为5的满二叉树则需增加24个节点 B．该树的度和深度分别为2和3 C．该二叉树中序遍历的结果为DBEAGCF D．节点D、F都是节点B的孩子节点 3. 二叉树的每个节点最多有几个子节点？（       ） A. 0 B. 1 C. 2 D. 无限 4. 二叉树的遍历方式不包括以下哪一种？（       ） A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 逆序遍历 5. 在满二叉树中，第i层的节点数最多是多少？（       ） A. 2^(i-1) B. 2^i C. 2^(i+1) D. (2^i)-1 6. 树是一种什么样的数据结构？（       ） A. 非线性结构 B. 线性结构 C. 集合结构 D. 网状结构 7. 树的度指的是什么？（       ） A. 树中边的数量 B. 树中节点的最大子节点数 C. 树的深度 D. 树的广度 8. 树的叶子节点个数与度为2的节点数的关系是什么？（       ） A. 相等 B. 多1 C. 少1 D. 无直接关系 【巩固提升】 9. 在树的先序遍历序列中，根节点的位置在哪里？ A. 最后 B. 中间 C. 第一个 D. 任意位置 10. 一棵深度为h的满二叉树有多少个叶子节点？ A. 2^h B. 2^(h-1) C. 2^(h-1) - 1 D. 2^h / 2 11. 二叉树的后序遍历序列是D B E A C，中序遍历序列是D E B A C，根节点是什么？ A. D B. B C. E D. A 12.一个数学表达式可以用一棵表达式树来表示，而一棵二叉树可以用一维数组表示。有一棵表达式树用一维数组表示如下。下列有关该表达式树的说法正确的是（       ） A．该表达式树是一棵完全二叉树 B．该表达式树的左右子树深度相差为1 C．该表达式树的叶子结点有4 D．该表达式树中序遍历的结果为4*6/8-4 13.由3个结点可以构造出多少种不同的二叉树？（    ） A．2          B．3             C．4          D．5   【拓展应用】 14. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 A．250 B． 500 C．254 D．501 15. 一个具有1025个结点的二叉树的高h为（ ）。 A．11 B．10 C．11至1025之间 D．10至1024之间 参考答案： 【夯实基础】 1. B 解析：本题考查二叉树的遍历。选项B对应的中序遍历是ABCED。故选B 2. A解析：本题考查二叉树相关内容。A选项，依据二叉树性质，高度为5的满二叉树有25-1=31个节点，现有7个节点，需要增加24个节点，选项正确。B选项，该二叉树的度为2，深度为4，选项错误。C选项，二叉树中序遍历规则是:若二叉树非空，则先遍历二叉树的左子树，再遍历根节点，最后遍历右子树，该二叉树的中序遍历序列是:DBEGACF，选项错误。D选项，D是B的孩子节点，F是C的孩子节点，选项错误。 3. C. 解析：二叉树的每个节点最多可以有两个子节点，分别称为左子节点和右子节点。 4. D. 解析：二叉树的三种基本遍历方式是前序遍历、中序遍历和后序遍历，不包括逆序遍历这一说法。逆序遍历通常指的是对一个线性结构的倒序访问，不是二叉树的标准遍历方式。 5. B. 解析：在满二叉树中，每一层的节点数正好是上一层节点数的2倍。因此，第i层的节点数为2^(i-1) * 2 = 2^i。 6. A. 解析：树是一种典型的非线性数据结构，因为它允许一个节点有多个后继节点，形成了分支结构，不同于线性结构（如数组、链表）中每个元素只有一个后继和/或前驱。 7. B. 解析：树的度指的是树中节点子节点的最大数目。对于一颗非空树，其度指的是该树中度最大的节点的子节点个数。 8. B. 解析：在任何一棵二叉树中，叶子节点（度为0的节点）的数量总是比度为2的节点的数量多1。这是二叉树的一个重要性质，可以用归纳或数学证明来验证。 【巩固提升】 9. C. 解析：在树的先序遍历中，访问顺序是根节点 -> 左子树 -