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

admin2010-05-13 38

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

嵌入式系统的应用形式是多种多样的，不同的嵌入式应用系统，需要选择适合其应用需求的开发工具来进行开发。采用开发工具的主要目的是()。

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

基于ARM内核的嵌入式芯片是以ARM内核为基础，通过AMBA总线将其他硬件组件连接在一起的。下面列出的4个组件中，哪一个组件是挂在AMBA的APB总线上的?()

常见的嵌入式Linux进程间通信机制包括信号、管道、【75】、信号量、共享内存和【76】

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

利用下图LED数码管接口显示字符“A”的汇编语言程序片段如下，请填空将语句补充完整。MOVR0，#__________【65】；“A”的共阳编码，用16进制表示LDRR1，=0x10000000；指向nGCS2段中的任何一个地址STRBR0，_

μC／OS－II中调用中断退出函数OSIntExit()标志着中断服务子程序的【75】_，OSIntExit()将中断嵌套层数计数器的值【76】_。

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

在ADS1．2的集成开发环境中，若生成的输出文件需要包含所有的调试信息，那么，生成目标应该选择为【79】。若目标系统地址映射关系比较复杂时，应使用【80】格式的文件来说明地址映射方式。

王某\张某和李某成立一合伙企业，合伙协议中约定由王某全权负责企业的事务，以下说法不正确的是()

下列关于漏洞扫描技术和工具的描述中，正确的是()。

新颖性

A．心电图V1～V3导联出现特征性改变B．心电图V2～V5导联出现特征性改变C．心电图V2、V4R导联出现特征性改变D．心电图Ⅱ、Ⅲ、aVF导联出现特征性改变E．心电图I、aVL导联出现特征性改变急性心肌梗死下壁定位是

工程项目策划旨在为项目建设的决策和实施(　　)。

为防止火势失去控制，继续扩大燃烧而造成灾害，需要采取必要的措施将火扑灭。下列灭火过程中所采取的措施，错误的是()

加强会计职业道德建设的意义主要包括()。

期货交易所的工作人员履行职务，遇到与(　　)有利害关系的情形时，应当回避。

行政处罚，是行政机关或其他行政主体依法律设定的行政处罚权和程序，对违反行政法规范的相对方给予行政制裁的具体行政行为。其特征为(　　)。

【2011年江苏省第90题】甲、乙两人从运动场同一起点同向出发，甲跑步速度为200米／分钟，乙步行，当甲第5次超越乙时，乙正好走完第三圈，再过1分钟，甲在乙前方多少米?

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

三级数据库技术

NCRE全国计算机三级

嵌入式系统的应用形式是多种多样的，不同的嵌入式应用系统，需要选择适合其应用需求的开发工具来进行开发。采用开发工具的主要目的是()。

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

基于ARM内核的嵌入式芯片是以ARM内核为基础，通过AMBA总线将其他硬件组件连接在一起的。下面列出的4个组件中，哪一个组件是挂在AMBA的APB总线上的?()

常见的嵌入式Linux进程间通信机制包括信号、管道、__________【75】、信号量、共享内存和__________【76】

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

利用下图LED数码管接口显示字符“A”的汇编语言程序片段如下，请填空将语句补充完整。MOVR0，#__________【65】；“A”的共阳编码，用16进制表示LDRR1，=0x10000000；指向nGCS2段中的任何一个地址STRBR0，_

μC／OS－II中调用中断退出函数OSIntExit()标志着中断服务子程序的【75】_______，OSIntExit()将中断嵌套层数计数器的值【76】_______。

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

在ADS1．2的集成开发环境中，若生成的输出文件需要包含所有的调试信息，那么，生成目标应该选择为__________【79】。若目标系统地址映射关系比较复杂时，应使用__________【80】格式的文件来说明地址映射方式。

王某\张某和李某成立一合伙企业，合伙协议中约定由王某全权负责企业的事务，以下说法不正确的是()

下列关于漏洞扫描技术和工具的描述中，正确的是()。

新颖性

A．心电图V1～V3导联出现特征性改变B．心电图V2～V5导联出现特征性改变C．心电图V2、V4R导联出现特征性改变D．心电图Ⅱ、Ⅲ、aVF导联出现特征性改变E．心电图I、aVL导联出现特征性改变急性心肌梗死下壁定位是

工程项目策划旨在为项目建设的决策和实施( )。

为防止火势失去控制，继续扩大燃烧而造成灾害，需要采取必要的措施将火扑灭。下列灭火过程中所采取的措施，错误的是()

加强会计职业道德建设的意义主要包括()。

期货交易所的工作人员履行职务，遇到与( )有利害关系的情形时，应当回避。

行政处罚，是行政机关或其他行政主体依法律设定的行政处罚权和程序，对违反行政法规范的相对方给予行政制裁的具体行政行为。其特征为( )。

【2011年江苏省第90题】甲、乙两人从运动场同一起点同向出发，甲跑步速度为200米／分钟，乙步行，当甲第5次超越乙时，乙正好走完第三圈，再过1分钟，甲在乙前方多少米?

常见的嵌入式Linux进程间通信机制包括信号、管道、【75】、信号量、共享内存和【76】

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

μC／OS－II中调用中断退出函数OSIntExit()标志着中断服务子程序的【75】_，OSIntExit()将中断嵌套层数计数器的值【76】_。

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

在ADS1．2的集成开发环境中，若生成的输出文件需要包含所有的调试信息，那么，生成目标应该选择为【79】。若目标系统地址映射关系比较复杂时，应使用【80】格式的文件来说明地址映射方式。

工程项目策划旨在为项目建设的决策和实施(　　)。

期货交易所的工作人员履行职务，遇到与(　　)有利害关系的情形时，应当回避。

行政处罚，是行政机关或其他行政主体依法律设定的行政处罚权和程序，对违反行政法规范的相对方给予行政制裁的具体行政行为。其特征为(　　)。