具有12个关键字的有序表中,对每个关键字的查找概率相同,折半查找查找成功和查找失败的平均查找长度依次为( )。

admin2019-07-18  31

问题 具有12个关键字的有序表中,对每个关键字的查找概率相同,折半查找查找成功和查找失败的平均查找长度依次为(    )。

选项 A、37/12,49/13
B、35/12,39/13
C、37/13,49/13
D、37/12,49/12

答案A

解析 考查折半查找的平均查找长度。假设有序表中元素为A[0…11],不难画出它所对应的折半查找判定树如下图所示,圆圈是查找成功结点,方形是虚构的查找失败结点。从而可以求出查找成功的ASL=(1+2×2+3×4+4×5)/12=37/12,查找失败的ASL=(3×3+4×10)/13。
转载请注明原文地址:https://jikaoti.com/ti/OaGjFFFM
0

最新回复(0)