【题目】
42.(10分)设包含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)采用顺序存储结构，数据元素按其查找概率降序排列。(2分)
采用顺序查找方法。(1分)
查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。(2分)
(2)【答案一】
采用链式存储结构，数据元素按其查找概率降序排列，构成单链表。(2分)
采用顺序查找方法。(1分)
查找成功时的平均查找长度=0.35×1+0.35×2+0.15x3+0.15×4=2.1。(2分)
【答案二】
采用二叉链表存储结构，构造二叉排序树，元素存储方式见下图。(2分)
采用二叉排序树的查找方法。(1分)
查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。(2分)