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

admin2010-04-24 74

问题假设有一个长度为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)

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

数据结构

理工类

数据链路层中主要用于面向连接服务的功能的是()

不属于TCP／IP协议层次的互联层能够提供的服务是()

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

下列不属于HDLC常用的操作方式的是()

长1km，传输速率10Mbit／s，包含50个站点的令牌环，每个站引入1位延迟，信号传播速度为200m／μs，令牌长8位，数据帧长度为256位(包含32位开销)，确认包含在数据帧中捎带，问该环不包括开销的有效数据速率为多少?

金融互换实现的条件有()

简述我国货币层次的划分。

下面是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，

如图所示交通图的物资调运问题，试作出第一流向图．

宁夏回族自治区得黄河水灌溉而形成了悠久的黄河文明。早在5万年前，宁夏回族自治区就已有了人类生息的痕迹。()

RL串联在u=220sin(100π+30°)V的电源上，已知L=51mH，若要使电感两端的电压UL=176V，求R的值，并写出电流的瞬时值表达式。

A．球形心B．靴形心C．梨形心D．虎斑心二尖瓣关闭不全

A、生蒲黄B、鸡屎藤C、西红花D、罂粟壳E、血余炭为防灰尘污染，不宜装于一般药斗内的是（）

()是房地产经纪人向委托人提供房地产的交易信息,包括交易的数量、交易行情、交易方式等使委托人能够选择符合自己交易目的的房地产。

采用加押电传进行付款方式是()。

问题(1)的正确账务调整分录包括(　　)。问题(4)的正确账务调整分录包括(　　)。

Arecentanti-monopolycampaignlaunchedbytheChinesegovernmenthasraiseconcernsaboutwhetherprotectionismwillriseinC

Tomemorizenamesofpeopleisnotonlyanimportantsocialskillbutalsoahighlyrecommended_____.

Rita:Susan,youcouldbecomeamodel.Susan:Don’tmakemelaugh!Question:WhatdoesSusanmean?

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

数据结构

理工类

数据链路层中主要用于面向连接服务的功能的是()

不属于TCP／IP协议层次的互联层能够提供的服务是()

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

下列不属于HDLC常用的操作方式的是()

长1km，传输速率10Mbit／s，包含50个站点的令牌环，每个站引入1位延迟，信号传播速度为200m／μs，令牌长8位，数据帧长度为256位(包含32位开销)，确认包含在数据帧中捎带，问该环不包括开销的有效数据速率为多少?

金融互换实现的条件有()

简述我国货币层次的划分。

下面是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，

如图所示交通图的物资调运问题，试作出第一流向图．

宁夏回族自治区得黄河水灌溉而形成了悠久的黄河文明。早在5万年前，宁夏回族自治区就已有了人类生息的痕迹。()

RL串联在u=220sin(100π+30°)V的电源上，已知L=51mH，若要使电感两端的电压UL=176V，求R的值，并写出电流的瞬时值表达式。

A．球形心B．靴形心C．梨形心D．虎斑心二尖瓣关闭不全

A、生蒲黄B、鸡屎藤C、西红花D、罂粟壳E、血余炭为防灰尘污染，不宜装于一般药斗内的是（）

()是房地产经纪人向委托人提供房地产的交易信息,包括交易的数量、交易行情、交易方式等使委托人能够选择符合自己交易目的的房地产。

采用加押电传进行付款方式是()。

问题(1)的正确账务调整分录包括( )。问题(4)的正确账务调整分录包括( )。

Arecentanti-monopolycampaignlaunchedbytheChinesegovernmenthasraiseconcernsaboutwhetherprotectionismwillriseinC

Tomemorizenamesofpeopleisnotonlyanimportantsocialskillbutalsoahighlyrecommended_____.

Rita:Susan,youcouldbecomeamodel.Susan:Don’tmakemelaugh!Question:WhatdoesSusanmean?

问题(1)的正确账务调整分录包括(　　)。问题(4)的正确账务调整分录包括(　　)。