假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

admin2010-04-24 41

问题假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

选项

答案假设判定树的内部结点的总数为n=2^h-1-1。则判定树是深度为h=lg(n+1)的满二叉树，树中第k层上的结点的个数为2^h-1，查找它们所需要比较的次数是k。则在等概率下，二分查找成功时的平均查找长度为：[*]，如果n很大，则可以用如下近似公式：lg(n+1)-1，作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上

解析

转载请注明原文地址:https://jikaoti.com/ti/61taFFFM

本试题收录于：数据结构题库理工类分类

数据结构

理工类

相关试题推荐

随机试题

最新回复(0)

假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

数据结构

理工类

IP地址的二进制数的字节个数是()

数据链路层通过使用计数器和_______来保证每帧都能被正确地递交给目标网络层一次。

在TCP的段结构中，端口地址的比特数为_______。

_______由域名空间、域名服务器和地址转换请求程序三部分组成。

马克思的货币需求理论表达式是

求解下列矩阵的最小化分派问题。(1)(2)(3)

某汽车运输公司有许多载重量为5吨的卡车，某天该公司接受了表7．5所示的9项运输业务。装卸点位置如图7．30所示的交通图(线上数字单位：km)。怎样安排卡车来完成这些运输业务才能够做到最节约?

如图C-4所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。

已知二叉树的前序遍历序列HACDFGBE，中序遍历序列为CAFDCHEB，请画出该二叉树，并给出后序遍历序列。

突发呼吸困难患者一侧胸部叩诊呈实音见于下述哪种情况

C型药物不良反应的特点有

A．昏迷患者B．间歇期后继续进行化疗的白血病患者C．脑中风一侧肢体瘫痪的患者D．腹部手术后第2天的患者E．剖宫产术后康复准备出院的产妇

某矩形基础受到建筑物传来的轴心压力值1200kN，基础尺寸为4m×2m(图5．3．4)，基础埋深1．5m，土的重度γ=17．5kN／m3。试问：基础面外G点下z=2．0m深度处的附加应力值(kPa)最接近下列()项。

甲向乙保险公司投保定期寿险8000元，后又向丙保险公司投保定期寿险5000元，当保险事故发生导致被保险人死亡后，(　　)。

读“长江水系图”(图2)，回答下列问题。长江“黄金水道”的优势有：________________

庭院经济是指农户充分利用家庭庭落的空间、周围非承包的空坪隙地和各种资源，从事高度集约化商品生产的一种经营形式，主要有种植业、养殖业、加工业。根据上述定义，下列属于庭院经济的是：

A、 B、 C、 B图片[A]是在商店门口，图片[B]是在学校门口，图片[C]是在图书馆门口，原句为“那我们到时候在学校门口见”，所以答案应该为[B]。

Thelanguageproducedbysecondlanguagelearnersistechnicallycalled

假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

数据结构

理工类

IP地址的二进制数的字节个数是()

数据链路层通过使用计数器和_______来保证每帧都能被正确地递交给目标网络层一次。

在TCP的段结构中，端口地址的比特数为_______。

_______由域名空间、域名服务器和地址转换请求程序三部分组成。

马克思的货币需求理论表达式是

求解下列矩阵的最小化分派问题。(1)(2)(3)

某汽车运输公司有许多载重量为5吨的卡车，某天该公司接受了表7．5所示的9项运输业务。装卸点位置如图7．30所示的交通图(线上数字单位：km)。怎样安排卡车来完成这些运输业务才能够做到最节约?

如图C-4所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。

已知二叉树的前序遍历序列HACDFGBE，中序遍历序列为CAFDCHEB，请画出该二叉树，并给出后序遍历序列。

突发呼吸困难患者一侧胸部叩诊呈实音见于下述哪种情况

C型药物不良反应的特点有

A．昏迷患者B．间歇期后继续进行化疗的白血病患者C．脑中风一侧肢体瘫痪的患者D．腹部手术后第2天的患者E．剖宫产术后康复准备出院的产妇

某矩形基础受到建筑物传来的轴心压力值1200kN，基础尺寸为4m×2m(图5．3．4)，基础埋深1．5m，土的重度γ=17．5kN／m3。试问：基础面外G点下z=2．0m深度处的附加应力值(kPa)最接近下列()项。

甲向乙保险公司投保定期寿险8000元，后又向丙保险公司投保定期寿险5000元，当保险事故发生导致被保险人死亡后，( )。

读“长江水系图”(图2)，回答下列问题。 长江“黄金水道”的优势有：________________

庭院经济是指农户充分利用家庭庭落的空间、周围非承包的空坪隙地和各种资源，从事高度集约化商品生产的一种经营形式，主要有种植业、养殖业、加工业。根据上述定义，下列属于庭院经济的是：

A、 B、 C、 B图片[A]是在商店门口，图片[B]是在学校门口，图片[C]是在图书馆门口，原句为“那我们到时候在学校门口见”，所以答案应该为[B]。

Thelanguageproducedbysecondlanguagelearnersistechnicallycalled

甲向乙保险公司投保定期寿险8000元，后又向丙保险公司投保定期寿险5000元，当保险事故发生导致被保险人死亡后，(　　)。

读“长江水系图”(图2)，回答下列问题。长江“黄金水道”的优势有：________________