设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

admin2010-05-13 61

问题设平衡的二叉排序树(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，则可以证明它的深度和log₂n是同数量级的(N为结点个数)。因此，它的平均查找长度也和log₂n同数量级。

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

三级数据库技术

NCRE全国计算机三级

ARM7采用冯．诺依曼结构，【47】级流水线，ARMCortex–A15采用哈佛结构，【48】级流水线。

下面关于数字信号处理器的叙述中错误的是()。

下面关于片上系统(SoC)的叙述中，错误的是()。

S3C2410与一位共阳接法的8段LED数码管的连接如下图所示。下面与该图相关的叙述中，错误的是()。

数字视频信息的数据量相当大，通常需要进行压缩处理之后才进行传输和存储。目前数字有线电视所传输的数字视频采用的压缩编码标准是()。

在μC／OS—II中，OSSched()函数是任务调度的前导函数，用于判断进行任务调度的条件是否满足。下列满足条件的变量值为()。

在数字音频信息数字化过程中，正确的处理顺序是()。

下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中CPU中的组成部分A是_【41】；组成部分B是_【42】。

局域网是计算机网络中最流行的一种形式。下面有关局域网的叙述中错误的是()。

慢性消化性溃疡不具备的病理变化是

关于传入侧支抑制

低渗性脱水的常见病因是高钾血症的常见病因是

按照《治安管理处罚法》的规定，询问不满多少周岁的违反治安管理的行为人，应当通知其父母或者其他监护人到场？()

假定有A、B两个投资方案，它们的投资额相同，现金流量总和也相同，但A方案的现金流量逐年递增，B方案的现金流量逐年递减。如果考虑资金时间价值，在两方案均可行的情况下，下列表述正确的是()。

下列项目中，应计入商品流通企业存货入账价值的有()。

今年祖父的年龄是小军年龄的6倍，几年后祖父的年龄是小军年龄的5倍，又过几年以后，祖父的年龄是小军年龄的4倍。由此可知，祖父今年60岁。()

WhilepopularintheU.S.,theAprilFool’sDaytraditionisevenmoreprevalentinEuropeancountries,suchasFranceandGre

Home,Sweet(andSour)HomeOnAugust15,1945,thedaythatwarended,Australiawasjubilant.Amonthlateritwasmorewar

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

三级数据库技术

NCRE全国计算机三级

ARM7采用冯．诺依曼结构，【47】级流水线，ARMCortex–A15采用哈佛结构，【48】级流水线。

下面关于数字信号处理器的叙述中错误的是()。

下面关于片上系统(SoC)的叙述中，错误的是()。

S3C2410与一位共阳接法的8段LED数码管的连接如下图所示。下面与该图相关的叙述中，错误的是()。

数字视频信息的数据量相当大，通常需要进行压缩处理之后才进行传输和存储。目前数字有线电视所传输的数字视频采用的压缩编码标准是()。

在μC／OS—II中，OSSched()函数是任务调度的前导函数，用于判断进行任务调度的条件是否满足。下列满足条件的变量值为()。

在数字音频信息数字化过程中，正确的处理顺序是()。

下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中CPU中的组成部分A是___________【41】；组成部分B是___________【42】。

局域网是计算机网络中最流行的一种形式。下面有关局域网的叙述中错误的是()。

慢性消化性溃疡不具备的病理变化是

关于传入侧支抑制

低渗性脱水的常见病因是高钾血症的常见病因是

按照《治安管理处罚法》的规定，询问不满多少周岁的违反治安管理的行为人，应当通知其父母或者其他监护人到场？()

假定有A、B两个投资方案，它们的投资额相同，现金流量总和也相同，但A方案的现金流量逐年递增，B方案的现金流量逐年递减。如果考虑资金时间价值，在两方案均可行的情况下，下列表述正确的是()。

下列项目中，应计入商品流通企业存货入账价值的有()。

今年祖父的年龄是小军年龄的6倍，几年后祖父的年龄是小军年龄的5倍，又过几年以后，祖父的年龄是小军年龄的4倍。由此可知，祖父今年60岁。()

WhilepopularintheU.S.,theAprilFool’sDaytraditionisevenmoreprevalentinEuropeancountries,suchasFranceandGre

Home,Sweet(andSour)HomeOnAugust15,1945,thedaythatwarended,Australiawasjubilant.Amonthlateritwasmorewar

下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中CPU中的组成部分A是_【41】；组成部分B是_【42】。