设包含4个数据元素的集合S={“do”,“for”,“repeat”,“while”},各元素的查找概率依次为:p1=0.35,p2=0.15,p3=0.15,p4=0.35。将S保存在一个长度为4的顺序表中,采用折半查找法,查找成功时的平均查找长度为2.

admin2014-01-15  85

问题 设包含4个数据元素的集合S={“do”,“for”,“repeat”,“while”},各元素的查找概率依次为:p1=0.35,p2=0.15,p3=0.15,p4=0.35。将S保存在一个长度为4的顺序表中,采用折半查找法,查找成功时的平均查找长度为2.2。请回答:
若采用顺序存储结构保存S,且要求平均查找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?

选项

答案采用顺序存储结构,数据元素按其查找概率降序排列。采用顺序查找方法。查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。

解析
转载请注明原文地址:https://kaotiyun.com/show/Zqxi777K
0

最新回复(0)