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

admin2015-12-30 27

问题设包含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。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/TzRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

毛泽东从事了大量理论研究工作，系统阐述了新民主主义的理论，下列选项中，不属于这一范围的是()

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

试结合新民主主义革命不同历史时期的历史实际，阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。

1979年3月，邓小平在中央理论工作务虚会上首次明确提出必须坚持()。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最多需要比较的次数是()。

采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是____。

患者，女性，27岁。1个月前右膝被铁锹把撞伤，此后即感局部疼痛，来院检查，右胫骨上端轻微肿胀并且压痛，X线片显示右股骨下端外呈膨胀性、偏心性肥皂泡样改变。为进一步确诊应选择的检查为

不属于泌尿系造影检查的是

夏季，某5周龄雏鹅群出现精神委顿，排灰白色或暗红色带黏液的稀粪。剖检见小肠肿胀，黏膜出血、坏死，形成伪膜和肠芯。刮取肠黏膜镜检，见有大量圆形或椭圆形裂殖体。治疗该病应选择

A．罹患率B．相对危险度C．有效率、副反应发生率D．抗体阳转率、效果指数E．患病率调查某市甲型肝炎爆发，分析时可选用指标

证券公司委托其他证券公司代为买卖证券的，属于操纵市场行为。()

通常而言，下列可以导致股票价格上涨的经济状况变动是()。

下列关于可转换债券的说法中，不正确的是()。

新员工培训分为()。

下图所示的大型商城，以汇集国际品牌商品、价格优惠为经营模式。某地理小组学生实地考察了该商城与地理环境的关系。结合图文材料，回答第以下题。同学们经考察认识到，最利于该商城发展的区位条件是()。

篮球队教练规定，如果一号队员上场，而且三号队员没有上场，那么，五号与七号队员中至少要有一人上场。如果教练的规定被贯彻执行了。一号队员没有上场的充分条件为：