第四章 树 2023-2024学年高中信息技术浙教版（2019）选修1

第四章树同步作业2023—2024学年高中信息技术浙教版（2019）选修1 一、选择题 1．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（   ） A．250 B．500 C．254 D．501 2．某二叉树中序遍历为ABCDEF，则下列不可能是此二叉树的是（   ） A． B． C． D． 3．用一维数组表示二叉树，如下表所示： 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．该二叉树的结构图为（如图所示） 4．某二叉树的中序遍历序列为ABCDEFG，后序遍历序列为ACBFEGD，下列说法正确的是（   ） A．前序遍历序列为DBACGFE B．节点G为节点E的父节点 C．该二叉树有两个叶子节点 D．节点A与节点F为同一层 5．一个数学表达式可以用一棵表达式树来表示，而一棵二叉树可以用一维数组表示。有一棵表达式树用一维数组表示如下。下列有关该表达式树的说法正确的是（   ） A．该表达式树是一棵完全二叉树 B．该表达式树的左右子树深度相差为1 C．该表达式树的叶子结点有4 D．该表达式树中序遍历的结果为4*6/8-4 6．已知一棵二叉树的前序遍历为ABDECFG，中序遍历为DBEAFCG，则该二叉树的后序遍历序列为(　　) A．DEBAFGC B．DEBFGCA C．DBEGFCA D．DEBFGCA 7．某二叉树的树形结构如图所示，后序遍历结果为stnaqm，则该二叉树的中序遍历结果是（   ） A．mntsqa B．ntsmqa C．nstmqa D．nstmaq 8．如图所示二叉树的前序遍历序列是（   ） A． A-B-C-D-E-G-H-F-I B．A-B-D-E-G-H-C-F-I C．D-B-E-G-H-A-C-F-I D．B-D-G-H-E-A-F-I-C 9．下列关于抽象数据类型的说法，不正确的是（   ） A．程序设计语言的一个内置类型可以看作是一个抽象数据类型 B．抽象数据类型的定义仅取决于它的一组逻辑特性，与其在计算机内部的表示与实现无关 C．定义一个抽象数据类型，只需要清晰地表达出各方面的形式要求 即可 D．使用抽象数据类型编写的程序结构清晰、层次分明，也便于程序的移植和重用 10．有如图所示的二叉树，下列说法正确的是（ ） A．该树度为2的节点数为1 B．该树的深度为3 C．该树的中序遍历序列为B-A-C-E-D-F D．该树可以用一维数组['A','B','C','','D','','E','F']存储 11．某二叉树前序遍历的结果为“大好河山”，则中序遍历的结果不可能是（   ） A．大好河山 B．河山好大 C．好山大河 D．山河好大 12．如图所示的二叉树，其节点的中序遍历的序列为（  ） A．ABCDEFG B．GDBEACF C．GDEBFCA D．ABDGECF 13．下列二叉树中，中序遍历结果为回文的是（   ） A． B． C． D． 14．某二叉树的结构如下，下列说法错误的是（   ） A．该二叉树不是完全二叉树 B．其中序遍历为DBGEHIFCA C．该二叉树的深度为4 D．叶子节点G和H不属于兄弟节点 15．已知某二叉树的前序遍历序列为ABCDEF，中序遍历序列为BCAEFD，则该二叉树的后序遍历序列为（    ） A．CBFEDA B．BCDEFA C．CBEFDA D．BCFEDA 16．有一棵完全二叉树，已知其中序遍历结果是CADGBEIHJ，则其前序遍历结果应该为（   ） A．ABCDEFGHI B．EGACDBHIJ C．EACGBDIHJ D．EACDBHIJ 17．某二叉树的部分树形结构如图所示，其前序遍历结果为ABCDEF，下列说法正确的是（   ） A．该二叉树的深度一定是3 B．节点C和节点D一定都是叶子节点 C．节点F在该二叉树的左子树中 D．该二叉树的后序遍历可能是CDBFEA 18．已知7个结点的二叉树的前序遍历是 A B D E F C G（字母为结点的编号，以下同），中序遍历是D B F E A G C，则该二叉树的后序遍历是（   ） A．D F E B G C A B．D F E B A C G C．F B C G E D A D．D F E C A G B 19．某完全二叉树包含5个节点，其根节点在后序遍历序列、中序遍历序列中的位置序号分别记为x，y，则x-y的值为（   ） A．0 B．1 C．2 D．3 20．某二叉树按从上而下、自左往右的顺序，对节点进行编号，数组存储示意图如下： 0 1 2 3 4 5 6 7 8 A B C D E F G 下列关于该二叉树，说法正确的是（   ） A． 该二叉树的叶子节点有4个，分别是C，E，F，G B．该二叉树后序遍历结果为FGDBECA C．该二叉树共有4层，E和F位于同一层 D．该二叉树共有3对兄弟节点 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题考查完全二叉树。解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。故选择D。 2．C 【详解】本题考查的是二叉树遍历。中序遍历的规则：（1）中序遍历左子树（2）访问根节点（3）中序遍历右子树。选项C的中序遍历为：ACBDEF。故本题应选C。 3．C 【详解】 本题考查二叉树相关内容。由二叉树存储结构可以画出此二叉树的形态：。根据图可知共有3个叶子节点；此树的深度为4；是一棵不规则的二叉树；中序遍历为BFDGACE。故本题答案是C选项。 4．B 【详解】本题考查的是二叉树。依据题意可画出如下的数： 由图可知，前序遍历序列为DBACGEF，节点G为节点E的父节点，该二叉树有3个叶子节点，节点A与节点F不在同一层。故本题应选B。 5．C 【详解】本题考查的是二叉树相关知识。本题考查二叉树相关内容。由该二叉树的一维数组表示可知，该二叉树结构如图所示 故选C。 6．B 【详解】本题主要考查二叉树的遍历。根据前序遍历为ABDECFG，中序遍历为DBEAFGC可画出该二叉树如下： ，则该二叉树的后序遍历序列为DEBFGCA，故本题选B选项。 7．C 【详解】本题考查树的遍历。根据后序遍历stnaqm和图示，可知根节点为m。左子树3个节点nst，右子树2个aq。后序遍历可知右子树的根节点为q，并且右子树没有左节点，有右节点，故中序遍历qa。后序遍历可知左子树根节点n，没有左节点，左子树有右节点，右节点有左节点，故中序遍历nst。中序遍历为nstmqa，故正确选项为C。 8．B 【详解】本题考查二叉树遍历相关内容。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。由图可知，该二叉树的前序遍历序列是：A-B-D-E-G-H-C-F-I。故本题答案是B选项。 9．C 【详解】本题考查抽象数据类型。定义一个抽象数据类型，不仅要清晰地表述出各方面的形式要求，还要清晰地表述出功能要求，因此答案为C。 10．C 【详解】本题主要考查二叉树的描述。由图可知，该树度为2的节点数为2；该树的深度为4；该树的中序遍历序列为B-A-C-E-D-F；该树可以用一维数组['A','B','C','','','','D','','','','','','','E','F']存储，故本题选C选项。 11．C 【详解】本题考查二叉树相关内容。已知二叉树前序遍历的结果为“大好河山”，由于该二叉树可能有多种形态，故可以将题目中给出的前序遍历和四个选项给出的中序遍历结果结合，依次画出对应的二叉树形态，不能画出二叉树的即为所求答案。对于A选项，若中序遍历为“大好河山”，则其结构如下图A所示，正确；对于B选项，若中序遍历为“河山好大”，则其结构如下图B所示，正确；对于C选项，若中序遍历为“好山大河”，不能确定其二叉树结构，错误；对于D选项，若中序遍历为“山河好大”，则其结构如下图D所示，正确。故本题答案是C选项。                          图A                         图B                          图D 12．B 【详解】本题主要考查二叉树的遍历。中序遍历，即先遍历左子树、再遍历根节点、最后遍历右子树。由图可知，其节点的中序遍历的序列为GDBEACF，故本题选B选项。 13．A 【详解】本题考查二叉树。分别中序遍历选项中的二叉树： 选项B，ABCCAB；选项C，CABCBA；选项D，CBACBA；选项A，ABCCBA。故正确答案为：选项A。 14．B 【详解】本题考查二叉树。该二叉树中序遍历为DBAEGCHFI。故答案为：B。 15．A 【详解】本题考查二叉树。 前序遍历顺序为根→左→右，中序遍历顺序为左→根→右，因此使用前序遍历定根，使用中序遍历定左右，可确认一棵唯一的二叉树，如图。 故正确答案为：选项A。 16．B 【详解】本题考查二叉树的遍历。因为这是一颗完全二叉树，前三层均满的情况下一共有7个元素，剩下的2个元素在第四层最左边，结合中序遍历结果，可画出该二叉树如下，由图可知，其前序遍历结果是EGACDBHIJ。故选B。 17．D 【详解】本题考查二叉树。仅根据部分树形结构无法确定唯一的二叉树，二叉树的深度不一定是3，也有可能为4，A错误；节点C和D有可能有子节点，不一定都是叶子节点，B错误；在前序遍历中，F在E后遍历，因此节点F在二叉树的右子树中，C错误；后序遍历是先左子树，再右子树，最后根节点，所以该二叉树的后序遍历可能是CDBFEA，D正确。故答案为：D。 18．A 【详解】本题主要考查二叉树遍历。前序遍历是 A B D E F C G（即先遍历：根左右），中序遍历是D B F E A G C（左根右的方式），则可以画出该二叉树如下，则该二叉树的后序遍历是（即左右根的方式）：D F E B G C A，故本题选A选项。 19．B 【详解】本题考查树的遍历相关内容。分析题目内容，推知： 该二叉树为完全二叉树且包含5个节点，其结构如图所示：，由后序遍历规则知，其访问过程为：3-4-1-2-0，则其根节点的位置x处于第5个，即x=5；由中序遍历的规则知，其访问过程为：3-1-4-0-2，则其根节点的位置y处于第4个，即y=4；由此得出：x-y=1，故本题答案是B选项。 20．B 【详解】本题考查二叉树。由题意可知， 二叉树如图所示。A选项错误，该二叉树的叶子节点有3个。B选项正确，该二叉树后序遍历结果为FGDBECA。C选项错误，该二叉树共有4层，E和F不位于同一层。D选项错误，该二叉树共有2对兄弟节点。故答案为：B。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$