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

admin2009-01-19 75

问题设平衡的二叉排序树(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://jikaoti.com/ti/xxQ7FFFM

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

下面关于闪存盘(也称为优盘)的叙述中，错误的是

若汇编语言程序的宏定义中使用了标号，则该标号必须用下列哪种伪指令于以说明?

下列关于PC机软件的叙述中，错误的是

如果8251A设定为异步通信方式，发送器时钟输入端和接收器时钟输入端都连接到频率为2KHz的输入信号，波特率为1200，字符数据长度为7位，1位停止位，采用偶校验，则8251A的方式控制字为【　　】。

Internet(互联网)是一个庞大的计算机网络，每一台入网的计算机必须有一个唯一的标识，以便相互通信，该标识就是常说的【　　】。

如果选择波特率因子为16，在接收时，采用波特率的16倍频率作为接收时钟，其目的是(　　　)。

请编制程序，其功能是：内存中连续存放着20个无符号二进制字序列Xi(i＝1,2,…,20)，字的最高3位为000，此序列对应某一信号在一段时间内的连续变化，现对该信号进行一阶低通数字滤波，其滤波方程为：Yi＝(15*Yi-1/16)+(Xi/16)

请编制程序，其功能是：内存中连续存放着20个无符号字节数序列，请将它们排成升序(从小到大)。例如：内存中有01H,04H,02H…(假设后17个字节均大与04H)结果为01H,02H,04H…(后跟17个字节，按从小到大的顺

在软件测试中，检查各模块间接口关系、各模块组合在一起时的功能是否满足总的功能要求的测试是(　　　)

在现代社会中，各个不同政治制度的国家制定其教育目的的首要依据是()

新生儿，19天，拒乳，发热3天，皮肤黄染退而复现2天。精神萎靡、嗜睡，脐窝有少许脓性分泌物，诊断为败血症。其首选护理措施是

中毒时，有中枢兴奋作用的药物是有中枢抑制作用的药物是

作者甲将自己创作的一部小说交乙出版社出版，但双方始终未签订出版合同，事后该作者又与丙出版社会签订了专有出版合同，将此书交丙出版。现乙对甲和丙提出异议，本案依法应如何认定?

(2018年)根据公司法律制度的规定，下列各项中，应当由上市公司股东大会作出决议的有()。

幼儿的自我评价主要有以下特点()。

我国《宪法》规定：“中华人民共和国的一切权力属于人民”。这一规定体现的宪法原则是()

「私はあしたコンサートへ行くつもりですが、あなたも行きませんか。」「ええ、()、私もいきたいです。」

Whatisthetopicofthetalk?

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

三级数据库技术

NCRE全国计算机三级

下面关于闪存盘(也称为优盘)的叙述中，错误的是

若汇编语言程序的宏定义中使用了标号，则该标号必须用下列哪种伪指令于以说明?

下列关于PC机软件的叙述中，错误的是

如果8251A设定为异步通信方式，发送器时钟输入端和接收器时钟输入端都连接到频率为2KHz的输入信号，波特率为1200，字符数据长度为7位，1位停止位，采用偶校验，则8251A的方式控制字为【 】。

Internet(互联网)是一个庞大的计算机网络，每一台入网的计算机必须有一个唯一的标识，以便相互通信，该标识就是常说的【 】。

如果选择波特率因子为16，在接收时，采用波特率的16倍频率作为接收时钟，其目的是( )。

请编制程序，其功能是：内存中连续存放着20个无符号二进制字序列Xi(i＝1,2,…,20)，字的最高3位为000，此序列对应某一信号在一段时间内的连续变化，现对该信号进行一阶低通数字滤波，其滤波方程为：Yi＝(15*Yi-1/16)+(Xi/16)

请编制程序，其功能是：内存中连续存放着20个无符号字节数序列，请将它们排成升序(从小到大)。例如：内存中有01H,04H,02H…(假设后17个字节均大与04H)结果为01H,02H,04H…(后跟17个字节，按从小到大的顺

在软件测试中，检查各模块间接口关系、各模块组合在一起时的功能是否满足总的功能要求的测试是( )

在现代社会中，各个不同政治制度的国家制定其教育目的的首要依据是()

新生儿，19天，拒乳，发热3天，皮肤黄染退而复现2天。精神萎靡、嗜睡，脐窝有少许脓性分泌物，诊断为败血症。其首选护理措施是

中毒时，有中枢兴奋作用的药物是有中枢抑制作用的药物是

作者甲将自己创作的一部小说交乙出版社出版，但双方始终未签订出版合同，事后该作者又与丙出版社会签订了专有出版合同，将此书交丙出版。现乙对甲和丙提出异议，本案依法应如何认定?

(2018年)根据公司法律制度的规定，下列各项中，应当由上市公司股东大会作出决议的有()。

幼儿的自我评价主要有以下特点()。

我国《宪法》规定：“中华人民共和国的一切权力属于人民”。这一规定体现的宪法原则是()

「私はあしたコンサートへ行くつもりですが、あなたも行きませんか。」「ええ、()、私もいきたいです。」

Whatisthetopicofthetalk?

如果8251A设定为异步通信方式，发送器时钟输入端和接收器时钟输入端都连接到频率为2KHz的输入信号，波特率为1200，字符数据长度为7位，1位停止位，采用偶校验，则8251A的方式控制字为【　　】。

Internet(互联网)是一个庞大的计算机网络，每一台入网的计算机必须有一个唯一的标识，以便相互通信，该标识就是常说的【　　】。

如果选择波特率因子为16，在接收时，采用波特率的16倍频率作为接收时钟，其目的是(　　　)。

在软件测试中，检查各模块间接口关系、各模块组合在一起时的功能是否满足总的功能要求的测试是(　　　)