首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为(52)。
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为(52)。
admin
2013-05-11
67
问题
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为(52)。
选项
A、21
B、23
C、41
D、62
答案
B
解析
分块查找又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。二分查找表由分块有序的线性表和索引表组成。表R[1,…,n]均分为b块,前b-1块中结点个数为s=[n/b],第b块的结点数允许小于等于s;每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即表是分块有序的。抽取各块中的最大关键字及其起始位置构成一个索引表ID[1,…,b],即ID
(1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。分块查找的基本思想是:索引表是有序表,可采用二分查找或顺序查找,以确定待查的结点在哪一块。由于块内无序,只能用顺序查找。分块查找是两次查找过程,整个查找过程的平均查找长度是两次查找的平均查找长度之和。如果以二分查找来确定块,则分块查找成功时的平均查找长度为ASL1=log
2
(b+1)-1+(s+1)/2≈log
2
(n/s+1)+s/2;如果以顺序查找确定块,分块查找成功时的平均查找长度为ASL2=(b+1)/2+(s+1)/2=(s
2
+2s+n)/(2s)。在本题中,n=123,b=3,s=41,因此平均查找长度为(41*41+2*41+123)/(2*41)=23。
转载请注明原文地址:https://kaotiyun.com/show/d2RZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
可以用于表示地址块220.17.0.0~220.17.7.0的网络地址是(1),这个地址块中可以分配(2)个主机地址。(2012年下半年试题)(1)
子网过滤防火墙安装方法是把防火墙安装在一个由(1)控制边界的公共子网中,子网中有一台执行(2)的主机,对于多数应用入口,需要一个附加的(3)机制来控制、筛选入口与网络之间的信息流。这样可以有效地把该机制和(4)结合起来,达到多层屏障保护的目的。
子网过滤防火墙安装方法是把防火墙安装在一个由(1)控制边界的公共子网中,子网中有一台执行(2)的主机,对于多数应用入口,需要一个附加的(3)机制来控制、筛选入口与网络之间的信息流。这样可以有效地把该机制和(4)结合起来,达到多层屏障保护的目的。
子网过滤防火墙安装方法是把防火墙安装在一个由(1)控制边界的公共子网中,子网中有一台执行(2)的主机,对于多数应用入口,需要一个附加的(3)机制来控制、筛选入口与网络之间的信息流。这样可以有效地把该机制和(4)结合起来,达到多层屏障保护的目的。
Kerberos要求用户使用(1)作为自己的标识,而客户端与KDC服务器之间的交互则使用(2)。当用户需要和其他用户通信时,需要从服务器端获得(3),然后再用其向KDC服务器申请与需要通信的一方交互的会话密钥。接收到这个密钥后,就可以建立与对方用户
在SNMP管理模型中,关于管理信息库MIB的说法,正确的是(1)。SNMP实现管理功能的方式是(2)。SNMP网络管理模型中关于管理代理与委托代理的说法正确的是(3)。SNMP将一个值存储到指明变量中去使用(4)命令,而有关get操作命令的目的是(5)。
以太网中,当数据传输提高时,帧的发送时间要按比例缩短,这样有可能会影响冲突的检测。为了能有效地检测冲突,可以(1)或者(2)。快速以太网仍然遵循CSMA/CD,它采取(3)而将最大电缆长度减少到100m的方式,使以太网的数据传输速率提高到100Mb/s。
随机试题
某次小学五年级的英语期中测验,全班同学的成绩均不理想,很多学生只答了50多分,班主任王老师对这次考试的成绩很不满意,命令全班学生回去以后将做错的试题重新抄下来,每题抄写十遍,再做十遍。你怎样看待这一现象?请运用记忆的有关规律加以分析。
某临床医师善治急、慢性肝炎,常用茵胆平肝胶囊,用后每能收效。该制剂功能清热、利湿、退黄,可用于肝胆湿热所致的胁痛、口苦、尿黄、身目发黄以及急、慢性肝炎见上述证候者。处方组成有茵陈、黄芩、栀子、当归、龙胆、炒白芍、甘草等。处方中含有裂环环烯醚萜苷类有效
甲向乙借款20万元,合同约定的还款期限为2年,但只约定需要支付利息,没有约定利率。合同到期后,甲无力还款,拍卖自己的财产还款。知情的丙以远低于市场价的价格从甲处购买了一批货物,其问,甲的祖父去世,留给甲一笔25万元的遗产,甲明确表示放弃该遗产的继承。后经核
症见心烦不寐,躁扰不宁,口舌生疮,小便短赤,舌红苔薄黄,脉数。治疗方剂宜选用()
构造简单,落距短,对设备和桩头不易打坏,打桩速度及冲击力较落锤大,效率高的桩锤是()。
保险事故发生后,投保人/被保险人不积极施救,延误最好的抢救时机,而使损失增加的可能性是( )。
人类智力可分为流体智力和晶体智力两类。流体智力是一个人生来就能进行智力活动的能力,即学习和解决问题的能力,它依赖于先天的禀赋,随神经系统的成熟而提高,不受教育与文化的影响。而晶体智力是指以学得的经验为基础的认知能力,受后天的经验影响较大。根据上述定义,下列
新民主主义国家的政体是民主集中制的人民代表大会制度,实行这一政体的决定性因素是
微分方程(y+x3)dx一2xdy=0满足y|x=1=的特解为_________。
Thestormsweepingoverthisareanowissuretocause()ofvegetablesinthecomingdays.
最新回复
(
0
)