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

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

admin2015-12-30  21
问题 设包含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/HzRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)