首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
假设有一个长度为n的有序序列,在进行查找时,可以借助二叉树来进行,请结合二叉树的性质来分析二分查找的最坏性能和平均性能。
假设有一个长度为n的有序序列,在进行查找时,可以借助二叉树来进行,请结合二叉树的性质来分析二分查找的最坏性能和平均性能。
admin
2010-04-24
46
问题
假设有一个长度为n的有序序列,在进行查找时,可以借助二叉树来进行,请结合二叉树的性质来分析二分查找的最坏性能和平均性能。
选项
答案
假设判定树的内部结点的总数为n=2
h-1
-1。则判定树是深度为h=lg(n+1)的满二叉树,树中第k层上的结点的个数为2
h-1
,查找它们所需要比较的次数是k。则在等概率下,二分查找成功时的平均查找长度为:[*],如果n很大,则可以用如下近似公式:lg(n+1)-1,作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度,在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上
解析
转载请注明原文地址:https://kaotiyun.com/show/QMAx777K
本试题收录于:
数据结构题库理工类分类
0
数据结构
理工类
相关试题推荐
在OSI中,完成源机网络层来的数据可靠地传输到相邻节点的目标机网络层功能的层次是_______。
UDP的段结构中,源端口所占的长度为()
在OSI七层模型中负责数据通信的最高层,并且面向网络通信的低三层和面向信息处理的高三层之间的中间层的层次是()
为了能够使客户端程序查询不同的信息资源时有统一的访问方法而定义的一种地址标识方法是()
为什么说中央银行票据的发行丰富了公开市场业务操作工具?
下列关于间接融资的说法中,正确的有()
下列说法中不正确的是()
如图所示交通图的物资调运问题,试作出第一流向图.
具有n个结点的完全二叉树,顺序存储在一维数组A[1…,z]中,设计算法将A中顺序存储变为二叉链表存储的二叉树。
随机试题
患者,女,22岁。主诉咀嚼无力两年余。口腔检查:下颌第一恒磨牙近远中牙周袋约8mm,牙齿松动Ⅰ度,口腔卫生尚佳,下前牙牙石(+),松动Ⅰ度,拟诊为
以“疏风清热,宣肺止咳”为功用的方剂是
自我意识和自然人成为社会人标志着
仲裁员陈某有哪种情形时,乙可以提出回避申请?()。仲裁过程中,甲发现乙试图将其欲购的尼桑轿车藏匿到外地,于是向仲裁委员会申请财产保全,此时,仲裁委员会的正确做法是()。
打桩的人土深度控制,对于承受轴向荷载的摩擦桩,应( )。
根据《担保法》规定,办理财产抵押贷款的,除签订抵押合同外,还应()才能取得贷款。
提倡自我激励、自我调节的学习,情感教育、真实性评定等主张的是人本主义理论。()
某单位准备组建几支运动队,开展员工运动情况的调查,发现喜欢篮球的员工中,只要是人力资源部的员工,则其也一定喜欢登山。下列推断正确的是:
酸雨被称为“空中死神”,它会破坏土壤的结构和营养,使土壤贫瘠化,危害动植物生长,其pH值范围()。
A、SouthwesternChina.B、NorthernChina.C、NorthernCalifornia.D、SouthernCalifornia.D
最新回复
(
0
)