数据结构
2013-42
设包含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）顺序存储：元素按查找概率降序排列（如“do”、“while”、“for”、“repeat”），采用顺序查找方法，查找成功时的平均查找长度为2.1。
（2）链式存储：构造二叉排序树（如以“for”为根，“do”为左孩子，“while”为右孩子，“repeat”为“while”的左孩子），采用二叉排序树的查找方法，查找成功时的平均查找长度为2.0。