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

admin2010-05-13 78

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

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

答案2

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

为了使操作系统容易在不同的硬件平台上进行移植，一些嵌入式操作系统使用了HAL技术，它的中文名称是【71】，其原理是取消了操作系统对【72】的直接访问，使操作系统在HAL基础上运行，从而隐藏了硬件平台的差异。

以下不属于转移(分支)类指令的是()。

ARM处理器如果R1=0x98001200，已知在小端模式下，内存0x98001204中存放数据0x35，0x98001205中存放数据0x36，0x98001206中存放数据0x37，0x98001207中存放数据0x38，在指令LDRR0，[R1，#

下列选项中用于完成创建任务的自用栈空间的μC／OS–Ⅱ程序源代码的是()。

JTAG标准是电子行业片上测试技术的一种国际标准，用于芯片和【79】的硬件测试。其中规定的TAP接口使用【80】根信号线。

在ARM汇编语言程序设计中，用于子程序设计及调用，最常用的指令是()。

在ARMCortex—M3中可实现中断嵌套，中断可以改为比之前的中断服务程序更高的优先级，并且可以在运行时改变优先级状态，使用末尾连锁连续中断需要消耗_【51】个时钟周期，而普通中断需要_【52】个时钟周期。

实时系统对时间约束要求的严格性，使【73】性成为实时系统的一项重要性能要求，它是指RTOS能够对外部事件的【74】时间和实时任务的执行时间进行判断，以确定被事件触发的实时任务能否在规定的时间内完成。

A．结膜方式B．转移方式C．吸性方式D．渗透方式E．黏附方式字迹材料写在纸上时，经外界一定压力填充在纸张的表面孔隙内。牢固度差，不耐摩擦。这种最不耐久的结合方式是

EasyWaystoGreenupYourLife①Eatingmeatproducesgreenhousegasemissions(排放).Ifyoucan’tgiveupmeatcompletely

预制混凝土梁(板)安装的技术要求中，下部构造条件不包括（）。

利润表是反映企业在(　　)财务成果的报表。

下列选项中不属于征信活动特点的是()。

高中化学课程中，侧重反映化学学科的核心研究领域和核心知识的是()。

4岁的小红知道小明是自己的亲哥哥，却不知道自己是小明的妹妹。这种现象体现了儿童思维具有()。

•Readthetexttakenfromabusinessmagazine．•Choosethebestsentencetofilleachofthegaps．•Foreachgap(9-14)，m

Newtechnologylinkstheworldasneverbefore.Ourplanethasshrunk.It’snowa"globalvillage"wherecountriesareonlyseco

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

三级数据库技术

NCRE全国计算机三级

为了使操作系统容易在不同的硬件平台上进行移植，一些嵌入式操作系统使用了HAL技术，它的中文名称是【71】，其原理是取消了操作系统对【72】的直接访问，使操作系统在HAL基础上运行，从而隐藏了硬件平台的差异。

以下不属于转移(分支)类指令的是()。

ARM处理器如果R1=0x98001200，已知在小端模式下，内存0x98001204中存放数据0x35，0x98001205中存放数据0x36，0x98001206中存放数据0x37，0x98001207中存放数据0x38，在指令LDRR0，[R1，#

下列选项中用于完成创建任务的自用栈空间的μC／OS–Ⅱ程序源代码的是()。

JTAG标准是电子行业片上测试技术的一种国际标准，用于芯片和__________【79】的硬件测试。其中规定的TAP接口使用__________【80】根信号线。

在ARM汇编语言程序设计中，用于子程序设计及调用，最常用的指令是()。

在ARMCortex—M3中可实现中断嵌套，中断可以改为比之前的中断服务程序更高的优先级，并且可以在运行时改变优先级状态，使用末尾连锁连续中断需要消耗_________【51】个时钟周期，而普通中断需要_________【52】个时钟周期。

实时系统对时间约束要求的严格性，使【73】性成为实时系统的一项重要性能要求，它是指RTOS能够对外部事件的【74】时间和实时任务的执行时间进行判断，以确定被事件触发的实时任务能否在规定的时间内完成。

A．结膜方式B．转移方式C．吸性方式D．渗透方式E．黏附方式字迹材料写在纸上时，经外界一定压力填充在纸张的表面孔隙内。牢固度差，不耐摩擦。这种最不耐久的结合方式是

EasyWaystoGreenupYourLife①Eatingmeatproducesgreenhousegasemissions(排放).Ifyoucan’tgiveupmeatcompletely

预制混凝土梁(板)安装的技术要求中，下部构造条件不包括（）。

利润表是反映企业在( )财务成果的报表。

下列选项中不属于征信活动特点的是()。

高中化学课程中，侧重反映化学学科的核心研究领域和核心知识的是()。

4岁的小红知道小明是自己的亲哥哥，却不知道自己是小明的妹妹。这种现象体现了儿童思维具有()。

•Readthetexttakenfromabusinessmagazine．•Choosethebestsentencetofilleachofthegaps．•Foreachgap(9-14)，m

Newtechnologylinkstheworldasneverbefore.Ourplanethasshrunk.It’snowa"globalvillage"wherecountriesareonlyseco

JTAG标准是电子行业片上测试技术的一种国际标准，用于芯片和【79】的硬件测试。其中规定的TAP接口使用【80】根信号线。

在ARMCortex—M3中可实现中断嵌套，中断可以改为比之前的中断服务程序更高的优先级，并且可以在运行时改变优先级状态，使用末尾连锁连续中断需要消耗_【51】个时钟周期，而普通中断需要_【52】个时钟周期。

利润表是反映企业在(　　)财务成果的报表。