4.1 树与二叉树（分层作业）信息技术浙教版2019选择性必修1

4.1树与二叉树 1课时（分层作业） 【基础达标】 1.树是一种 的数据结构，用它能很好地描述有 和 特性的数据集合。 2.树（Tree）可以描述为由 个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。 3.一棵具有n个节点的树，它有 条边。 4.树的一个节点所拥有的子树个数称为该节点的度（Degree），最大的节点的度称为 。 5.二叉树（Binary Tree）是一个具有 个节点的有限集合。当n=0时，二叉树是一棵 。 6.二叉树的重要特征：它的所有节点的度都 。 7.二叉树的第k层上最多有 个节点。 8.深度为k的二叉树最多有 个节点。 9.一棵度为3，深度为4的树，最多有（）个节点。 A.31 B.32 C.40 D.42 10.一棵高度为6的满二叉树中的节点数为（） A.31个 B.32个 C.63个 D.64个 【巩固提升】 1.某完全二叉树共有 300个节点，该二叉树的高度是（） A.8 B.9 C.10 D.11 2.已知一棵完全二叉树共有200个节点，下列说法正确的是（） A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 3.某二叉树如图所示，下列说法正确的是（） D E A B C F A.该二叉树是完全二叉树 B.该二叉树共有4个叶子节点 C.节点D、F都是节点B的孩子节点 D.该二叉树后序遍历的结果为DEBFCA 4.某二叉树的前序遍历结果为 ABC,若该二叉树不是满二叉树，则其后序遍历结果为（） A.ABC B.BCA C.CBA D.CAB 5.已知某二叉树的前序遍历为“ABCDEF"中序遍历为“BCAEFD”，则该二叉树的后序遍历为（） A.CBFEDA B.BCFEDA C.CBEFDA D.BCEFD 6.某二叉树用一维数组存储结构如下表所示: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H 下列有关该二叉树的说法正确的是（） A.该二叉树是完全二叉树 C.前序遍历为 A-B-D-F-G-C-H-E B.度为2的节点有3个 D.节点C是节点E 的父节点 7.用一维数组表示二叉树，如表所示: 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 下列有关该二又树的说法正确的是（） A.该树中共有4个叶子节点 B.该树是完全二叉树，其深度为4 C.该树的中序遍历为B-F-D-G-A-C-E D.该二叉树的结构图为(如图所示) 8.诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是（） A.树 B.栈 C.队列 D.链表 9.已知一棵完全二叉树共有200个节点，下列说法正确的是( ) A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 【链接高考】 1.某二叉树如下图所示,用数组来表示为（） D E A B C F G A. 0 1 2 3 4 5 6 7 8 A B C D E F G B. 0 1 2 3 4 5 6 7 8 A B C D E F G C. 0 1 2 3 4 5 6 7 8 A B C D E F G D. 1 2 3 4 5 6 7 8 9 A B C D E F G 2.已知一棵完全二叉树有8个叶子节点，下列说法正确的是（） A.该完全二叉树的高度可能为3 B.该完全二叉树的形态只有一种 C.该完全二叉树可能有1个度为1的节点 D.该完全二叉树有9个度为2的节点 3.某二叉树如下图所示： 用list表示该二叉树为（） A.['1,2,3',4,5'↓6',7'] B.[1,[2,4',5],['3',6','7']] C.[1,[2,[4],['5]],[3 ,[6’],['7']]] D.[1,[2,[4',None,None],[5',None,None]],[3',[6,None,None],[7,None,None]]] 4.一棵完全二叉树的第9层有200个叶结点,则该完全二叉树最多有 个结点。 5..若某完全二叉树包含200个结点,那么这颗完全二叉树中有 个叶子结点。 6.某完全二叉树，中序遍历结果为“甲乙丙丁”，则后序遍历结果是（） A.甲乙丁丙 B.丙乙甲丁 C.甲丁丙乙 D.乙丁丙甲 7.一个二叉树的叶子节点数为n,那么它的度为2的节点数为（） A.n+1 B.n-1 C.n D.无法确定 8.若一棵二叉树具有10个叶子节点,则树形结构度为2的节点数（） A.8 B.9 C.10 D.11 9.某二叉树的后序遍历序列为F-?-?-C-A-D，中序遍历序列为F-B-D-E-A-C，则其前序遍历序列为（） A.D-B-A-F-E-C B.D-B-F-A-E-C C.D-E-F-A-B-C D.D-E-A-F-B-C 10.已知二叉树T节点的前序遍历序列为A-B-D-E-F-G-C，中序遍历序列是D-B-F-E-G-A-C，则其后序遍历序列是（） A.F-D-G-E-B-C-A B.D-F-G-E-B-C-A C.B-F-D-G-B-C-A D.C-G-F-E-D-B-A 11.数学表达式： (7 - 5)*(1+2)可用二叉树表示，如图所示。则下列说法错误的是（） A.该二叉树是满二叉树 B.该二叉树的高度为3 C.通过后序遍历可求出该表达式的逆波兰式为7512- +* D.用列表方式存储该二叉树的具体结构为:[’*’，[’-’，[7, None, None],[5, None,None]],[’ +’，[1,None, None], [2, None, None]]] 12.如图所示，一个数学表达式可以用一棵表达式树来表示。下列关于该表达式树的描述，不正确的是（） A.该表达式树不是完全二叉树 B.若表达式树中只有四则运算,则对应的表达式树的每个节点都有两个子节点 C.表达式树的根节点左右子树深度差不会超过1 D.该表达式树对应的表达式为“(3+4)*6-8+4/(3*2)” 参考答案 【基础达标】 1.非线性、分支、层次。 2.n（n≥0）。 3.n-1。 4.树的度。 5.n（n≥0）、空树。 6.小于或者等于2。 7.2k–1（k≥1）。 8.2k–1（k≥1）。 9.【答案】C [解析]第一层为1个节点，第二层为3个节点，第三次为9个节点，第四层为27个节点。共计1+3+9+27=40故选:C。 10.【答案】C [解析]本题主要考查的是满二叉树的特点。一棵高度为6的满二叉树中的节点数为26-1个,即63个,因此,答案为C。 【巩固提升】 1.【答案】B [解析]本题考查的是二叉树的遍历。前序的规则就是根结点--->左子树--->右子树;中序遍历的规则是:左子树--->根结点--->右子树;后续就是左子树--右子树--->根结点。根节点:没有父节点的节点。度:节点下孩子节点的个数，树的度为节点度的最大值。分支节点:度不为0的节点。叶子结点:没有子节点的节点，树的终端。完全二叉树，高度是[log2N]+1，以2为底的对数取整后+1。故该完全二叉树的高度为h=log2300+1=9。故选:B。 2.【答案】D [解析]完全二叉树的性质可以知道:叶子节点肯定在最后两层上，所以先计算出树的深度为8，前七层一共有127个节点，所以第8层有73个节点且都为叶节点，第七层有64个节点，第八层的13个节点的父节点在第七层，占据37个，所以总共叶节点为:73+(64-37)=100个;根据二叉树的性质:对于一棵非空的二叉树，如果叶子节点数为n0，度为2的结点数为n2，则no=n2+1，所以度为2的节点有100-1=99个;所以选项D符合意。故选:D。 3.【答案】D [解析]选项A，该二叉树不是完全二叉树，如果是完全二叉树，则叶子节点尸的位置应该是C节点的左孩子节点。选项B，该二又树共有4个叶子节点，说法错误。共有3个叶子节点，分别是D、E、F。选项C，说法错误，F节点是节点C的孩子节点。故选:D。 4.【答案】CB A C B A C [解析]前序遍历结果为ABC，不是满二叉树，故其树可能为: B A C C B A 其后序遍历结果都为:CBA。故选:C。 5.【答案】A [解析]阅读题干根据前序遍历可知根节点为4，所以左子树为BC，右子树为EFD，最终推得后序遍历为CBFEDA。故选:A。 6.【答案】D [解析]由数组可知二叉树如图: B A C D E H F G 该二叉树不是完全二叉树;度为2的节点有2个;前序遍历为:ABDFGCEH;节点C是节点E的父节点。故选:D。 7.【答案】C [解析]观察图形可知，中序遍历的规则是:左子树--->根结点--->右子树所以该树的中序遍历为B-F-D-G-A-C-E选项C说法正确。故选:C。 8.【答案】A [解析]树状图是一种数据结构，它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。选项A符合题意。故选:A。 9.【答案】D [解析]完全二叉树的性质可以知道:叶子节点肯定在最后两层上，所以先计算出树的深度为8，前七层一共有127个节点，所以第8层有73个节点且都为叶节点，第七层有64个节点，第八层的13个节点的父节点在第七层，占据37个，所以总共叶节为:73+(64-37)=100个;根据二叉树的性质:对于一棵非空的二叉树，如果叶子节点数为n0，度为2的结点数为n2，则no=n2+1，所以度为2的节点有100-1=99个;所以选项D符合意。故选:D。 【链接高考】 1.【答案】C [解析]本题主要考查的是二叉树的数组表示，图中的二叉树为非完全二叉树,先将它补全为一棵完全二叉树,即补全C节点的右孩子节点,然后按照完全二叉树的方法来表示，因此,答案为C。 2.【答案】C [解析]已知一棵完全二叉树有8个叶子节点，可能是高度为4的满二叉树，也可能第五层还有一个叶子节点的完全二叉树，因此该完全二叉树的形态有两种;该完全二叉树可能有1个度为1的节点;该完全二叉树有7个度为2的节点。故选:C。 3.【答案】D [解析]本题主要考查的是二叉树的list 实现。空树用None表示,非空二叉树用三个元素的列表[根节点,左子树节点,右子树节点],左右子树也采用相同的方式处理。因此该二叉树用list表示为[1',[['2',[['4',None,None]，[['5',None,None]]，[['3',[['6',None,None]，[['7',None,None]]]，答案为D。 4.【答案】623 [解析]完全二叉树叶子结点可以出现在最下两层设根结点层次为1,完全二叉树第9层有200个叶子,第9层结点个数最多就是满二叉树,共29-=256个结点,因此第9层并不都是叶子考虑到是计算最多结点,因此,可以认为第9层不是最下层,也就是说该完全二叉树的高度为10，第9层剩下的256-200=56个结点都是度为2,这样第10层的结点个数是2x56=112所以结点总数=1+2+4+8+16+32+64 + 128+256 +112= (29-1)+112=511+112=623。 5.【答案】100 [解析]完全二叉树除最后一层，其他层都是满结点的。所以这里总结点200个，这里是偶数，可以判断度为1的结点是1个。根据二叉树性质n0=n2+1;叶子结点数量等于度为2的结点数+1 n0 + n1 + n2=200 n0+n1+n0-1=200; 2n0=201-n1=200(完全二叉树度为1的结点个数要么1，要么0.叶子结点数为整数，这里也可以推断出度为1的结点个数是1) n0=100 叶子结点数是100。 6.【答案】A [解析]依据题意可知二叉树如下: 故后序遍历结果是:甲乙丁丙。故选:A。 7.【答案】B [解析]二叉树有一个性质:任意一个二叉树其度为0的节点数比度为2的节点数多1,因此答案是B项。 8.【答案】B [解析]根据二叉树的性质,任意一棵二叉树中,若度为2 节点数量为n2,叶子节点数为n0,则n2=n2+1,故题目中度为2的节点数是9个。 9.【答案】B [解析]题干提供了后序遍历可以得到根节点，在通过中序遍历得到FB为左子树，ACE为右子树，结合中序和后序遍历可知，左子树中B为根节点，右子树中，A为根节点，E为左节点由此可以得到前序遍历为D-B-F-A-E-C。故选:B。 10.【答案】B [解析]二叉树的先序遍历中第一个为根节点，中序遍历中根节点位置的左右分别为左右子树，根据这个关系，我们可以还原出这个二叉树的结构，然后写出后序遍历为D-F-G-E-B-C-A。故选:B。 11【答案】C [解析]一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树，所以该二叉树为满二叉树;二叉树的高度是垂直方向上树的长度的量度，所以该二叉树的高度为3;通过后序遍历可求出该表达式的逆波兰式为75-12+*;用列表方式存储该二叉树的具 体结构为:[’*’，[’-’，[7, None, None],[5, None,None]],[’ +’，[1,None, None], [2, None, None]]]，所以选项C说法错误。故选: C。 12.【答案】C [解析]表达式树根节点左右子节点的深度差可以超过1，*节点的左右子树深度分别为3和1。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$