第四章 树（单元测试）信息技术浙教版2019选择性必修1

第四章 树 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 填空题 总计 题数 20 5 25题 分数 60 40 100分 得分 一、单项选择题（每题3分，共60分） 1.某完全二叉树共有 300个节点，该二叉树的高度是（） A.8 B.9 C.10 D.11 2.某二叉树如图所示，下列说法正确的是()D E A B C F A.该二叉树是完全二叉树 B.该二叉树共有4个叶子节点 C.节点D、F都是节点B的孩子节点 D.该二叉树后序遍历的结果为DEBFCA 3.某二叉树用一维数组存储结构如下表所示: 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 的父节点 4.诸葛亮家族的部分家谱如图所示,和家谱图结构相似的数据结构是() A.树 B.栈 C.队列 D.链表 5..已知一棵完全二叉树共有200个节点，下列说法正确的是( ) A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 6.若一棵二叉树具有10个叶子节点,则树形结构度为2的节点数() A.8 B.9 C.10 D.11 7.某二叉树的后序遍历序列为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 8.已知二叉树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 9.某二叉树如下图所示,用数组来表示为() 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 10.某二叉树的树形结构如第8题图所示，其后序遍历结果为“物技化数英语”，则中序遍历结果为() A.语数英物化技 B.物数技化语英 C.语数物化技英 D.化物技英数语 11.某二叉树的前序遍历为+*a-bc/df，中序遍历为a*b-c+d/f，下列说法正确的是（   ） A．该二叉树的叶子节点有2个 B．该二叉树为完全二叉树 C．该二叉树的后序遍历是abc-*df/+ D．若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为4 12.已知某二叉树的前序遍历结果为ABCDEF中序遍历结果为CBDAEF，则下列说法正确的是() A.其后序遍历结果为DCBFEA B.该二叉树为完全二叉树 C.该二叉树深度为3，叶子节点数为3 D.该二叉树用一维数组实现需要6个节点的存储空间才能表示 13.某二叉树用一维数组来表示如表所示。该二叉树从根节点开始，按照从上到下，从左到右的顺序依次用A-H字母表示，该二叉树的中序遍历为() 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 元素 A B C D E F G H A.DBGEACFH B.DBGEACHF C.DBEGACHF D.ABCDEFGH 14.若一棵二叉树的中序遍历序列为BIGDHAECF，后序遍历序列为IGHDBEFCA，则该二叉树的前序遍历序 列为（） A.ABCDEFCHI B.ABDCHICEF C.ABDHGICEF D.ABDGIHCEF 15.完全二叉树的节点个数为4*N+3,则它的叶子节点个数为 A.2*N B.2*N-1 C. 2*N+1 D.2*N+2 16.下列关于抽象数据类型的说法,不正确的是 A,程序设计语言的一个内置类型可以看作是一个抽象数据类型 B.抽象数据类型的定义仅取决于它的一组逻辑特性,与其在计算机内部的表示与实现无关 C.定义一个抽象数据类型,只需要清浙地表达出各方面的形式要求即可 D.使用抽象数据类型编写的程序结构清晰、层次分明,也便于程序的移植和重用 17.有如下自定义函数: def fun(a): s=0 for i in a: s+=i return s 则 Python 内置函数中,与自定义函数fun(a)的功能相似的是（） A.len( ) C.max( ) B.sum( ) D.min( ) 18.下列是一个简单的 ADT: class Sstring: def init_(self,str1): self.ss = strl def substr(self,a,b): return self.ss[a-l:b] def concat(self,str2): return self.ss + str2 sstrl=Sstring("Python" ) print(sstrl.substr(2,4)) print(sstrl.concat(" is so easy!")) 下列有关该抽象数据类型(ADT)实例的说法中,不正确的是（） A.Sstring 为抽象数据类型名 B.sstrl为 Sstring 类的一个对象 C.执行代码“print(sstr1.substr(2,4))”,输出结果为“yth” D,执行代码“print(sstrl.concat("is so easy!"))”,输出结果为“yth is so easy!” 19.定义一个简单的ADT,部分代码如下: class mystring: def init_(self,ssepl): self.ss=ssepl def substr(self,a,b): return self.ss[a:b+1] def concat(self,ssep2): return self.ss+ssep2 s=mystring("Beautiful") print(s.substr(1,5)) print(s.concat("flower!")) 下列关于该抽象数据类型实例的说法，不正确的是() A.mystring为抽象数据类型名 B.s为mystring类的一个对象 C.执行语句“print(s.substr(1,5))”,输出结果为 Beauti D.执行语句“print(s.concat("flower!"))”,输出结果为Beautifulflower! 20.创建一个简单的ADT，如下所示： classNd( ): def _init_(self,data): self.data=data def judge(self): if self.data%5==0: print(self.data,“是5的倍数”) else: print(self.data,“不是5的倍数”) #创建实例 my_data=Nd(10) my_data.judgeodd( ) 下列有关该抽象数据类型（ADT）实例的说法中，不正确的是（ ） A.创建的类名称为Nd B.def judge(self)的功能是定义judge函数 C.程序代码执行后的结果为“10是5的倍数” D.my_data为Nd类的一个对象 二、填空题（每空2分，共计40分） 1.一棵完全二叉树的第9层有200个叶结点,则该完全二叉树最多有 个结点。 2.已知某二叉树的前序遍历为“ABCDEF"中序遍历为“BCAEFD”，则该二叉树的后序遍历为 。 3.某二叉树的前序遍历结果为 ABC,若该二叉树不是满二叉树，则其后序遍历结果为 。 4.观察如图所示的树形结构示意图,请回答下列问题: (1)该树共有 个节点， 条边。 (2)根节点的名称是 ，它有 个孩子节点,节点E (选填：是/不是)根节点的孩子节点。 (3)节点A和节点B的度分别是 ，整棵树的度是 。 (4)该树的分支节点的数量是 ，叶子节点的数量是 。 (5)节点C的层数是 ，树的深度是 。 (6)节点D的父节点是 ，兄弟节点是 ，孩子节点是 。 5.下列是一个加减乘除四则运算的ADT,请回答程序后的问题: class operator(): def init_( self,datal ,data2 ,ch): self.datal = datal self.data2 = data2 ① def cal( self): if self.ch= ="+": c=self.data1+self.data2 print( self.datal ,"+" ,self.data2 ,"=" ,c) if self.ch= ="_": c =self.datal-self.data2 print(self.datal ,"-" ,self.data2 ,"=",e) if self.ch= =" * ": c=self.datal* self.data2 print( self.datal ," * ",self.data2 ,"=",c) if self.ch=="/". if self.data2!=0: ② print(self.datal ,"/",self.data2,"=",c ) else: print("分母不能为 0”) #创建实例: my_operator=operator( 2,6," *" ) my_operator.cal() （1）程序运行后,输出的结果是 。 （2）请在程序划线处填人合适的语句。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$ 第四章 树 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 填空题 总计 题数 20 5 25题 分数 60 40 100分 得分 一、单项选择题（每题3分，共60分） 1.某完全二叉树共有 300个节点，该二叉树的高度是（） A.8 B.9 C.10 D.11 【答案】B [解析]本题考查的是二叉树的遍历。前序的规则就是根结点--->左子树--->右子树;中序遍历的规则是:左子树--->根结点--->右子树;后续就是左子树--右子树--->根结点。根节点:没有父节点的节点。度:节点下孩子节点的个数，树的度为节点度的最大值。分支节点:度不为0的节点。叶子结点:没有子节点的节点，树的终端。完全二叉树，高度是[log2N]+1，以2为底的对数取整后+1。故该完全二叉树的高度为h=log2300+1=9。故选:B。 2.某二叉树如图所示，下列说法正确的是()D E A B C F A.该二叉树是完全二叉树 B.该二叉树共有4个叶子节点 C.节点D、F都是节点B的孩子节点 D.该二叉树后序遍历的结果为DEBFCA 【答案】D [解析]选项A，该二叉树不是完全二叉树，如果是完全二叉树，则叶子节点尸的位置应该是C节点的左孩子节点。选项B，该二又树共有4个叶子节点，说法错误。共有3个叶子节点，分别是D、E、F。选项C，说法错误，F节点是节点C的孩子节点。故选:D。 3.某二叉树用一维数组存储结构如下表所示: 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 的父节点 【答案】D [解析]由数组可知二叉树如图: B A C D E H F G 该二叉树不是完全二叉树;度为2的节点有2个;前序遍历为:ABDFGCEH;节点C是节点E的父节点。故选:D。 4.诸葛亮家族的部分家谱如图所示,和家谱图结构相似的数据结构是() A.树 B.栈 C.队列 D.链表 【答案】A [解析]树状图是一种数据结构，它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。选项A符合题意。故选:A。 5..已知一棵完全二叉树共有200个节点，下列说法正确的是( ) A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 【答案】D [解析]完全二叉树的性质可以知道:叶子节点肯定在最后两层上，所以先计算出树的深度为8，前七层一共有127个节点，所以第8层有73个节点且都为叶节点，第七层有64个节点，第八层的13个节点的父节点在第七层，占据37个，所以总共叶节点为:73+(64-37)=100个;根据二叉树的性质:对于一棵非空的二叉树，如果叶子节点数为n0，度为2的结点数为n2，则no=n2+1，所以度为2的节点有100-1=99个;所以选项D符合意。故选:D。 6.若一棵二叉树具有10个叶子节点,则树形结构度为2的节点数() A.8 B.9 C.10 D.11 【答案】B [解析]根据二叉树的性质,任意一棵二叉树中,若度为2 节点数量为n2,叶子节点数为n0,则n2=n2+1,故题目中度为2的节点数是9个。 7.某二叉树的后序遍历序列为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 【答案】B [解析]题干提供了后序遍历可以得到根节点，在通过中序遍历得到FB为左子树，ACE为右子树，结合中序和后序遍历可知，左子树中B为根节点，右子树中，A为根节点，E为左节点由此可以得到前序遍历为D-B-F-A-E-C。故选:B。 8.已知二叉树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 【答案】B [解析]二叉树的先序遍历中第一个为根节点，中序遍历中根节点位置的左右分别为左右子树，根据这个关系，我们可以还原出这个二叉树的结构，然后写出后序遍历为D-F-G-E-B-C-A。故选:B。 9.某二叉树如下图所示,用数组来表示为() 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 【答案】C [解析]本题主要考查的是二叉树的数组表示，图中的二叉树为非完全二叉树,先将它补全为一棵完全二叉树,即补全C节点的右孩子节点,然后按照完全二叉树的方法来表示，因此,答案为C。 10.某二叉树的树形结构如第8题图所示，其后序遍历结果为“物技化数英语”，则中序遍历结果为() A.语数英物化技 B.物数技化语英 C.语数物化技英 D.化物技英数语 【答案】B [解析]后续就是左子树--->右子树--->根结点，所以根节点为语，可排除选项AC，由于右子树只有一个节点，所以为英，可排除选项D。故选:B。 11.某二叉树的前序遍历为+*a-bc/df，中序遍历为a*b-c+d/f，下列说法正确的是（   ） A．该二叉树的叶子节点有2个 B．该二叉树为完全二叉树 C．该二叉树的后序遍历是abc-*df/+ D．若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为4 【答案】C [解析]本题主要考查二叉树的遍历。由前序遍历以及中序遍历，可画出该二叉树，由二叉树可知，该二叉树的叶子节点有5个;不是完全二叉树;该二叉树的后序遍历是abc-*df+;若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为3.0，故本题选C选项。 12.已知某二叉树的前序遍历结果为ABCDEF中序遍历结果为CBDAEF，则下列说法正确的是() A.其后序遍历结果为DCBFEA B.该二叉树为完全二叉树 C.该二叉树深度为3，叶子节点数为3 D.该二叉树用一维数组实现需要6个节点的存储空间才能表示 【答案】C [解析]某二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBDAEF，某其后序遍历结果为CBDFEA;该二叉树不是完全二叉树;该二叉树深度为3，叶子节点数为3，所以选项C符合题意。故选:C。 13.某二叉树用一维数组来表示如表所示。该二叉树从根节点开始，按照从上到下，从左到右的顺序依次用A-H字母表示，该二叉树的中序遍历为() 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 元素 A B C D E F G H A.DBGEACFH B.DBGEACHF C.DBEGACHF D.ABCDEFGH 【答案】A [解析]中序遍历的顺序为左子树，根节点，右子树，所以中序遍历为DBGEACFH，所以选项A符合题意。 故选:A。 14.若一棵二叉树的中序遍历序列为BIGDHAECF，后序遍历序列为IGHDBEFCA，则该二叉树的前序遍历序 列为（） A.ABCDEFCHI B.ABDCHICEF C.ABDHGICEF D.ABDGIHCEF 【答案】D [解析]后序遍历为IGHDBEFCA可以得到根节点为A;中序遍历可知左子树为BIGDH，右子树为BCF，依次类推可以得到该二叉树的前序遍历为ABDGIHCEF。故选:D。 15.完全二叉树的节点个数为4*N+3,则它的叶子节点个数为 A.2*N B.2*N-1 C. 2*N+1 D.2*N+2 【答案】D [解析]完全二又树的节点个数为4"N十3,则最后一个叶子节点的编号为 4*N+3,其父节点的编号为2*N十1,即度为2的节点数为2*N+1,因此它的叶子节点个数为4*N+3-(2*N+1)=2"N+2,故答案为D。 16.下列关于抽象数据类型的说法,不正确的是 A,程序设计语言的一个内置类型可以看作是一个抽象数据类型 B.抽象数据类型的定义仅取决于它的一组逻辑特性,与其在计算机内部的表示与实现无关 C.定义一个抽象数据类型,只需要清浙地表达出各方面的形式要求即可 D.使用抽象数据类型编写的程序结构清晰、层次分明,也便于程序的移植和重用 【答案】C [解析]定义一个抽象数据类型,不仅要清晰地表述出各方面的形式要求,还要清晰地表述出功能要求,因此答案为 C。 17.有如下自定义函数: def fun(a): s=0 for i in a: s+=i return s 则 Python 内置函数中,与自定义函数fun(a)的功能相似的是（） A.len( ) C.max( ) B.sum( ) D.min( ) 【答案】B [解析]自定义函数fun(a)的功能是计算并返回列表a的元素之和,与之功能相似的是内置函数 sum()。 18.下列是一个简单的 ADT: class Sstring: def init_(self,str1): self.ss = strl def substr(self,a,b): return self.ss[a-l:b] def concat(self,str2): return self.ss + str2 sstrl=Sstring("Python" ) print(sstrl.substr(2,4)) print(sstrl.concat(" is so easy!")) 下列有关该抽象数据类型(ADT)实例的说法中,不正确的是（） A.Sstring 为抽象数据类型名 B.sstrl为 Sstring 类的一个对象 C.执行代码“print(sstr1.substr(2,4))”,输出结果为“yth” D,执行代码“print(sstrl.concat("is so easy!"))”,输出结果为“yth is so easy!” 【答案】D [解析]执行代码“print(sstrl.concat("is soeasy!"))”,输出结果为“Python is so easy!”,因此,答案为 D。 19.定义一个简单的ADT,部分代码如下: class mystring: def init_(self,ssepl): self.ss=ssepl def substr(self,a,b): return self.ss[a:b+1] def concat(self,ssep2): return self.ss+ssep2 s=mystring("Beautiful") print(s.substr(1,5)) print(s.concat("flower!")) 下列关于该抽象数据类型实例的说法，不正确的是() A.mystring为抽象数据类型名 B.s为mystring类的一个对象 C.执行语句“print(s.substr(1,5))”,输出结果为 Beauti D.执行语句“print(s.concat("flower!"))”,输出结果为Beautifulflower! 【答案】C [解析]执行语句“print(s.substr(1,5))”,取得字符串s中[1:5+1]的子串，左闭右开区间，字符串的索引从0开始,输出结果为eauti。 20.创建一个简单的ADT，如下所示： classNd( ): def _init_(self,data): self.data=data def judge(self): if self.data%5==0: print(self.data,“是5的倍数”) else: print(self.data,“不是5的倍数”) #创建实例 my_data=Nd(10) my_data.judgeodd( ) 下列有关该抽象数据类型（ADT）实例的说法中，不正确的是（ ） A.创建的类名称为Nd B.def judge(self)的功能是定义judge函数 C.程序代码执行后的结果为“10是5的倍数” D.my_data为Nd类的一个对象 【答案】B [解析]本题主要考查的是抽象数据类型(ADT)的组成。defjudge(self)的功能是定义judge操作,而不是函数。因此,不正确的是 B。 二、填空题（每空2分，共计40分） 1.一棵完全二叉树的第9层有200个叶结点,则该完全二叉树最多有 个结点。 【答案】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。 2.已知某二叉树的前序遍历为“ABCDEF"中序遍历为“BCAEFD”，则该二叉树的后序遍历为 。 【答案】CBFEDA [解析]阅读题干根据前序遍历可知根节点为4，所以左子树为BC，右子树为EFD，最终推得后序遍历为CBFEDA。 3.某二叉树的前序遍历结果为 ABC,若该二叉树不是满二叉树，则其后序遍历结果为 。 【答案】CBA [解析]前序遍历结果为ABC，不是满二叉树，故其树可能为: 其后序遍历结果都为:CBA。 4.观察如图所示的树形结构示意图,请回答下列问题: (1)该树共有 个节点， 条边。 (2)根节点的名称是 ，它有 个孩子节点,节点E (选填：是/不是)根节点的孩子节点。 (3)节点A和节点B的度分别是 ，整棵树的度是 。 (4)该树的分支节点的数量是 ，叶子节点的数量是 。 (5)节点C的层数是 ，树的深度是 。 (6)节点D的父节点是 ，兄弟节点是 ，孩子节点是 。 【答案】(1)10；9(2)A；3；不是(3)3、3；3 (4)4；6(5)2；3(6)A；BC；IJ [解析](1)该树共有10个节点,9条边。(2)根节点的名称是A,它共有BC、D3个孩子节点,因为节点E与 节点A没有直接相连,故节点E不是根节点A的孩子节点,但可以称节点E为节点A的子孙节点,相应地可以称节点A为节点E的祖先节点。(3)节点A和节点B的度均为3.树的度也是3。(4)树的分支节点为节点A、B.CD,共4个;叶子节点为节点E、FGHIJ,共6个。(5)节点C的层数是2,树的深度是3。(6)节点D的父节点是A.兄弟节点是B和C,孩子节点是1和J。 5.下列是一个加减乘除四则运算的ADT,请回答程序后的问题: class operator(): def init_( self,datal ,data2 ,ch): self.datal = datal self.data2 = data2 ① def cal( self): if self.ch= ="+": c=self.data1+self.data2 print( self.datal ,"+" ,self.data2 ,"=" ,c) if self.ch= ="_": c =self.datal-self.data2 print(self.datal ,"-" ,self.data2 ,"=",e) if self.ch= =" * ": c=self.datal* self.data2 print( self.datal ," * ",self.data2 ,"=",c) if self.ch=="/". if self.data2!=0: ② print(self.datal ,"/",self.data2,"=",c ) else: print("分母不能为 0”) #创建实例: my_operator=operator( 2,6," *" ) my_operator.cal() （1）程序运行后,输出的结果是 。 （2）请在程序划线处填人合适的语句。 【答案】(1)2*6=12 (2)①self.ch=ch ②c = self.dalal/self.data2 [解析]本题考查定义一个抽象数据类型。(1)根据语句 my_operator=operator(2,6,"≈")可知,数据 datal 和data2 进行乘法运算,因此输出结果为2*6=12。(2)划线①处的语句功能是初始化属性c,因此填人的代码为self.ch=ch;划线②处的语句表示 datal 和 data2 进行除法运算,结果存储在变量c中。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$