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

admin2010-05-13 43

问题设平衡的二叉排序树(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全国计算机三级

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

以下关于VxWorks操作系统的叙述中，错误的是()。

实时操作系统完成每次任务所需时间的偏差称为【71】。硬实时操作系统的这一参数比软实时操作系统的这一参数【72】。

数字图像的文件格式有多种，不同的文件格式采用不同的编码方法，具有不同的特点，适合不同的应用。通常，数码相机中大多使用【43】图像文件格式，www网页中具有动画效果的插图或剪贴画其文件格式是【44】。

数字图像的文件格式有多种，不同的文件格式采用不同的编码方法，具有不同的特点，适合不同的应用。通常，数码相机中大多使用【43】图像文件格式，WWW网页中具有动画效果的插图或剪贴画其文件格式是【44】。

GNu开发工具套件中的c语言编译器，其英文简称是【79】_。它所能编译的目标机处理器包括X86、ARM、PowerPC等体系结构的处理器。针对于ARM体系结构的目标机而言，该C语言编译器的命令书写格式中，其带前缀的命令是【80】_。

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

在完全二叉树的顺序存储中，若结点i有左子女，则其左子女是结点()。

按先根次序周游树（林）等同于按【】序周对应的二叉树。

β2受体兴奋剂在应用2周后，常引起β2受体下调，支气管舒张作用减弱。下列哪种药物可促进β2受体功能的恢复

慢性肺源性心脏病最常见的病因是

绝经前后诸证的产生机制主要是

关于刑事责任的追究，下列哪些选项是正确的?(2009年卷二54题，多选)

某企业年初向银行借款8万元，年利率为10％，还款周期为4年，还款方式为每年年末等额偿还本金，并支付当年利息，则该企业还款总额为()万元。

呈块(石)碎(石)状镶嵌结构或呈大块状砌体结构，拱部无支护时可产生小坍塌，侧壁基本稳定，爆破震动过大易坍塌的是（）围岩。

施工单位在某项目施工中偷工减料，造成建设工程不符合规定的质量标准，给建设单位造成损失。建设行政主管部门可以对该施工单位实施的制裁是()。

信用证中的软条款规定()。

Howmenfirstlearnedtoinventwordsisunknown;【C1】______,theoriginoflanguageisamystery.Allwereallyknowisthatme

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

三级数据库技术

NCRE全国计算机三级

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

以下关于VxWorks操作系统的叙述中，错误的是()。

实时操作系统完成每次任务所需时间的偏差称为__________【71】。硬实时操作系统的这一参数比软实时操作系统的这一参数__________【72】。

数字图像的文件格式有多种，不同的文件格式采用不同的编码方法，具有不同的特点，适合不同的应用。通常，数码相机中大多使用【43】图像文件格式，www网页中具有动画效果的插图或剪贴画其文件格式是【44】。

数字图像的文件格式有多种，不同的文件格式采用不同的编码方法，具有不同的特点，适合不同的应用。通常，数码相机中大多使用【43】图像文件格式，WWW网页中具有动画效果的插图或剪贴画其文件格式是【44】。

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

在完全二叉树的顺序存储中，若结点i有左子女，则其左子女是结点()。

按先根次序周游树（林）等同于按【】序周对应的二叉树。

β2受体兴奋剂在应用2周后，常引起β2受体下调，支气管舒张作用减弱。下列哪种药物可促进β2受体功能的恢复

慢性肺源性心脏病最常见的病因是

绝经前后诸证的产生机制主要是

关于刑事责任的追究，下列哪些选项是正确的?(2009年卷二54题，多选)

某企业年初向银行借款8万元，年利率为10％，还款周期为4年，还款方式为每年年末等额偿还本金，并支付当年利息，则该企业还款总额为()万元。

呈块(石)碎(石)状镶嵌结构或呈大块状砌体结构，拱部无支护时可产生小坍塌，侧壁基本稳定，爆破震动过大易坍塌的是（）围岩。

施工单位在某项目施工中偷工减料，造成建设工程不符合规定的质量标准，给建设单位造成损失。建设行政主管部门可以对该施工单位实施的制裁是()。

信用证中的软条款规定()。

Howmenfirstlearnedtoinventwordsisunknown;【C1】______,theoriginoflanguageisamystery.Allwereallyknowisthatme

实时操作系统完成每次任务所需时间的偏差称为【71】。硬实时操作系统的这一参数比软实时操作系统的这一参数【72】。