设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为________。

admin2010-05-13 32

问题设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为________。

选项 A、O(1)
B、O(log₂n)
C、O(n)
D、O(nlog₂n)

答案2

解析平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的(N为结点个数)。由此，它的平均查找长度也和logN同数量级。

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

本试题收录于：三级数据库技术题库NCRE全国计算机三级分类

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为________。

三级数据库技术

NCRE全国计算机三级

ARM处理器在指令LDRR2，[R5，#2]!执行后，R5中的值为()。

我国大陆地区目前广泛使用的汉字编码国家标准有【43】和GB18030两种，常用汉字采用【44】个字节表示。

下面有关CNU的描述语句中，不恰当的是()。

嵌入式Linux操作系统由用户进程、OS服务组件和Linux内核3个部分组成，下面叙述中错误的是()。

下面的描述语句中不正确的是()。

关系模型有三类完整性约束：实体完整性、参照完整性和用户定义的完整性。定义外键实现的是哪一（些）类完整性？

A．阵发性睡眠性血红蛋白尿B．小细胞低色素性贫血C．急性髓性白血病D．亚急性脊髓联合变性E．急性造血功能停滞再生障碍性贫血()

男性，25岁，3天前抬重物扭伤腰部。服用芬必得，卧床休息腰痛无缓解，出现右腿麻木，右直腿抬高40°～50°阳性，加强试验阳性。经检查诊断为腰4～5椎间盘突出症，此时较合适的处理是

A．小柴胡汤B．身痛逐瘀汤C．独活寄生汤D．养荣壮肾汤加熟地黄E．黄芪桂枝五物汤加秦艽、当归、鸡血藤

变压器的额定容量为2MVA，变压器阻抗电压百分数为5.5，基准容量取100MVA，变压器的电抗标幺值为()。

每一个孩子都是一个潜在的天才儿童，要以多维度、全面发展的眼光来评价学生，这种主张的理论基础是()。

10，11，36，185，()。

5/121/33/413/12(　　)35/12

在一项试验中，第一组被试验者摄取了大量的人造糖，第二组则没有吃糖。结果发现，吃糖的人比没有吃糖的人认知能力低。这一试验说明，人造糖中所含的某种成分会影响人的认知能力。以下哪项如果为真，最支持上述结论?

A、Leaveitattheairport.B、Giveittohisfriend.C、Takeitwithhim.D、Throwitaway.A推理判断题。本题询问男士会怎样处理那把小刀。在对话的末尾，女士建议男士把小刀

A、Philiphasnotbeentothispartofthelibrarybefore.B、Itwasveryquietinthelibrary.C、Philipfellofftheladderandm

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为________。

三级数据库技术

NCRE全国计算机三级

ARM处理器在指令LDRR2，[R5，#2]!执行后，R5中的值为()。

我国大陆地区目前广泛使用的汉字编码国家标准有【43】和GB18030两种，常用汉字采用【44】个字节表示。

下面有关CNU的描述语句中，不恰当的是()。

嵌入式Linux操作系统由用户进程、OS服务组件和Linux内核3个部分组成，下面叙述中错误的是()。

下面的描述语句中不正确的是()。

关系模型有三类完整性约束：实体完整性、参照完整性和用户定义的完整性。定义外键实现的是哪一（些）类完整性？

A．阵发性睡眠性血红蛋白尿B．小细胞低色素性贫血C．急性髓性白血病D．亚急性脊髓联合变性E．急性造血功能停滞再生障碍性贫血()

男性，25岁，3天前抬重物扭伤腰部。服用芬必得，卧床休息腰痛无缓解，出现右腿麻木，右直腿抬高40°～50°阳性，加强试验阳性。经检查诊断为腰4～5椎间盘突出症，此时较合适的处理是

A．小柴胡汤B．身痛逐瘀汤C．独活寄生汤D．养荣壮肾汤加熟地黄E．黄芪桂枝五物汤加秦艽、当归、鸡血藤

变压器的额定容量为2MVA，变压器阻抗电压百分数为5.5，基准容量取100MVA，变压器的电抗标幺值为()。

每一个孩子都是一个潜在的天才儿童，要以多维度、全面发展的眼光来评价学生，这种主张的理论基础是()。

10，11，36，185，()。

5/121/33/413/12( )35/12

在一项试验中，第一组被试验者摄取了大量的人造糖，第二组则没有吃糖。结果发现，吃糖的人比没有吃糖的人认知能力低。这一试验说明，人造糖中所含的某种成分会影响人的认知能力。以下哪项如果为真，最支持上述结论?

A、Leaveitattheairport.B、Giveittohisfriend.C、Takeitwithhim.D、Throwitaway.A推理判断题。本题询问男士会怎样处理那把小刀。在对话的末尾，女士建议男士把小刀

A、Philiphasnotbeentothispartofthelibrarybefore.B、Itwasveryquietinthelibrary.C、Philipfellofftheladderandm

5/121/33/413/12(　　)35/12