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

admin2010-05-13 59

问题设平衡的二叉排序树(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://www.kaotiyun.com/show/j3SZ777K

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

三星公司基于ARM9内核的S3C2410嵌入式微处理器芯片使用由AHB总线和APB总线组成的AMBA总线。对于高速组件采用【63】总线连接，而对于低速外设接口则采用【64】总线连接。

下列系统属于实时系统的是()。

嵌入式系统硬件的逻辑组成可用下图描述，图中①、②、③、④处分别是()。

已知R1=0x81000000，R0=0x00112233，在小端模式下执行ARM指令STRR0，[R1]之后，内存0x81000002中的值为()。

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

用ARlM汇编语言，在内存空间定义一个字(32位)变量的伪指令为【57】，指示下面为16位代码的伪指令是【58】。

当满足一定条件时，μC／OS–II操作系统内核将进行任务调度。下列各项中属于中断级任务调度需满足的条件的是()。

在μC／OS—II操作系统下，处于运行态的任务调用系统函数OSSemPend()后将转入()。

目前，无线局域网(WLAN)已经是无线上网的一种重要手段，它采用的通信协议是IEEE【45】a／b／g／n，其数据传输速率可达11一【46】Mb／s。

科学决策追求的是最优最好方案。()

A．3，4-苯并芘B．黄曲霉毒素C．石棉纤维D．乙萘胺

A．身热不扬B．高热不退C．午后低热D．日晡潮热E．发热重，恶寒轻

乘轮船旅游购买儿童票的旅游者，身高应在()之间。

设δ＞0，f(x)在(一δ，δ)有连续的三阶导数，f’(0)=f"(0)=0且，则下列结论正确的是

曲线的渐近线条数为()．

CarSafety1.Thefocalpointoftheproject:RoadRage-e.g.Amanhitthedriverwhohad【T1】himearlier【T1】2.

DrugshavebeenapartoftheAmericanstorysincetheveryfirstdayColumbuslandedintheNewWorld.TheTainoIndians【B1】___

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

三级数据库技术

NCRE全国计算机三级

三星公司基于ARM9内核的S3C2410嵌入式微处理器芯片使用由AHB总线和APB总线组成的AMBA总线。对于高速组件采用【63】总线连接，而对于低速外设接口则采用【64】总线连接。

下列系统属于实时系统的是()。

嵌入式系统硬件的逻辑组成可用下图描述，图中①、②、③、④处分别是()。

已知R1=0x81000000，R0=0x00112233，在小端模式下执行ARM指令STRR0，[R1]之后，内存0x81000002中的值为()。

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

用ARlM汇编语言，在内存空间定义一个字(32位)变量的伪指令为__________【57】，指示下面为16位代码的伪指令是__________【58】。

当满足一定条件时，μC／OS–II操作系统内核将进行任务调度。下列各项中属于中断级任务调度需满足的条件的是()。

在μC／OS—II操作系统下，处于运行态的任务调用系统函数OSSemPend()后将转入()。

目前，无线局域网(WLAN)已经是无线上网的一种重要手段，它采用的通信协议是IEEE【45】a／b／g／n，其数据传输速率可达11一【46】Mb／s。

科学决策追求的是最优最好方案。()

A．3，4-苯并芘B．黄曲霉毒素C．石棉纤维D．乙萘胺

A．身热不扬B．高热不退C．午后低热D．日晡潮热E．发热重，恶寒轻

乘轮船旅游购买儿童票的旅游者，身高应在()之间。

设δ＞0，f(x)在(一δ，δ)有连续的三阶导数，f’(0)=f"(0)=0且，则下列结论正确的是

曲线的渐近线条数为()．

CarSafety1.Thefocalpointoftheproject:RoadRage-e.g.Amanhitthedriverwhohad【T1】______himearlier【T1】______2.

DrugshavebeenapartoftheAmericanstorysincetheveryfirstdayColumbuslandedintheNewWorld.TheTainoIndians【B1】___

用ARlM汇编语言，在内存空间定义一个字(32位)变量的伪指令为【57】，指示下面为16位代码的伪指令是【58】。

CarSafety1.Thefocalpointoftheproject:RoadRage-e.g.Amanhitthedriverwhohad【T1】himearlier【T1】2.