首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为
admin
2010-05-13
25
问题
设平衡的二叉排序树(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/j3SZ777K
本试题收录于:
三级数据库技术题库NCRE全国计算机三级分类
0
三级数据库技术
NCRE全国计算机三级
相关试题推荐
下面关于嵌入式系统中使用的触摸屏的叙述中,错误的是()。
在采用ADS1.2集成开发工具软件开发基于ARM微处理器的嵌入式系统软件时,下面有关地址映射的说明中,不正确的是()。
对于下图所示的采用行扫描方法的矩阵式键盘电路,在确定键盘中哪一个键被按下的过程中,需采用四根I/O引脚GPG4一GPG7作为行扣描信号的输__________【63】,四根I/O引脚GPF5-GPF8作为输__________【64】。
Thumb-2指令集提供了专门用于开、关中断的专用指令,关外部中断使用的指令为:__________【51】,开外部中断的指令为:__________【52】。
S3C2410与一位共阳接法的8段LED数码管的连接如下图所示。下面与该图相关的叙述中,错误的是()。
嵌入式系统的调试方法中有一种使用驻留监控软件的调试方法。所谓驻留监控软件是一段固化在【77】ROM中的程序。它是一种成本较低的调试方法,不需要专门的硬件调试和【78】设备。
为提高SoC芯片设计效率,减少重复开发,通常将合格的经过验证的IC设计文件存储在数据库中,供反复使用。这些IC电路具有固定的不可再分解的功能特性,并受到知识产权保护,人们称之为“知识产权核”或“IP核”。按照IC设计文件的类型,IP核通常分为三种【41】、
在ARM汇编语言程序设计中,经常用到子程序设计及调用,与子程序设计与调用无关的指令或伪指令是()。
设待排序关键码序列为(25,18,9,33,67,82,53,95,12,70),要按关键码值递增的顺序进行排序,采取以第一个关键码为分界元素的快速排序法,第一趟完成后关键码96被放到了第几个位置?
在有n个结点的二叉树的llink-rlink法存储表示中,n个结点所含有的2n个指针中,必有【】个为空指针。
随机试题
化工过程根据其操作方式可以分成哪几类?
1997年,我国再次进行的政府机构改革的目标和应遵循的原则是什么?
下列哪一项不属于调研人员对委托者的道德责任()
A肾上腺素B麻黄碱C异丙肾上腺素D特布他林E氨茶碱既能治疗支气管哮喘,又能治疗心源性哮喘的药物是
9个月男婴,腹泻,呕吐4天,大便为蛋花汤样,1天来伴明显口渴,尿少,精神不振。查体:方颅,皮肤弹性差,眼窝及前囟明显凹陷,血清钠140mmol/L。对该患儿的补液应首先选用以下哪种液体
患者,男性,56岁,缺失,缺隙窄,切1/3缺损,根长大,对颌为局部义齿人工牙。最佳修复设计是
下列关于凭证审核和记账操作说法中,正确的有()。
新中国成立后各时期的教育方针具有不同的时代特点。属于“文化大革命”时期的教育方针是()。
资料1在祖国的山山水水间,有这么一群人,他们或俯首案前,呕心沥血研究民间文化;或献身舞台,孜孜以求编演老百姓喜闻乐见的精彩节目;或走村串寨,把精神文化食粮播撒在田间地头……他们有一个共同的名字——“基层文化人”。2017年1月9日晚,“最美
Whatisthepriceofpumpkinsthisyear?
最新回复
(
0
)