首页 > 试题广场 >

回答下面问题

[问答题]

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

（1）若采用顺序存储结构保存 S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
（2）若采用链式存储结构保存 S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

查看答案及解析

城市里的养猫者

（1）采用顺序存储结构，数据元素按其查找概率降序排列。
采用顺序查找方法。
查找成功时的平均查找长度= 0.35×1+0.35×2+0.15×3+0.15×4=2.1。
（2）【答案一】
采用链式存储结构，数据元素按其查找概率降序排列，构成单链表。
采用顺序查找方法。
查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。
【答案二】