第四章 树 课时1 树与二叉树 一、基础巩固 1.树最适合用来表示下面哪种类型的数据( ) A.有序数据元素 B.无序数据元素 C.元素之间无联系的数据 D.元素之间具有分支层次关系的数据 2.在一棵树中，没有子节点的节点是( ) A.父节点 B.叶节点 C.根节点 D.空节点 3.具有3个节点的二叉树形态有5种，可推测出具有4个节点的二叉树形态共有( ) A.13种 B.14种 C.15种 D.16种 4.下列有关二叉树的说法，正确的是( ) A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.至少有一个节点的度为2 D.任一节点的度均为2 5.一棵度为3，深度为4的树的节点个数至多为( ) A.31 B.32 C.40 D.42 6.在一棵度为2的树中，度为2的节点数为15，度为1的节点数为30，则叶子节点(度为0的节点)的个数为( ) A.15 B.16 C.17 D.47 7.一棵高度为h的满二叉树，从上到下，同层从左到右的次序从1开始连续编号，若某子节点的右孩子的编号为x(x>1)，则该子节点的编号为( ) A.2*x＋1 B.2*x－1 C.x/2 D.x∥2 8.已知一棵二叉树有13个节点，树中度为1的节点数为2，则该树度为2的节点数为( ) A.4 B.5 C.6 D.11 9.下列关于二叉树的说法中，正确的是( ) A.完全二叉树一定是满二叉树 B.二叉树的深度是指二叉树中最大节点的度 C.二叉树的子树没有左右之分，左右子树的次序可以交换 D.二叉树中所有节点的度都小于或等于2 10.有一棵树如图所示，回答下面的问题： 这棵树的根节点是①_____，叶子节点个数是②_____；节点E的度是③_____，节点E的孩子节点是④_____；节点E的父节点是⑤_____；这颗树的度为⑥_____；这棵树的深度是⑦_____。 二、能力提升 11.根节点的深度为1，则深度为5的完全二叉树中节点数最少为( ) A.9 B.15 C.16 D.31 12.在一棵满二叉树中，若有N个叶节点，则该满二叉树的节点总数为( ) A.N个 B.2N个 C.2N－1个 D.2N＋1个 13.完全二叉树共有2*n－1个节点，则它的叶节点数为( ) A.n－1 B.n C.2*n D.2*n－1 14.假设完全二叉树的树根为第1层，树中第10层有5个叶子节点，则完全二叉树最多节点个数是( ) A.2047 B.2048 C.2037 D.2038 课时1 树与二叉树 1.D [树能很好地描述有分支和层次特性的数据集合。] 2.B [在树中，没有子节点的节点称为叶节点，也称终端节点，因此答案为B。] 3.B [可先画出3个节点的二叉树形态，然后求得二叉树的形态总数，具有4个节点的二叉树形态共有14种，因此，答案为B。] 4.B [本题主要考查的是二叉树的度。二叉树的度为最大节点的度，二叉树中的节点的度最大为2，最小为0(叶节点)，因此正确答案为B。] 5.C [度为3的树，即每个分支节点最多有3个孩子节点，按照每个分支节点均有3个孩子节点，即每一层都是上一层节点数的3倍，则前4层的节点数应分别为1，3，9，27，共40个节点，答案为C。] 6.B [设度为0的节点数为n0，总节点数为n，则由树中总结点数、不同度数的节点个数及总边数之间的关系可以列出以下两个等式：(1)n＝n0＋n1＋n2＝n0＋30＋15；(2)n－1＝1*n1＋2*n2＝30＋30，可得n＝61，n0＝16，答案为B。] 7.D [在一棵满二叉树中，若父节点的编号为x，则它的左孩子的节点编号为2*x，右孩子的节点编号为2*x＋1，同理，若某子节点的右孩子的编号为x，则该子节点的编号为x∥2，因此答案为D。] 8.B [本题考查二叉树性质。根据二叉树的性质，n0＝n2＋1，n＝n0＋n1＋n2，可以推出n2＝5。] 9.D [满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树，因此A选项错误；二叉树的度是指二叉树中最大节点的度，而二叉树的深度是指二叉树中节点的最大层数，因此B选项错误；二叉树的子树有左右之分，且左右子树的次序不能颠倒，因此C选项错误；二叉树中所有节点的度都小于或等于2，因此答案为D。] 10.①A ... ...
~~ 您好，已阅读到文档的结尾了 ~~
