首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均拉索长度为
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均拉索长度为
admin
2010-05-13
52
问题
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均拉索长度为
选项
A、O(1)
B、O(log
2
n)
C、O(n)
D、O(nlog
2
n)
答案
2
解析
平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1,若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和log
2
n是同数量级的(N为结点个数)。因此,它的平均查找长度也和log
2
n同数量级。
转载请注明原文地址:https://kaotiyun.com/show/AjSZ777K
本试题收录于:
三级数据库技术题库NCRE全国计算机三级分类
0
三级数据库技术
NCRE全国计算机三级
相关试题推荐
下面关于NORFlash和NANDFlash的叙述中,错误的是()。
嵌入式系统使用的存储器有多种类型,按照其存取特性可分为随机存取存储器(英文缩写为RAM)和__________【57】存储器(英文缩写为__________【58】)。
下面关于S3C2410的实时时钟(RTC)组件的叙述中,错误的是()。
在μC/OS-Ⅱ操作系统中,在使用内核提供的任何功能之前,必须先调用【75】()函数进行内核初始化。函数【76】()将启动多任务调度并从就绪态任务中选择最高优先级的任务转入运行态。
IP协议在计算机网络的互连中起着重要的作用。下面有关IP地址的叙述中,错误的是()。
用下图可以辅助解释SPI的工作原理。假设主机的移位寄存器A中已存入11001010,从机的移位寄存器B中已存入11110000,则在主机发出8个SCK有效信号后,主机移位寄存器A和从机移位寄存器B中的内容分别是()。
下面有关片上调试技术的描述语句中,不恰当的是()。
Linux内核主要是由5个子系统组成的,如下图所示,其中的A是【73】子系统,B是【74】子系统。
μC/OS-Ⅱ的事件控制块有4种类型,需要使用4个不同的函数来创建。如下选项中哪一个用于创建事件控制块?
利用中间件Middleware的高层【】可以将底层网络协议与实现技术隔离开来,使得程序员可以将精力集中在应用软件编程上。
随机试题
A.因子Ⅻ激活 B.凝血因子Ⅲ大量入血 C.大量膜磷脂促凝 D.直接激活凝血酶原 E.清除凝血物质的功能受损单核-巨噬细胞系统功能障碍诱发DIC是因为
一水泥厂工人,男,70kg,冒险在高温水泥窖中清炉渣,突然小泥窖坍塌,高温粉尘弥漫。患者大声呼救,数分钟后被工友救出,送医院抢救时见,神智清醒,对答切题,但语音粗哑,全身除有头发部位、双足、会阴部及双臂各有一块相当于患者1/2手掌大的创面未烧伤,双上肢因有
患者男,56岁。因车祸急诊入院。患者诊断:右侧两根肋骨骨折、右股骨粉碎性骨折,软组织撕裂伤、失血性休克。既往无输血史。经补液、输血治疗,无任何输血不良反应发生,血压上升至100/70mmHg,急诊手术治疗。术中实习护士给予加温的血液2U,输血后约50分钟,
亚硝酸钠滴定法中加入适量溴化钾的作用是
在三维空间中方程y2一z2=1所代表的图形是:
某出租设备价格50万元,租期为5年,折现率8%,附加率4%,采用附加率法计算租金时,则每年租金不能低于()万元。
有两个班的小学生要到少年宫参加活动,但只有一辆车接送。第一班的学生坐车从学校出发的同时,第二班的学生开始步行,车到途中某处,让第一班的学生下车步行,车立刻返回接第二班的学生上车并直接开往少年宫。该车载学生时车速为40千米/时,空车时为50千米/时,学生步行
用人单位延长工作时间不受《劳动法》第41条限制的特殊情况有哪些?
电视是现代文明的产物,但也给人们带来很多麻烦。对于有孩子的家庭,来自电视节目正反两方面的诱惑力都很大。电视看久了,也会影响学习。更使家长担心的是电视中的暴力片等的副作用。因此,家长应对孩子看电视给予指导与约束。以下哪种做法与以上观点不符?
全面从严治党的长远之策、根本之策是()
最新回复
(
0
)