42.（10分）设包含4个数据元素的集合S={"do"，"for"，"repeat"，" while"}，各元素的查找概率依次为∶pl=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.15×3+0.15×4=2.1。（2分） 【答案二】 采用二叉链表存储结构，构造二叉排序树，元素存储方式见下图。（2分） 采用二叉排序树的查找方法。（1分） 查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。（2分） 【（1）、（2）的评分说明】 ①若考生以实际元素表示"降序排列"，同样给分。 ② 若考生正确求出与其查找方法对应的查找成功时的平均查找长度，给 2 分;若计算过程正确，但结果错误，给1分。 ③若考生给出其他更高效的查找方法且正确，可参照评分标准给分。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（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.15×3+0.15×4=2.1。（2分） 【答案二】 采用二叉链表存储结构，构造二叉排序树，元素存储方式见下图。（2分） 采用二叉排序树的查找方法。（1分） 查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。（2分） 【（1）、（2）的评分说明】 ①若考生以实际元素表示"降序排列"，同样给分。 ② 若考生正确求出与其查找方法对应的查找成功时的平均查找长度，给 2 分;若计算过程正确，但结果错误，给1分。 ③若考生给出其他更高效的查找方法且正确，可参照评分标准给分。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！