首页 > 试题广场 >

设包含4个数据元素的集合S={"do",‘‘for","re

[问答题]

设包含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,且要求平均査找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?



第一问可以采取折半查找的方法吗,采用for,do,while,repeat排列
发表于 2021-11-30 19:48:02 回复(0)
为什么第一题不能用散列呢?
发表于 2022-11-21 17:10:44 回复(0)
(1)采用顺序存储结构,数据元素按其查找概率降序排列。
采用顺序查找方法。
查找成功时的平均查找长度=0.35x1+0.35x2+0.15x3+0.15x4=2.1。
(2)
答案一:
采用链式存储结构,数据元素按其查找概率降序排列,构成单链表。
采用顺序查找方法。
查找成功时的平均查找长度=0.35x1+0.35x2+0.15x3+0.15x4=2.1。
答案二:
采用二叉链表存储结构,构造二叉排序树,
元素存储方式
根结点for,左子树do,右子树根结点while(while左子树repeat) (a)
根结点while,左子树根结点do(do右子树for),右子树while       (b)
采用二叉排序树的查找方法。
查找成功时的平均查找长度=0.15x1+0.35x2+0.35x2+0.15x3=2.0。
发表于 2021-10-03 21:33:35 回复(1)