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

admin2009-01-19 71

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

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

答案2

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

Windows98支持多种不同类型的文件系统，并可以安装第三方提供的文件系统。在Windows98环境下，DVD-ROM采用的文件系统为哪一种?

下F面是关于PCI总线的叙述，其中错误的是

Windows98　的注册表信息分类存储在三个不同的文件中，它们分别是SYSTEM.DAT、【　　】.DAT和CONFIGPOL。

若(BX)=1000H，(DS)=2000H，(21000H)=12H，(21001H)二34H，执行LEASI，[BX]指令后，SI寄存器的内容是

局域网(LAN)指较小地域范围内的计算机网络，一般是一幢建筑物内或一个单位的几幢建筑物内的计算机互连而成的计算机网络。局域网有多种类型，目前使用最多的是

在汇编语言程序设计中，若调用不在本模块中的过程，则对该过程必须用(　　　)伪操作命令说明。

DVD-ROM　的速度计算方法与CD-ROM　不同，前者的速度单位(速度基准)是后者的9倍，所以DVD-ROM　的一倍速应为(　　　)。

一个显示适配器的显示存储器VRAM的容量为2MB，如果工作在1024×768像素高分辨率模式下，每个像素最多可以显示______种颜色。

请编制程序，其功能是：从第0行第0列开始，依次取出N阶矩阵中对角线上的元素(字节型)并计算累加和(字型)，然后将其存放在指定的内存区中。例如：内存中有：01H，01H，01H，02H，02H，02H，03ff，03H，03H结果为：

Windows98内置的某个多媒体软件组件提供了一套API函数，利用这些函数可以编写出许多高性能的实时多媒体应用程序（如游戏软件），而无须深入了解机器板卡的硬件特性。这个多媒体软件组件是

测定水样浊度时，要静止后，再测量。

下列哪一或哪些选项正确表达了法律与国家的关系?()

某造纸企业为应对桉树原料堆场、原料切片车间、碱回收锅炉车间、烘干车间以及发电机组车间发生的突发事件，制定了相应的应急预案。根据有关规定，关于该企业应急管理工作的说法，正确的有()。

依照招标投标法的规定提出招标项目,进行招标的法人或者其他组织为()。

下列各项中，工业企业不应将其计入财务费用的是()。

表一中，冰雪旅游四项指标总得分最高的城市是()。

Neverbefore(Ihave)seenanyone(whohas)theskill(Johnhas)whenhe(repairs)cars.

白板说

Everyoneknowsthattaxationisnecessaryinamodernstate.Withoutit,itwouldbeimpossibletopaythesoldiersandpoliceme

A、85.B、100.C、40.D、125.B

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

三级数据库技术

NCRE全国计算机三级

Windows98支持多种不同类型的文件系统，并可以安装第三方提供的文件系统。在Windows98环境下，DVD-ROM采用的文件系统为哪一种?

下F面是关于PCI总线的叙述，其中错误的是

Windows98 的注册表信息分类存储在三个不同的文件中，它们分别是SYSTEM.DAT、【 】.DAT和CONFIGPOL。

若(BX)=1000H，(DS)=2000H，(21000H)=12H，(21001H)二34H，执行LEASI，[BX]指令后，SI寄存器的内容是

局域网(LAN)指较小地域范围内的计算机网络，一般是一幢建筑物内或一个单位的几幢建筑物内的计算机互连而成的计算机网络。局域网有多种类型，目前使用最多的是

在汇编语言程序设计中，若调用不在本模块中的过程，则对该过程必须用( )伪操作命令说明。

DVD-ROM 的速度计算方法与CD-ROM 不同，前者的速度单位(速度基准)是后者的9倍，所以DVD-ROM 的一倍速应为( )。

一个显示适配器的显示存储器VRAM的容量为2MB，如果工作在1024×768像素高分辨率模式下，每个像素最多可以显示______种颜色。

请编制程序，其功能是：从第0行第0列开始，依次取出N阶矩阵中对角线上的元素(字节型)并计算累加和(字型)，然后将其存放在指定的内存区中。例如：内存中有：01H，01H，01H，02H，02H，02H，03ff，03H，03H结果为：

Windows98内置的某个多媒体软件组件提供了一套API函数，利用这些函数可以编写出许多高性能的实时多媒体应用程序（如游戏软件），而无须深入了解机器板卡的硬件特性。这个多媒体软件组件是

测定水样浊度时，要静止后，再测量。

下列哪一或哪些选项正确表达了法律与国家的关系?()

某造纸企业为应对桉树原料堆场、原料切片车间、碱回收锅炉车间、烘干车间以及发电机组车间发生的突发事件，制定了相应的应急预案。根据有关规定，关于该企业应急管理工作的说法，正确的有()。

依照招标投标法的规定提出招标项目,进行招标的法人或者其他组织为()。

下列各项中，工业企业不应将其计入财务费用的是()。

表一中，冰雪旅游四项指标总得分最高的城市是()。

Neverbefore(Ihave)seenanyone(whohas)theskill(Johnhas)whenhe(repairs)cars.

白板说

Everyoneknowsthattaxationisnecessaryinamodernstate.Withoutit,itwouldbeimpossibletopaythesoldiersandpoliceme

A、85.B、100.C、40.D、125.B

Windows98　的注册表信息分类存储在三个不同的文件中，它们分别是SYSTEM.DAT、【　　】.DAT和CONFIGPOL。

在汇编语言程序设计中，若调用不在本模块中的过程，则对该过程必须用(　　　)伪操作命令说明。

DVD-ROM　的速度计算方法与CD-ROM　不同，前者的速度单位(速度基准)是后者的9倍，所以DVD-ROM　的一倍速应为(　　　)。