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

admin2010-05-13 35

问题设平衡的二叉排序树(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，则可以证明它的深度和logN是同数量级的(N为结点个数)。由此，它的平均查找长度也和logN同数量级。

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

下面关于实时系统的叙述中，错误的是()。

对于内存容量而言，1KB=【59】B；而对于外存(如磁盘、U盘等)容量而言，1KB=【60】B。

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

下面与AMBA(AdvancedMicrocontrollerBusArchitecttJre)有关的叙述中，错误的是()。

如果一种存储器的总线工作频率为333MHz，数据线宽度为32位，每个存储器总线周期传输1次数据，则该存储器的带宽为【55】_______MB／s。AM29LV160是一种典型的NORFlash芯片，芯片内部具有20条地址线和16条数据线，该芯片的存储容量

在ARM指令中，两个无符号数在寄存器R5和R6中，若R5＜R6，则将R5与R6进行逻辑与操作，结果放R7中，并要求更新程序状态寄存器的状态位。用两条指令完成，则分别为_【51】和_【52】

Linux操作系统内核的网络模块可分为两部分：一部分提供对各种网络资源访问的控制，称为网络【75】；另一部分提供对各种网络硬件的支持，称为网络【76】。

VSAT系统的典型结构由()、室外单元、室内单元三部分组成。

孙先生，45岁。上腹痛5年，常发生在空腹饥饿时，进食后缓解，近3d出现黑便。为确定诊断应选择哪种检查()。

A．独活、川乌、威灵仙、防己B．防己、络石藤、蕲蛇、穿山龙C．川乌、独活、威灵仙、松节D．防己、络石藤、豨莶草、穿山龙E．蚕沙、伸筋草、秦艽、桑枝药性寒凉，以治风湿热痹的药物是()

适宜采用口腔测量体温的是

A．胆怯易惊，心悸失眠B．精神涣散，喜笑不休C．烦躁多怒，胸胁胀闷D．情志抑郁，忧愁不乐E．失眠多梦，头晕健忘悲恐证的临床表现是

人工挖孔桩的桩位偏差不是其主控项目。（）

室内生活污水管道应按管道的()设置排水坡度。

期货交易所交易规则应当载明的事项有(　　)。

五行学说中，金克木，木克土，水生木，金生土。()

Islanguage,likefood,abasichumanneedwithoutwhichachildatacriticalperiodoflifecanbestarvedanddamaged?Judgin

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

三级数据库技术

NCRE全国计算机三级

下面关于实时系统的叙述中，错误的是()。

对于内存容量而言，1KB=【59】B；而对于外存(如磁盘、U盘等)容量而言，1KB=【60】B。

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

下面与AMBA(AdvancedMicrocontrollerBusArchitecttJre)有关的叙述中，错误的是()。

如果一种存储器的总线工作频率为333MHz，数据线宽度为32位，每个存储器总线周期传输1次数据，则该存储器的带宽为【55】_______MB／s。AM29LV160是一种典型的NORFlash芯片，芯片内部具有20条地址线和16条数据线，该芯片的存储容量

在ARM指令中，两个无符号数在寄存器R5和R6中，若R5＜R6，则将R5与R6进行逻辑与操作，结果放R7中，并要求更新程序状态寄存器的状态位。用两条指令完成，则分别为___________【51】和___________【52】

Linux操作系统内核的网络模块可分为两部分：一部分提供对各种网络资源访问的控制，称为网络__________【75】；另一部分提供对各种网络硬件的支持，称为网络__________【76】。

VSAT系统的典型结构由()、室外单元、室内单元三部分组成。

孙先生，45岁。上腹痛5年，常发生在空腹饥饿时，进食后缓解，近3d出现黑便。为确定诊断应选择哪种检查()。

A．独活、川乌、威灵仙、防己B．防己、络石藤、蕲蛇、穿山龙C．川乌、独活、威灵仙、松节D．防己、络石藤、豨莶草、穿山龙E．蚕沙、伸筋草、秦艽、桑枝药性寒凉，以治风湿热痹的药物是()

适宜采用口腔测量体温的是

A．胆怯易惊，心悸失眠B．精神涣散，喜笑不休C．烦躁多怒，胸胁胀闷D．情志抑郁，忧愁不乐E．失眠多梦，头晕健忘悲恐证的临床表现是

人工挖孔桩的桩位偏差不是其主控项目。（）

室内生活污水管道应按管道的()设置排水坡度。

期货交易所交易规则应当载明的事项有( )。

五行学说中，金克木，木克土，水生木，金生土。()

Islanguage,likefood,abasichumanneedwithoutwhichachildatacriticalperiodoflifecanbestarvedanddamaged?Judgin

在ARM指令中，两个无符号数在寄存器R5和R6中，若R5＜R6，则将R5与R6进行逻辑与操作，结果放R7中，并要求更新程序状态寄存器的状态位。用两条指令完成，则分别为_【51】和_【52】

Linux操作系统内核的网络模块可分为两部分：一部分提供对各种网络资源访问的控制，称为网络【75】；另一部分提供对各种网络硬件的支持，称为网络【76】。

期货交易所交易规则应当载明的事项有(　　)。