下面关于二叉排序树的叙述，错误的是( )。

admin2017-09-14 107

问题下面关于二叉排序树的叙述，错误的是( )。

选项 A、对二叉排序树进行中序遍历，必定得到结点关键字的有序序列
B、依据关键字无序的序列建立二叉排序树，也可能构造出单支树
C、若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超过1
D、若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的差值一定不超过1

答案C

解析二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：①若它的左子树非空，则其左子树上所有节点的关键字均小于根节点的关键字；②若它的右子树非空，则其右子树上所有节点的关键字均大于根节点的关键字；③左、右子树本身就是两棵二叉排序树。-由上述定义可知，二叉排序树是一个有序表，对二叉排序树进行中序遍历，可得到一个关键字递增排序的序列。对于给定的关键字序列，可从空树开始，逐个将关键字插入树中来构造一棵二叉排序树。其过程是：每读入一个关键字值，就建立一个新节点。若二叉排序树非空，则将新节点的关键字与根节点的关键字相比较，如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空树，则新节点作为二叉排序树的根节点。显然，若关键字初始序列己经有序，则构造出的二叉排序树一定是单枝树(每个节点只有一个孩子)。为了使在二叉排序树上进行的查找操作性能最优，构造二叉排序树时需进行平衡化处理，使每个节点左、右子树的高度差的绝对值不超过1。

转载请注明原文地址:https://www.kaotiyun.com/show/gNRZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

下面关于二叉排序树的叙述，错误的是( )。

软件设计师上午基础知识考试

软考中级

下面关于二级目录的叙述中，错误的是(1)。多级目录结构的特点是(2)。文件系统实现按名存取主要用来实现(3)。文件系统采用二级文件目录可以(4)。为了解决不同用户文件的“命名冲突”问题，通常在文件系统中采用(5)。

以下关于边界网关协议BGP4的叙述中，不正确的是()。

在网络设计阶段进行通信流量分析时可以采用简单的80／20规则。下面关于这种规则的说明中，正确的是()。

Wi-Fi联盟制定的安全认证方案WPA(Wi-FiProtectedAccess)是__________标准的子集。(2011年上半年试题)

若某文件系统的目录结构如下图所示，假设用户要访问文件f1．java，且当前工作目录为Program，则该文件的全文件名为(1)，其相对路径为(2)。(2011年下半年试题)(1)

A．B．C．D．E．《中国药典》中规定，芦荟的指标控制成分是

布管轴线应符合设计要求，而且相邻管口错开()，以便清管和处理管口。

某甲的外祖父与某乙的父亲是亲兄弟，某丙的外祖母与某丁的祖母是亲姐妹。则()

为什么用δ值表示峰位，而不用共振频率的绝对值表示?为什么核的共振频率与仪器的磁场强度有关，而偶合常数与磁场强度无关?

下列关于肾血管性高血压临床特点的叙述，不正确的是()

关于脾转移性癌叙述，依据发生率高低依次为

在建设工程项目施工过程中，施工机具使用费的索赔款项包括()。