首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为(52)。
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为(52)。
admin
2013-05-11
72
问题
设顺序存储的某线性表共有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)结合起来,达到多层屏障保护的目的。
Kerberos要求用户使用(1)作为自己的标识,而客户端与KDC服务器之间的交互则使用(2)。当用户需要和其他用户通信时,需要从服务器端获得(3),然后再用其向KDC服务器申请与需要通信的一方交互的会话密钥。接收到这个密钥后,就可以建立与对方用户
在SNMP管理模型中,关于管理信息库MIB的说法,正确的是(1)。SNMP实现管理功能的方式是(2)。SNMP网络管理模型中关于管理代理与委托代理的说法正确的是(3)。SNMP将一个值存储到指明变量中去使用(4)命令,而有关get操作命令的目的是(5)。
某报文的长度是1000字节,利用MD5计算出来的报文摘要长度是(1)位,利用SHA计算出来的报文摘要长度是(2)位。(2010年下半年试题)(1)
以太网中,当数据传输提高时,帧的发送时间要按比例缩短,这样有可能会影响冲突的检测。为了能有效地检测冲突,可以(1)或者(2)。快速以太网仍然遵循CSMA/CD,它采取(3)而将最大电缆长度减少到100m的方式,使以太网的数据传输速率提高到100Mb/s。
随机试题
Allofushavereadthrillingstoriesinwhichtheherohadonlyalimitedandspecifiedtimetolive.【C1】______.Butalwayswe
男性,30岁,因寒战高热,右上腹胀痛20天入院。查体:体温39℃,消耗病容,右季肋区叩痛,右肋缘下3cm可触及肝下缘,触痛。化验检查Hb80g/,WBCl5.6×109/L,中性粒细胞92%B超检查:肝右叶液性暗区10cm×8cm。这种严重感染的致病菌最
不良反应相对较小的咪唑类抗真菌药是
A.劣药B.假药C.保健药品D.非处方药E.特殊管理药品药品成分的含量不符合同家药品标准的
患者,女性,因子宫破裂,胎儿死亡,行子宫切除术。术后制订心理调适的护理措施哪项不妥
就专业化建设项目管理公司的服务对象来说,应用最为普遍的是( )的项目管理。
简述一节好课的标准。
最早对无意识现象进行深入研究的是()
注重对孩子的自然教育,让孩子亲身感受大自然的神奇与美妙,可促进孩子释放天性,激发自身潜能;而缺乏这方面教育的孩子容易变得孤独,道德、情感与认知能力的发展都会受到一定的影响。以下哪项与以上陈述方式最为类似?
在窗体上画一个命令按钮,然后编写如下事件过程:PrivateSubCommand1_Click()DoUntilb<0a=InputBox("输入a的值")a=Val(a)b=InputBox("输入b的值")b=Val(b)
最新回复
(
0
)