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

admin2009-01-19 92

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

选项 A、O(1)
B、O(log₂n)
C、O(n)
D、O(n log₂n)

答案2

解析平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点韵左右子树的深度之差都不超过1，则可以证明它的深度和log₂n是同数量级的(N为结点个数)。因此，它的平均查找长度也和log₂n同数量级。

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

Pentium微处理器工作在实地址模式，使用A19-A0的20根地址线，该处理器支持的最大物理地址空间为_______。

Pentium　微处理器的存储器分页管理机制中，提供页目录表基地址的是(　　　)。

Windows98的屏幕保护程序的作用是(　　　)。

在Windows98中，msdos.sys　是一个十分重要的系统配置文件，通过对其修改(例如修改BootMulti、BootGUI、BootMenu　等命令)可以改变Windows98的启动方式。如果要使Windows98　启动时直接进入到DOS状态，该文

按照Pentium微处理器的存储器分页管理机制，线性地址00COFFFCH　的页表基地址是【　　】。

在下列进程调度算法中，可能引起进程长时间得不到运行的算法是(　　　)。

请编制程序，其功能是：从第0行第0列开始，依次取出N阶矩阵中对角线上的元素(字节型)并计算累加和(字型)，然后将其存放在指定的内存区中。例如：内存中有：01H，01H，01H，02H，02H，02H，03ff，03H，03H结果为：

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，【69】轻量化，占用存储资源【70】的特点。

在完全二叉树的顺序存储中，若结点i有左子女，则其左子女是结点()。

简述影响股利政策的因素。

A肾上腺素B麻黄碱C异丙肾上腺素D特布他林E氨茶碱既能治疗支气管哮喘，又能治疗心源性哮喘的药物是

传染病的治疗原则是

患者，男，29岁，舌体外伤出现部分组织缺损．处理原则是

在我国，对公司发行债券规定的条件有()。

目前，唯一没有资本金的中央银行是()。

人才的选拔与任用是政权建设中的重要问题，战国时期代表平民利益，主张尚贤，反对任人为亲的学派是()。

心理现象的产生方式是()。

A、 B、 C、 A现在十二点半了。该吃午饭了。

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

三级数据库技术

NCRE全国计算机三级

Pentium微处理器工作在实地址模式，使用A19-A0的20根地址线，该处理器支持的最大物理地址空间为_______。

Pentium 微处理器的存储器分页管理机制中，提供页目录表基地址的是( )。

Windows98的屏幕保护程序的作用是( )。

在Windows98中，msdos.sys 是一个十分重要的系统配置文件，通过对其修改(例如修改BootMulti、BootGUI、BootMenu 等命令)可以改变Windows98的启动方式。如果要使Windows98 启动时直接进入到DOS状态，该文

按照Pentium微处理器的存储器分页管理机制，线性地址00COFFFCH 的页表基地址是【 】。

在下列进程调度算法中，可能引起进程长时间得不到运行的算法是( )。

请编制程序，其功能是：从第0行第0列开始，依次取出N阶矩阵中对角线上的元素(字节型)并计算累加和(字型)，然后将其存放在指定的内存区中。例如：内存中有：01H，01H，01H，02H，02H，02H，03ff，03H，03H结果为：

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，__________【69】轻量化，占用存储资源__________【70】的特点。

在完全二叉树的顺序存储中，若结点i有左子女，则其左子女是结点()。

简述影响股利政策的因素。

A肾上腺素B麻黄碱C异丙肾上腺素D特布他林E氨茶碱既能治疗支气管哮喘，又能治疗心源性哮喘的药物是

传染病的治疗原则是

患者，男，29岁，舌体外伤出现部分组织缺损．处理原则是

在我国，对公司发行债券规定的条件有()。

目前，唯一没有资本金的中央银行是()。

人才的选拔与任用是政权建设中的重要问题，战国时期代表平民利益，主张尚贤，反对任人为亲的学派是()。

心理现象的产生方式是()。

A、 B、 C、 A现在十二点半了。该吃午饭了。

Pentium　微处理器的存储器分页管理机制中，提供页目录表基地址的是(　　　)。

Windows98的屏幕保护程序的作用是(　　　)。

在Windows98中，msdos.sys　是一个十分重要的系统配置文件，通过对其修改(例如修改BootMulti、BootGUI、BootMenu　等命令)可以改变Windows98的启动方式。如果要使Windows98　启动时直接进入到DOS状态，该文

按照Pentium微处理器的存储器分页管理机制，线性地址00COFFFCH　的页表基地址是【　　】。

在下列进程调度算法中，可能引起进程长时间得不到运行的算法是(　　　)。

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，【69】轻量化，占用存储资源【70】的特点。

　　A肾上腺素B麻黄碱C异丙肾上腺素D特布他林E氨茶碱既能治疗支气管哮喘，又能治疗心源性哮喘的药物是