首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均查找长度的数量级为 ______。
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均查找长度的数量级为 ______。
admin
2010-05-13
25
问题
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均查找长度的数量级为 ______。
选项
A、O(1)
B、0(log
2
n)
C、O(n)
D、0(nlog
2
n)
答案
2
解析
平衡二叉树又称AVL树。它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和logN是同数量级的(N为结点个数)。由此,它的平均查找长度也和logN同数量级。
转载请注明原文地址:https://kaotiyun.com/show/LMSZ777K
本试题收录于:
三级数据库技术题库NCRE全国计算机三级分类
0
三级数据库技术
NCRE全国计算机三级
相关试题推荐
S3C2410与一位共阳接法的8段LED数码管的连接如下图所示。下面与该图相关的叙述中,错误的是()。
酒店客房的门锁系统是由总台服务器和若干客房指纹锁组成,其基本功能具体描述如下:a、客房的指纹锁与总台服务器之间通过通信网络连接。b、旅客在总台登记住宿时,录入其指纹信息,并提取其特征值存储在总台服务器中。同时录入一个密码(若干位数字组成),以备指纹无法
数字图像的文件格式有多种,不同的文件格式采用不同的编码方法,具有不同的特点,适合不同的应用。其中【43】图像文件格式颜色数目较少(不超过256色),文件特别小,支持动画,适合互联网传输。【44】图像文件格式是静止图像数据压缩编码的国际标准,它在数码相机和互
下面是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图,其中的组成部分A是【41】_______接口;组成部分B是【42】_______接口。
在ARM汇编语言程序设计中常有子程序设计,下面指令中不属于子程序调用或者返回的指令是()。
基于嵌入式WEB的应用系统中,构件设计阶段需要设计支持以太网通信的电路,包括以太网控制电路及以太网__________【79】电路。若选用的以太网控制芯片为AX88796芯片,并用S3C2410芯片的nGCS2引脚连接到AX88796芯片的片选引脚上(即C
I2C总线被启动后,多个主机在每发送一个数据位时都要对SDA信号线电平进行检测,只要检测的电平与自己发出的电平__________【63】就会继续占用总线。总线控制遵循的原则是谁先发送__________【64】电平谁就会掌握对总线的控制权。
互联网借助TCP/IP协议把许多同构或异构的计算机网络互相连接起来,实现了遍布全球的计算机的互连、互通和互操作,其中的IP协议起着关键性的作用。下面有关IP协议的叙述中,错误的是()。
下图为8段LED数码管(图(a))及其共阳极(图(b))及共阴极(图(c))LED数码管的内部结构原理图。为显示字符“8”,加到共阳极及共阴极LED数码管的dp、g、f、e、d、c、b、a的编码分别为0x【65】及0x【66】。
IP协议在计算机网络的互连中起着重要的作用。下面有关IP地址的叙述中,错误的是()。
随机试题
根据《突发公共卫生事件应急条例》,突发公共卫生事件发生后,具体负责组织突发公共卫生事件查、控制和医疗救治工作的部门是县级以上地方人民政府()。
内部控制的目标不包括()
WWW浏览器有使用获取______上的各种资源。
A.先兆流产B.不全流C.稽留流产D.难免流产E.完全流产妊娠后阴道出血,量多,伴有组织块,检查子宫小于停经月份,宫口松软,有活动性出血。可能的诊断是
有关解剖学方位的描述,错误的是
A公司经常派业务员小赵与B公司订立合同。小赵调离后,又持盖有A公司公章的合同书与尚不知其已调离的B公司订立一份合同,并按照通常做法提走货款,后逃匿。对此A公司并不知情。B公司要求A公司履行合同,A公司认为该合同与己无关,予以拒绝。下列说法正确的是()。
设防烈度为7度时的毛料石砌体房屋总高度和层数不宜超过()。
下面关于电子邮件和即时通讯的说法正确的有()。
根据企业所得税的有关规定,下列各项中,属于免税收入的有()。
A、 B、 C、 D、 B
最新回复
(
0
)