教科版（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；对该表达式树进 ... ...