有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是( )。

admin2013-12-31 37

问题有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是( )。

选项 A、13850
B、13119
C、14580
D、16041

答案A

解析长度为12的折半查找判定树如下图3—4所示，判定树中有12个内结点。

对于长度为12的有序表，折半查找成功时的平均查找长度为：

=(1×2⁰+2×2¹+…+k×2k^k-1)／n
=(1×1+2×2+3×4+4×5)／12=37／1 2

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

计算机408

相关试题推荐

随机试题

最新回复(0)