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

admin2010-04-24 89

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

选项

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

解析

转载请注明原文地址:https://www.kaotiyun.com/show/QMAx777K

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

数据结构

理工类

相关试题推荐

随机试题

最新回复(0)

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

数据结构

理工类

数据由_______拆成若干个分组送给通信子网，由通信子网将分组传送到数据接收方。

在以特定模式01111110对信息位中的任何连续出现的5个“1”，发送方自动在其后插入一个“0”，而接收方则做该过程的逆操作，以此恢复原始信息实现数据的透明传输的帧同步方法称为()

用BSC规程传输一批汉字，若已知采用不带报头的分块传输，而且最大报文块长为129字节，共传输了5帧，其中最后一块报文长为101字节。问每个报文最多能传多少汉字?这批数据报共有多少汉字?

金融期权按其权利性质划分，可以分为、__。

下面是60个大学生一个月生活费支出的调查数据：375，375，255，315，270，405，360，240，285，300，480，390，495，615，225435，525，450，225，390，300，285，375，425，600，405，

如图7．37所示的流向图，试调整一次使之成为最优流向图。

某运输公司接受了一项货运业务，如表7．6所示，收发货点的位置如图7．33所示，求车辆最优调度方案。

已知效益矩阵如下求使效益最大的指派方案．

若用后根遍历法遍历图C-2所示的二叉树，其输出序列为_______。

已知采用顺序存储结构的一棵二叉树，其存储映像为则其前序遍历序列为______。

“请问先生有几位?”用英语最妥当的表述是()。

多发性骨髓瘤(MM)患者易合并感染的原因是

薄型和超薄型防火涂料的耐火极限一般与涂层厚度无关，与之有关的是()。

在同一厂房内同一平面上安装5台相互联系的单体设备，应用(　　)确定设备的位置。

(2016年)企业拥有的一项经济资源，即使没有发生实际成本或发生的实际成本很小，但如果公允价值能够可靠计量，也应认为符合资产能够可靠计量的确认条件。()

如图，在底面为菱形的四棱锥P—ABCD中，∠ABC=60°，PA=AD=a，PB=PD=，点E在PD上，且PE：ED=2：1．[img][/img]求二面角E—AC—D的大小．

Butletnoonethinkthatpleasureisimmoral.Pleasureinitselfisagreatgood,allpleasure,butitsconsequencesmaybesuc

INTHEGROUNDSOFAREGENCYMANSIONLuxurySelf-cateringHolidayCottagesintheheartoftheDevonshirecountryside.In

下列关于奔腾处理器体系结构的描述中，正确的是()。

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

数据结构

理工类

数据由_______拆成若干个分组送给通信子网，由通信子网将分组传送到数据接收方。

在以特定模式01111110对信息位中的任何连续出现的5个“1”，发送方自动在其后插入一个“0”，而接收方则做该过程的逆操作，以此恢复原始信息实现数据的透明传输的帧同步方法称为()

用BSC规程传输一批汉字，若已知采用不带报头的分块传输，而且最大报文块长为129字节，共传输了5帧，其中最后一块报文长为101字节。问每个报文最多能传多少汉字?这批数据报共有多少汉字?

金融期权按其权利性质划分，可以分为________、__________。

下面是60个大学生一个月生活费支出的调查数据：375，375，255，315，270，405，360，240，285，300，480，390，495，615，225435，525，450，225，390，300，285，375，425，600，405，

如图7．37所示的流向图，试调整一次使之成为最优流向图。

某运输公司接受了一项货运业务，如表7．6所示，收发货点的位置如图7．33所示，求车辆最优调度方案。

已知效益矩阵如下求使效益最大的指派方案．

若用后根遍历法遍历图C-2所示的二叉树，其输出序列为_______。

已知采用顺序存储结构的一棵二叉树，其存储映像为则其前序遍历序列为______。

“请问先生有几位?”用英语最妥当的表述是()。

多发性骨髓瘤(MM)患者易合并感染的原因是

薄型和超薄型防火涂料的耐火极限一般与涂层厚度无关，与之有关的是()。

在同一厂房内同一平面上安装5台相互联系的单体设备，应用( )确定设备的位置。

(2016年)企业拥有的一项经济资源，即使没有发生实际成本或发生的实际成本很小，但如果公允价值能够可靠计量，也应认为符合资产能够可靠计量的确认条件。()

如图，在底面为菱形的四棱锥P—ABCD中，∠ABC=60°，PA=AD=a，PB=PD=，点E在PD上，且PE：ED=2：1．[img][/img]求二面角E—AC—D的大小．

Butletnoonethinkthatpleasureisimmoral.Pleasureinitselfisagreatgood,allpleasure,butitsconsequencesmaybesuc

INTHEGROUNDSOFAREGENCYMANSIONLuxurySelf-cateringHolidayCottagesintheheartoftheDevonshirecountryside.In

下列关于奔腾处理器体系结构的描述中，正确的是()。

金融期权按其权利性质划分，可以分为、__。

在同一厂房内同一平面上安装5台相互联系的单体设备，应用(　　)确定设备的位置。