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

admin2010-05-13 32

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

采用ADS1．2集成开发工具软件来开发基于ARM微处理器的嵌入式系统时，ADS1．2把目标文件中的信息按照三种存储区域类型来进行划分，即划分为RO段、【77】、ZI段。其中RO段是指【78】和常数的存储区域，具有只读属性。

在ARM汇编语言程序设计中，经常用到分支程序设计，以下不属于分支指令的是()。

通用分组无线服务技术简称为【65】_，它是GSM用户可用的一种移动数据业务，通常支持用【66】_指令集实现呼叫、短信、传真、数据传输等业务。

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

以下是有关TCP／IP协议中IP地址格式(IPv4)的叙述，其中错误的是()。

VxWorks和Linux都将I／O设备分为多种类型。其中，以字节流方式进行数据交互的设备称为【71】设备；硬盘和闪存等设备则称为【72】设备。

半导体集成电路是微电子技术的核心。下面有关集成电路的叙述中错误的是()。

按照内核结构分类，Android属于_【59】操作系统，这类内核的特点是各个模块之间的耦合度很_【60】，通过函数调用实现模块之间的通信。

局域网指较小地域范围内的计算机网络，最流行的局域网是以太网。以太网采用的通信协议是【47】，连接在以太网中的每台计算机必须至少有一个全球唯一的【48】地址。

玉液汤的组成药物中有

关于先天性无阴道，下列哪项说法正确

《中华人民共和国港口法》第十三条规定在港口总体规划区内建设港口设施，使用非深水岸线的，由()批准。

反映结构工程中混凝土工艺方案技术特性的指标是______。

记账凭证的填制必须做到记录真实，内容完整，填制及时，书写清楚外，还必须符合()要求。

国库集中收付制度是指以国库单一账户体系为基础，将所有财政性资金都纳入国库单一账户体系管理，收入直接缴入国库和财政专户，支出通过国库单一账户体系支付到商品和劳务供应者或用款单位的一项国库管理制度。()

《2016年政府工作报告》指出，改革是引领发展的第一动力，必须摆在国家发展全局的核心位置，深入实施创新驱动发展战略。()

关于水平滚动条，如下叙述中错误的是(　　)。

Itisoftenobservedthattheagedspendmuchtimethinkingandtalkingabouttheirpastlives,21aboutthefuture.Theseremin

Nextfall,whenyouseegeeseheadingsouthforthewinter,flyingalongin"V"formation,youmightconsiderwhatsciencehasd

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

三级数据库技术

NCRE全国计算机三级

采用ADS1．2集成开发工具软件来开发基于ARM微处理器的嵌入式系统时，ADS1．2把目标文件中的信息按照三种存储区域类型来进行划分，即划分为RO段、【77】、ZI段。其中RO段是指【78】和常数的存储区域，具有只读属性。

在ARM汇编语言程序设计中，经常用到分支程序设计，以下不属于分支指令的是()。

通用分组无线服务技术简称为【65】_______，它是GSM用户可用的一种移动数据业务，通常支持用【66】_______指令集实现呼叫、短信、传真、数据传输等业务。

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

以下是有关TCP／IP协议中IP地址格式(IPv4)的叙述，其中错误的是()。

VxWorks和Linux都将I／O设备分为多种类型。其中，以字节流方式进行数据交互的设备称为【71】设备；硬盘和闪存等设备则称为【72】设备。

半导体集成电路是微电子技术的核心。下面有关集成电路的叙述中错误的是()。

按照内核结构分类，Android属于___________【59】操作系统，这类内核的特点是各个模块之间的耦合度很___________【60】，通过函数调用实现模块之间的通信。

局域网指较小地域范围内的计算机网络，最流行的局域网是以太网。以太网采用的通信协议是【47】，连接在以太网中的每台计算机必须至少有一个全球唯一的【48】地址。

玉液汤的组成药物中有

关于先天性无阴道，下列哪项说法正确

《中华人民共和国港口法》第十三条规定在港口总体规划区内建设港口设施，使用非深水岸线的，由()批准。

反映结构工程中混凝土工艺方案技术特性的指标是______。

记账凭证的填制必须做到记录真实，内容完整，填制及时，书写清楚外，还必须符合()要求。

国库集中收付制度是指以国库单一账户体系为基础，将所有财政性资金都纳入国库单一账户体系管理，收入直接缴入国库和财政专户，支出通过国库单一账户体系支付到商品和劳务供应者或用款单位的一项国库管理制度。()

《2016年政府工作报告》指出，改革是引领发展的第一动力，必须摆在国家发展全局的核心位置，深入实施创新驱动发展战略。()

关于水平滚动条，如下叙述中错误的是( )。

Itisoftenobservedthattheagedspendmuchtimethinkingandtalkingabouttheirpastlives,21aboutthefuture.Theseremin

Nextfall,whenyouseegeeseheadingsouthforthewinter,flyingalongin"V"formation,youmightconsiderwhatsciencehasd

通用分组无线服务技术简称为【65】_，它是GSM用户可用的一种移动数据业务，通常支持用【66】_指令集实现呼叫、短信、传真、数据传输等业务。

按照内核结构分类，Android属于_【59】操作系统，这类内核的特点是各个模块之间的耦合度很_【60】，通过函数调用实现模块之间的通信。

关于水平滚动条，如下叙述中错误的是(　　)。