首页 > 试题广场 >

假设顺序表中包含5个关键字{a，b，c，d，e}，它们的查找

[单选题]
假设顺序表中包含5个关键字{a，b，c，d，e}，它们的查找概率分别为{0.25，0.3，0.2，0.1，0.15}，为了使查找成功时的平均查找长度达到最小，则顺序表中数据元素的出现顺序是（     ） 
  • e，d，c，b，a
  • b，a，c，e，d
  • b，a，d，c，e
  • a，d，e，c，b
查看答案及解析
添加回答
推荐
白驹之过隙头像 白驹之过隙
选B。
根据题干的“使查找成功时的平均查找长度达到最小”，所以将经常需要查找（查找概率大）的数据放在顺序表中较前的位置。
所以b的查找概率0.3最大，应放在顺序表最前位置。d的查找概率为0.1最小，放在最后位置。
编辑于 2019-09-11 14:15:47 回复(0)
toomanyconversation头像 toomanyconversation
b
发表于 2018-09-12 07:56:25 回复(0)
Light_D头像 Light_D
答案：B
顺序表查询长度与顺序表遍历长度有关，概率越大，其在顺序表中所占长度越长，概率越大 应放在前面
发表于 2019-09-11 11:42:46 回复(0)
August-us2020头像 August-us2020
类似于哈夫曼编码的思想，让概率大的查找次数少就可以保证总的查找次数最小，所以对序列依照查找概率排序，概率最大的找的次数最小，所以答案选B
发表于 2019-09-10 21:40:17 回复(0)
谁在偷笑呢头像 谁在偷笑呢
<p>d的出现概率最小，出现的可能性最小，放到最后稀释平均长度。</p>
发表于 2020-07-14 00:43:52 回复(0)
jingjinghao头像 jingjinghao
B选项正确    顺序查找时，元素出现概率乘以深度/序数的求和是查找操作的损失函数，这是最小化解。
发表于 2019-09-11 07:05:36 回复(0)
汤米弟弟头像 汤米弟弟
个人理解，如有误，请纠正！

要使得平均查找长度最小，要按照查找概率从高到低进行查找，所以这边就是答案b。

在顺序为b,a,c,e,d时，平均查找长度为：0.3*1+0.25*2+0.2*3+0.15*4+0.1*5，也就是说要查找到b只要查找一次，查找a要两次，...

平均查找长度=sum(P_i * i),其中P_i是指第i位元素的查找概率。
发表于 2019-03-06 15:31:48 回复(0)
提交观点

问题信息

查找
上传者：逍遥20180616142306
难度：
7条回答 11136浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号