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

admin2010-05-13 41

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

下面关于Linux内核的叙述中，错误的是()。

ARM处理器采用的指令集结构是【47】，其中面向实时系统的嵌入式Cortex系列是【48】。

ARM7采用冯．诺依曼结构，【47】级流水线，ARMCortex–A15采用哈佛结构，【48】级流水线。

关于ARM处理器的工作模式，以下说法错误的是()。

在μC／OS—II操作系统中，当处于运行态的任务执行节拍延时函数OSTimeDly()后，该任务将转入【73】态。一旦预定的延时时间达到，该任务立即转入【74】态。

苹果公司研发的手持设备操作系统名为【65】，美国加州大学伯克利分校开发的主要用于无线传感器网络的操作系统名为【66】。

数字文本(也称电子文本)是以文字及符号为主的一种数字媒体，下面关于数字文本的有关叙述中，错误的是()。

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

下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是【41】；组成部分B是【42】。

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

ThemajorityofpeopleinScotlandareinfavorbreakingawayfromtherestoftheUKandbecomingindependent,accordingtoap

男性，28岁。体力劳动时突然出现剧烈头痛，难以忍受，急送医院。体检：神清，颅神经正常，四肢活动正常，颈有抵抗，克氏征阳性，最可能的诊断为

要比较甲、乙两厂某工种工人某职业病患病萃的高低，采取标准化法的原理是

关于乳酸循环的叙述，不正确的是

某企业外部融资占销售增长的百分比为5％，若上年营业收入为1000万元，预计营业收入增加200万元，则相应外部应追加的融资额为()万元。

下列关于企业内部劳动规则的说法错误的是()。

沉没成本是指已经付出且不可收回的成本。沉没成本是由过去的决策或环境决定的，它所造成的成本是不能由现在或将来的任何决策而改变的。根据上述定义，下列不涉及沉没成本的是()。

并发操作可能会产生数据不一致，用什么方法能避免这些不一致的情况?一——

信息传输的安全应保证信息在网络传输的过程中不被泄漏和不被攻击，下列哪些属于在网络中攻击的方法?Ⅰ．复制信息　　Ⅱ．剪裁信息　　Ⅲ．窃听信息

WhenCarlyFiorinabecameHewlett-Packard’sfirstfemalechiefexecutiveofficer,theexistenceofherhousehusband,FrankFiori

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

三级数据库技术

NCRE全国计算机三级

下面关于Linux内核的叙述中，错误的是()。

ARM处理器采用的指令集结构是【47】，其中面向实时系统的嵌入式Cortex系列是【48】。

ARM7采用冯．诺依曼结构，【47】级流水线，ARMCortex–A15采用哈佛结构，【48】级流水线。

关于ARM处理器的工作模式，以下说法错误的是()。

在μC／OS—II操作系统中，当处于运行态的任务执行节拍延时函数OSTimeDly()后，该任务将转入【73】态。一旦预定的延时时间达到，该任务立即转入【74】态。

苹果公司研发的手持设备操作系统名为【65】，美国加州大学伯克利分校开发的主要用于无线传感器网络的操作系统名为【66】。

数字文本(也称电子文本)是以文字及符号为主的一种数字媒体，下面关于数字文本的有关叙述中，错误的是()。

下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是__________【41】；组成部分B是__________【42】。

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

ThemajorityofpeopleinScotlandareinfavorbreakingawayfromtherestoftheUKandbecomingindependent,accordingtoap

男性，28岁。体力劳动时突然出现剧烈头痛，难以忍受，急送医院。体检：神清，颅神经正常，四肢活动正常，颈有抵抗，克氏征阳性，最可能的诊断为

要比较甲、乙两厂某工种工人某职业病患病萃的高低，采取标准化法的原理是

关于乳酸循环的叙述，不正确的是

某企业外部融资占销售增长的百分比为5％，若上年营业收入为1000万元，预计营业收入增加200万元，则相应外部应追加的融资额为()万元。

下列关于企业内部劳动规则的说法错误的是()。

沉没成本是指已经付出且不可收回的成本。沉没成本是由过去的决策或环境决定的，它所造成的成本是不能由现在或将来的任何决策而改变的。根据上述定义，下列不涉及沉没成本的是()。

并发操作可能会产生数据不一致，用什么方法能避免这些不一致的情况?一——

信息传输的安全应保证信息在网络传输的过程中不被泄漏和不被攻击，下列哪些属于在网络中攻击的方法?Ⅰ．复制信息 Ⅱ．剪裁信息 Ⅲ．窃听信息

WhenCarlyFiorinabecameHewlett-Packard’sfirstfemalechiefexecutiveofficer,theexistenceofherhousehusband,FrankFiori

下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是【41】；组成部分B是【42】。

信息传输的安全应保证信息在网络传输的过程中不被泄漏和不被攻击，下列哪些属于在网络中攻击的方法?Ⅰ．复制信息　　Ⅱ．剪裁信息　　Ⅲ．窃听信息