首页 > 试题广场 > 回答下面问题
[问答题]

设包含 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。
【答案二】

采用二叉链表存储结构,构造二叉排序树,元素存储方式见下图。


采用二叉排序树的查找方法。
查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。

发表于 2016-11-19 16:58:48 回复(4)