(
课件网) 第四章 树 验收卷(三) 树 (考试时间40分钟 满分50分) 一、选择题(本题共14小题，每小题2分，共28分) 1.树中所有节点的度等于( ) C 解析 本题主要考查的是节点的度。树中节点的度是指该节点的后继节点数，两个节点间有一条边，即节点的度是从该节点出发的边数。因此，所有节点的度等于所有节点数减1，故答案为C。 A.所有节点数 B.所有节点数加1 C.所有节点数减1 D.所有节点数加2 C 2.一棵高度为6的满二叉树中的节点数为( ) 解析 本题主要考查的是满二叉树的特点。一棵高度为6的满二叉树中的节点数为26－1个，即63个，因此，答案为C。 A.31个 B.32个 C.63个 D.64个 B 3.某树的结构如下，下列说法正确的是( ) 解析 本题考查树的性质。A选项数的度取决于节点的最大度数，因此该树的度为3。 A.该树的度为4 B.该树的高度为4 C.该树的叶子节点为3个 D.节点F和G是兄弟节点 A 4.一棵有n(n>0)个节点的二叉树，其节点为0度或2度，则此树的最大高度是( ) 解析 本题考查二叉树基本性质。该二叉树的节点的度都为0或2，即除根节点外，其每个节点都有一个兄弟节点。题目要求树的最大高度，每层就只有2个节点(除了根节点)，若总节点数加上1，相当于令第1层也变成两个节点，那么总层数就是(n＋1)∥2。 A.(n＋1)∥2 B.n∥2 C.(n－1)∥2 D.int(log2n＋1) C 5.已知一棵完全二叉树有8个叶子节点，下列说法正确的是( ) 解析 本题考查树的性质。根据树的性质，2度节点个数为叶子节点个数减1，因此2度节点有7个。由于是完全二叉树，1度节点的个数为0或1，因此总共节点数为15或16个。A选项根据总共节点数，可知该树可能是3层，也可以是4层。B选项当总节点是3层时，是一棵满二叉树，当节点为16时，在4层下有一个节点。C选项当总节点为16时，有一个1度节点。D选项2度节点个数为7个。 A.该完全二叉树的高度可能为3 B.该完全二叉树的形态只有一种 C.该完全二叉树可能有1个度为1的节点 D.该完全二叉树有9个度为2的节点 C 6.如图所示，将二叉树A的根节点与二叉树B的根节点连接，使得二叉树A成为二叉树B的左子树，合并为一棵新的二叉树C。下列说法中正确的是 ( ) 解析 本题考查二叉树的性质和遍历。新二叉树高度为4；叶子节点数量为4，是一棵完全二叉树；中序遍历的结果为84251637，不是一个有序序列。 A.二叉树C的高度为3 B.二叉树C的叶子节点数量为3 C.二叉树C是一棵完全二叉树 D.二叉树C中序遍历的结果是一个有序序列 D A.二叉树的数据元素之间呈非线性关系 B.二叉树的第 k 层上最多有2k－1(k≥1)个节点 C.由前序遍历和中序遍历序列能唯一确定一棵二叉树 D.具有 100 个节点的完全二叉树有 50 个度为 2 的节点 解析 本题考查树的性质。A选项树表现一种层次性的非线性关系。D选项设二叉树0度、1度和2度的节点个数分别为t0，t1，t2，有等式t0＋t1＋t2＝100和t0＝t2＋1成立，代入可得t2＋1＋t1＋t2＝100，且完全二叉树1度节点个数为0或1，因此t2值为49。 A 8.某二叉树如图所示，该二叉树的中序遍历序列是( ) 解析 中序遍历的每棵子树均为左根右。 A.BIGDHAECF B.IGHDBEFCA C.ABDGIHCEF D.BDGHIACEF C 9.对于如图所示的二叉树，下列说法正确的是 ( ) 解析 本题考查二叉树相关知识。A选项叶子节点有7，9，15，共3个。B选项完全二叉树要求叶子节点从右开始，且最多只出现在最下面 2 层。C 正确，前序遍历时 2－5－7－8－9－10－13－15，是一个递增序列。D选项用数组表示是[2，5，10，7，8，None，13，None，None，9，None，None，None，None，15]. A.叶子节点有 4 个 B.是完全二叉树，树的高度为 4 C.前序遍历的结果是一个递增序列 D.可以使用数组[2，5，10 ... ...
