教科版（2019）选修一6.1数结构及其实现同步训练

教科版（2019）选修一6.1数结构及其实现同步训练 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．下列二叉树中，中序遍历结果为BAEDFC的是（   ） A． B． C． D． 2．有树结构的示意图如图所示，下列关于该树的描述正确的是（   ） A．该树的度为6 B．该树的叶子节点数量是7 C．节点I、J互为兄弟节点 D．该树的深度为5 3．一棵包含10个节点的完全二叉树，其叶子节点的个数为（　　） A．3 B．4 C．5 D．6 4．表达式树是包含表达式的数据结构，表达式树对于一些高性能的场景下有较大实用性。如图所示，一个数学表达式可以用一棵表达式树来表示。下列关于该表达式树的描述中不正确的是（　　） A．表达式树的根节点左右子树的深度差不会超过1 B．对该表达式树进行后序遍历得到的后序表达式，实现了无括号处理和优先级处理 C．该表达式树对应的表达式为(6-3)/2+5*(7+2)/8 D．该表达式树中的内部节点比分支节点少一个 5．以下数据结构中哪一个是非线性结构？（   ） A．队列 B．列表 C．树 D．线性表 6．假设完全二叉树的树根为第1 层，树中第10 层有5 个叶子节点，则完全二叉树最多有多少个节点？（     ） A．2047 B．2048 C．2037 D．2038 7．一棵度为3，深度为4的树，最多有（     ）个节点。 A．31 B．32 C．40 D．42 8．有一棵二叉树，如图所示，下列说法正确的是（   ） A．此二叉树是完全二叉树 B．此二叉树的叶子节点有3个 C．此二叉树的后序遍历为F—D—B—E—C—A D．此二叉树用一维数组表示为[‘A’‘B’，‘C’，‘D’，‘E’，‘F’] 9．诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是（   ） A．树 B．栈 C．队列 D．链表 10．某二叉树的树形结构如图所示，其后序遍历结果为FBCEAD，则前序遍历结果为（    ） A．ABCDEF B．FEDCBA C．DFACBE D．FDBCAE 11．某二叉树的中序遍历序列为ABCDEFG，后序遍历序列为ACBFEGD，下列说法正确的是（   ） A．前序遍历序列为DBACGFE B．节点G为节点E的父节点 C．该二叉树有两个叶子节点 D．节点A与节点F为同一层 12．如图所示的二叉树，下列说法正确的是（   ） A．该二叉树是一个完全二叉树 B．该二叉树的深度为4，节点D的度为2 C．该二叉树的叶子节点数比非叶子节点数少一个 D．该二叉树中A是D和E的父节点 13．某二叉树的树形结构如下图所示，后序遍历结果为“WUSVTR”，则该二叉树的前序遍历结果为（   ） A．RSTUVW B．RTSVUW C．RTSUWV D．RSUWTV 14．有如下Python程序段: def search(x):     ans=""     if a[2 *x]!="":        ans= ans+search(2 *x)     if a[2*x+1]!="":        ans= ans+search(2*x+1)     ans= ans+a[x]     return ans a=["" for i in range(32)] a[1]="A";a[2]="B";a[3]="C";a[4]="D";a[7]="E";a[9]="F" print(search(1)) 运行该程序段后，输出的结果是（   ） A．FDBECA B．ACEBDF C．ABCDEF D．FEDCBA 15．全国航运图属于（   ） A．线性结构 B．树结构 C．图结构 D．以上均不是 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题考查的是二叉树遍历相关知识。二叉树的中序遍历：先遍历左子树节点，再遍历根节点，再遍历右子树节点。选项A中序遍历结果为EDFBAC；选项B中序遍历结果为BEDFAC；选项C中序遍历结果为BAEDFC；选项D中序遍历结果为BACEDF，故本题应选C。 2．B 【详解】本题主要考查树结构的描述。由图可知，该树的度为3； 该树的叶子节点数量是7； 节点I、H互为兄弟节点； 该树的深度为4，故本题选B选项。 3．C 【详解】本题考查的二叉树相关知识。一个具有n个节点的完全二叉树，其其叶子节点的个数为：n/2向上取整，或(n+1)/2向下取整。10/2=5，故选项C正确。 4．A 【详解】本题主要考查树结构。表达式树的根节点左右子树的深度差可以超过1；对该表达式树进行后序遍历得到的后序表达式，实现了无括号处理和优先级处理；该表达式树对应的表达式为(6-3)/2+5*(7+2)/8；该表达式树中的内部节点比分支节点少一个，故本题选A选项。 5．C 【详解】本题考查的是数据结构。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)。故本题应选C。 6．C 【详解】本题考查二叉树相关内容。由题目内容可知，若求该完全二叉树最多有多少个节点，两种方法可解决：（1）该二叉树共11层，前10层为满二叉树，第10层有5个叶子节点，说明这5个节点没有孩子，则第11层将缺少10个节点才可以达到节点数最多。前10层节点数为：210-1=1023，第11层节点数最多为：211-1-10=210-10=1014。1023+1014=2037。（2）一棵完全二叉树达到最多节点，则该二叉树可以为满二叉树，但题目中告知第10层有5个叶子节点，则其最多节点数为11层满二叉树节点数-10，即：211-1-10=2037。以上两种方法都可得结果：2037。故本题答案是C选项。 7．C 【详解】本题主要考查数据结构。一棵度为3，深度为4的树，则第一层有1个根节点，第二层最多有3个子节点，第三层最多有3*3=9个子节点，第四层最多有3*9=27个子节点，则最多有1+3+9+27=40个节点，故本题选C选项。 8．C 【详解】本题考查二叉树相关知识。A选项，观察此图，结合完全二叉树的定义，发现该二叉树不是完全二叉树，A错误；该二叉树的叶子节点有2个，不是3个，B错误；C选项，按照后序遍历（左右根）规则，该二叉树后序遍历序列为：FDBECA，正确。D选项，观察一维数组可以发现，B节点的孩子为D、E节点，这不符合二叉树图示，D错误。故本题答案是C选项。 9．A 【详解】本题考查的是数据结构。树状图是一种数据结构，它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。故本题应选A。 10．C 【详解】 本题考查二叉树的前序遍历。后序遍历规则为“左右根”，已知后序遍历结果为FBCEAD，结合题干中树形结构图可知该二叉树的树形结构应为：，前序遍历规则为“根左右”，根据完整的二叉树结构图，得出前序遍历为DFACBE。故答案为C选项。 11．B 【详解】本题考查的是二叉树。依据题意可画出如下的数： 由图可知，前序遍历序列为DBACGEF，节点G为节点E的父节点，该二叉树有3个叶子节点，节点A与节点F不在同一层。故本题应选B。 12．C 【详解】本题考查的是二叉树。完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1)) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉数。图中所示的二叉树不是一个完全二叉树；该二叉树的深度为4，节点D的度为1；该二叉树的叶子节点数（3）比非叶子节点数（4）少一个；A是B和C的父节点。故本题应选C。 13．D 【详解】本题考查二叉树相关内容。通过观察该二叉树树型结构及分析其后序遍历序列，可得该二叉树具体形态为：   故其前序遍历序列为：RSUWTV。 14．A 【详解】本题考查的是递归及树的遍历。本题是将递归算法和树的遍历进行了结合，search(1)就是从根节点出发， 首先查看有无左子树，若有继续查看还有没有左子树，若有则继续，直到无左子树的时候再查看右子树的情况....故此判断该算法说的是树的遍历，而且是后序遍历的情况，由此画出该二叉树如下： 故选A。 15．C 【详解】本题考查图数据结构的描述。图是最为复杂的数据结构，如果数据元素之间存在一对多或者多对多的关系，那么这种数据的组织结构就叫作图结构。全国航运图存在多对多的关系，属于图结构。线性结构和树结构不存在多对多的关系。故选C。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$