2. 考研
  3. 设包含4个数据元素的集合S={“do”，“for”，“repeat”，“while”}，各元素的查找概率依次为：p1=0．35，p2=0．15，p3=0．15，p4=0．35。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2．

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

admin2014-01-15  28
问题 设包含4个数据元素的集合S={“do”，“for”，“repeat”，“while”}，各元素的查找概率依次为：p1=0．35，p2=0．15，p3=0．15，p4=0．35。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2．2。请回答：
若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?
选项
答案【答案一】采用链式存储结构，数据元素按其查找概率降序排列，构成单链表。采用顺序查找方法。查找成功时的平均查找长度=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。
解析
转载请注明原文地址:https://kaotiyun.com/show/4qxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)