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

admin2010-05-13 51

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

在Internet中负责选择合适的路由，使发送的数据分组(packet)能够正确无误地按照地址找到目的计算机所使用的【45】协议簇中的【46】协议。

下面关于嵌入式系统存储器的叙述中，错误的是()。

程序代码中，执行时不可分割的代码称为【75】_。一旦这部分代码开始执行，则不希望系统进行任务调度。在μC／OS－II系统中，可以调用函数【76】_(void)锁定调度器。

在μC／OS-Ⅱ中，用于释放信号量的函数为INT8U【73】(OS＿EVENT*pevent)。周期执行的任务一般采用循环结构，并在每次完成具体功能后调用系统延时函数【74】等待下一个执行周期。

I2C可用于连接嵌入式处理器及其外围器件，它是广泛采用的一种串行【59】双工传输的总线标准。I2C总线中，发起数据传输操作的I2C器件是【60】控器件。

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

下面的描述语句中不正确的是()。

嵌入式系统使用的存储器可以划分成不同的层次，下列叙述中，错误的是()。

在数据库的三级模式体系结构中，概念模式与内模式之间的映像(概念模式/内模式)，实现了数据的()独立性。

Paymentsshallbemadebyusafterreceiptoftheshippingdocumentsspecifiedinclause10ofthiscontract.

A保留时间B峰面积C电泳淌度D电渗E理论塔板数哪项能够决定组分是否能被电泳法分离

铸造金属全冠修复最基本的固位形是

一年季节中，“长夏”所属的是

A/肥厚型心肌病B/围生期心肌病C/致心律失常型右室心肌病D/特异性心肌病E/不定型的心肌病患者男性，40岁，运动时出现眩晕、胸痛2年，冠状动脉造影检查未见异常，体格检查心界不大，胸骨左缘第3～4肋间可听到粗糙的

只有当风险已经降低时，才能开始或继续工作。如果无限的资源投入也不能降低风险，就必须禁止工作。上述风险控制策划是针对()风险采取的措施。

家庭访问一般分为幼儿入园前家访和入园后家访。入园后家访又可以分为________。

Advertiserstendtothinkbigandperhapsthisiswhythey’realwayscominginforcriticism.Theircriticsseemtoresentthem

某小区发生一起老公打老婆的事件，女子哭声厉害，邻居报警。指挥中心指令派出所民警处理。民警的下列做法不恰当的是()。

Experimentsonmonkeyswereviewedmuchmorenegativelythanthoseinvolvingmouse.Indeed,onlyexperimentstodevelop【M1】_____

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

三级数据库技术

NCRE全国计算机三级

在Internet中负责选择合适的路由，使发送的数据分组(packet)能够正确无误地按照地址找到目的计算机所使用的【45】协议簇中的【46】协议。

下面关于嵌入式系统存储器的叙述中，错误的是()。

程序代码中，执行时不可分割的代码称为【75】_______。一旦这部分代码开始执行，则不希望系统进行任务调度。在μC／OS－II系统中，可以调用函数【76】_______(void)锁定调度器。

在μC／OS-Ⅱ中，用于释放信号量的函数为INT8U【73】(OS＿EVENT*pevent)。周期执行的任务一般采用循环结构，并在每次完成具体功能后调用系统延时函数【74】等待下一个执行周期。

I2C可用于连接嵌入式处理器及其外围器件，它是广泛采用的一种串行【59】双工传输的总线标准。I2C总线中，发起数据传输操作的I2C器件是【60】控器件。

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

下面的描述语句中不正确的是()。

嵌入式系统使用的存储器可以划分成不同的层次，下列叙述中，错误的是()。

在数据库的三级模式体系结构中，概念模式与内模式之间的映像(概念模式/内模式)，实现了数据的()独立性。

Paymentsshallbemadebyusafterreceiptoftheshippingdocumentsspecifiedinclause10ofthiscontract.

A保留时间B峰面积C电泳淌度D电渗E理论塔板数哪项能够决定组分是否能被电泳法分离

铸造金属全冠修复最基本的固位形是

一年季节中，“长夏”所属的是

A/肥厚型心肌病B/围生期心肌病C/致心律失常型右室心肌病D/特异性心肌病E/不定型的心肌病患者男性，40岁，运动时出现眩晕、胸痛2年，冠状动脉造影检查未见异常，体格检查心界不大，胸骨左缘第3～4肋间可听到粗糙的

只有当风险已经降低时，才能开始或继续工作。如果无限的资源投入也不能降低风险，就必须禁止工作。上述风险控制策划是针对()风险采取的措施。

家庭访问一般分为幼儿入园前家访和入园后家访。入园后家访又可以分为________。

Advertiserstendtothinkbigandperhapsthisiswhythey’realwayscominginforcriticism.Theircriticsseemtoresentthem

某小区发生一起老公打老婆的事件，女子哭声厉害，邻居报警。指挥中心指令派出所民警处理。民警的下列做法不恰当的是()。

Experimentsonmonkeyswereviewedmuchmorenegativelythanthoseinvolvingmouse.Indeed,onlyexperimentstodevelop【M1】_____

程序代码中，执行时不可分割的代码称为【75】_。一旦这部分代码开始执行，则不希望系统进行任务调度。在μC／OS－II系统中，可以调用函数【76】_(void)锁定调度器。

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