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

admin2010-05-13 72

问题设平衡的二叉排序树(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://www.kaotiyun.com/show/LMSZ777K

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

已知R1=1，R2=0xFFFFFFFF，执行指令EORR0，R1，R2后，再执行指令ANDR1，R0，R1，则R0=【55】，R1=【56】。

嵌入式系统【71】的时候，所有的微处理器通常都从某个由CPU制造商预先安排的地址上取指令。例如，基于ARM920T核的微处理器从地址0x00000000取得它的第一条指令。CPU执行的第一条指令就是【72】程序中的第一条指令。

某ARM汇编语言程序要调用子程序，子程序名为MySubrutine，则调用该子程序的指令为【55】，子程序返回调用程序的指令为【56】。

无线局域网采用的通信协议主要是802．11，通常也称为【45】，为了能满足传输语音、数据、图像等需要，目前使用的802．11n协议其数据传输速率可达【46】Mbps甚至更高，相应的产品已经广泛使用。

Linux内核主要由5个子系统组成，下面选项中不属于这5个子系统的是()。

嵌入式Linux操作系统的组成，不包括()

IP协议在计算机网络的互连中起着非常重要的作用。目前广泛使用的IP协议的版本是第【45】版，每个IP地址用【46】位二进制表示。

ARM状态下指令代码长度的位数为【49】_位、Thumb状态下指令代码长度的位数为【50】_位。

UART传送一个字符时有固定的格式，如下图所示。图中①和②分别是【61】位和【62】位。

A．2天内B．2～3天C．3天内D．3～4天E．5天

口腔颌面部恶性肿瘤中，最常见的类型为

肝性脑病病人暂停蛋白质饮食，是为了

不属于担任单位会计机构负责人、会计主管人员的基本条件的是()。

当今世界，科学技术日新月异，以信息技术、()为代表的新技术产业迅速发展，深刻影响着各国的政治、经济、军事、文化等方面。

区别拐卖妇女罪与绑架罪的关键是()(2008年基础课单选第12题)

以下是关于某中学甲班同学参加夏令营的三个断定：(1)甲班有学生参加了夏令营。(2)甲班所有学生都没有参加夏令营。(3)甲班的蔡明没有参加夏令营。如果这三个断定中只有一项为真，则以下哪项一定为真?

Exactlywherewewillstandinthelongwaragainstdiseasebytheyear2050isimpossibletosay.【61】Butifdevelopmentsinr

A、Shelacksconfidenceinherself.B、Sheisnotinterestedincomputerprogramming.C、Shehasneversignedupforanycompetitio

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

三级数据库技术

NCRE全国计算机三级

已知R1=1，R2=0xFFFFFFFF，执行指令EORR0，R1，R2后，再执行指令ANDR1，R0，R1，则R0=【55】，R1=【56】。

嵌入式系统【71】的时候，所有的微处理器通常都从某个由CPU制造商预先安排的地址上取指令。例如，基于ARM920T核的微处理器从地址0x00000000取得它的第一条指令。CPU执行的第一条指令就是【72】程序中的第一条指令。

某ARM汇编语言程序要调用子程序，子程序名为MySubrutine，则调用该子程序的指令为【55】，子程序返回调用程序的指令为【56】。

无线局域网采用的通信协议主要是802．11，通常也称为【45】，为了能满足传输语音、数据、图像等需要，目前使用的802．11n协议其数据传输速率可达【46】Mbps甚至更高，相应的产品已经广泛使用。

Linux内核主要由5个子系统组成，下面选项中不属于这5个子系统的是()。

嵌入式Linux操作系统的组成，不包括()

IP协议在计算机网络的互连中起着非常重要的作用。目前广泛使用的IP协议的版本是第__________【45】版，每个IP地址用__________【46】位二进制表示。

ARM状态下指令代码长度的位数为【49】_______位、Thumb状态下指令代码长度的位数为【50】_______位。

UART传送一个字符时有固定的格式，如下图所示。图中①和②分别是【61】位和【62】位。

A．2天内B．2～3天C．3天内D．3～4天E．5天

口腔颌面部恶性肿瘤中，最常见的类型为

肝性脑病病人暂停蛋白质饮食，是为了

不属于担任单位会计机构负责人、会计主管人员的基本条件的是()。

当今世界，科学技术日新月异，以信息技术、()为代表的新技术产业迅速发展，深刻影响着各国的政治、经济、军事、文化等方面。

区别拐卖妇女罪与绑架罪的关键是()(2008年基础课单选第12题)

以下是关于某中学甲班同学参加夏令营的三个断定：(1)甲班有学生参加了夏令营。(2)甲班所有学生都没有参加夏令营。(3)甲班的蔡明没有参加夏令营。如果这三个断定中只有一项为真，则以下哪项一定为真?

Exactlywherewewillstandinthelongwaragainstdiseasebytheyear2050isimpossibletosay.【61】Butifdevelopmentsinr

A、Shelacksconfidenceinherself.B、Sheisnotinterestedincomputerprogramming.C、Shehasneversignedupforanycompetitio

IP协议在计算机网络的互连中起着非常重要的作用。目前广泛使用的IP协议的版本是第【45】版，每个IP地址用【46】位二进制表示。

ARM状态下指令代码长度的位数为【49】_位、Thumb状态下指令代码长度的位数为【50】_位。