首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为: 此处Pi为表中第i个记录被查找的概率,Ci为查找第i个记录时同关键字比较的次数,n为表中记录数。 以下叙述中均假定每一个记录被查找的概率相等,即Pi=1/n(i=1,2,…
在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为: 此处Pi为表中第i个记录被查找的概率,Ci为查找第i个记录时同关键字比较的次数,n为表中记录数。 以下叙述中均假定每一个记录被查找的概率相等,即Pi=1/n(i=1,2,…
admin
2019-06-12
53
问题
在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为:
此处P
i
为表中第i个记录被查找的概率,C
i
为查找第i个记录时同关键字比较的次数,n为表中记录数。
以下叙述中均假定每一个记录被查找的概率相等,即P
i
=1/n(i=1,2,…,n)。当表中的记录连续有序存储在一个一维数组中时,采用顺序查找与折半查找方法查找的值分别是( )。
选项
A、O(n),O(n)
B、D(n),O(1bn)
C、D(n1bn),O(n)
D、O(1bn),O(1bn)
答案
B
解析
顺序查找的基本思想是:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键字和给定值k相比较。若当前扫描到的结点关键字与k相等,则查找成功;若扫描结束后,仍未找到关键字等于k的结点,则查找失败。顺序查找方法既适用于线性表的顺序存储结构,也适用于线性表的链式存储结构。
成功的顺序查找的平均查找长度如下:
在等概率情况下,p
i
=1/n(1≤i≤n),故成功的平均查找长度为(n+…+2+1)/n=(n+1)/2,即查找成功时的平均比较次数约为表长的一半。若k值不在表中,则需进行n+1次比较之后才能确定查找失败。查找时间复杂度为O(n)。
若事先知道表中各结点的查找概率不相等,以及它们的分布情况,则应将表中结点按查找概率由小到大的顺序存放,以便提高顺序查找的效率。
顺序查找的优点是算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,也无论结点之间是否按关键字有序,它都同样适用。其缺点是查找效率低,因此,当n较大时不宜采用顺序查找。
二分法查找又称折半查找,是一种效率较高的查找方法。二分法查找要求线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。
二分法查找的基本思想是(设R[low,…,high]是当前的查找区间):
(1)确定该区间的中点位置:mid=[(10w+high)/2]。
(2)将待查的k值与R[mid].key比较,若相等,则查找成功并返回此位置,否则需确定新的查找区间,继续二分查找,具体方法如下:
若R[mid].key>k,则由表的有序性可知R[mid,…,n].key均大于k,因此若表中存在关键字等于k的结点,则该结点必定是在位置mid左边的子表R[low,…,mid一1]中。因此,新的查找区间是左子表R[low,…,high],其中high=mid一1。
若R[mid].key
若R[mid].key=k,则查找成功,算法结束。
(3)下一次查找针对新的查找区间进行,重复步骤(1)和(2)。
(4)在查找过程中,low逐步增加,而high逐步减少。如果high
因此,从初始的查找区间R[1,…,n]开始,每经过一次与当前查找区间中点位置上结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。重复这一过程,直至找到关键字为k的结点,或直至当前的查找区间为空(即查找失败)时为止。查找的时间复杂度为:O(log
2
n)。
转载请注明原文地址:https://kaotiyun.com/show/lORZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
以下关于网络布线子系统的说法中,错误的是(63)________________。
某四级指令流水线分别完成取指、取数、运算、保存结果四步操作。若完成上述操作的时间依次为8ns、9ns、4ns、8ns,则该流水线的操作周期应至少为_____________ns。
设信号的波特率为600Baud,采用幅度一相位复合调制技术,由4种幅度和 8种相位组成16种码元,则信道的数据速率为(14)。
假设网络的生产管理系统采用B/S工作方式,经常上网的用户数为100个,每个用户每分钟平均产生11个事务,平均事务量大小为0.06MB,则这个系统需要的信息传输速率为(34)。
在OSI参考模型中,上层协议实体与下层协议实体之间的逻辑接口叫做服务访问点(SAP)。在Internet中,网络层的服务访问点是(21)。
李某在《电脑与编程》杂志上看到张某发表的一组程序,颇为欣赏,就复印了100份作为程序设计辅导教材发给学生。李某又将这组程序逐段加以评析,写成评论文章后投到《电脑编程技巧》杂志上发表。李某的行为__________。(2008年下半年试题)
在某并发系统中,有一个发送进程A、一个接收进程B、一个环形缓冲区BUFFER、信号量S1和S2。发送进程不断地产生消息并写入缓冲区BUFFER,接收进程不断地从缓冲区BUFFER取消息。假设发送进程和接收进程可以并发地执行,那么,当缓冲区的容量为N时,如何
阅读下列说明、图和C代码。[说明5-1]B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树:①树中每个结点最多有m棵子树;②若根结点不是叶子结点,则它至少有两棵子树;⑧除根之外的所有非叶子结点至少有
阅读下列函数说明和c代码,将应填入(n)处的字句写在对应栏内。【说明】所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。应用贪婪法求解该问题。程
位图与矢量图相比,位图()。
随机试题
某地区有部分儿童出现智力低下,生长发育迟缓,应重点考虑
不含有"培土生金"配伍原理的方剂是
生产单位提前进厂参加施工、设备安装、调试等人员的工资、工资性补贴、劳动保护费等应从()中支付。
以股东财富最大化作为财务管理目标的首要任务是协调相关者的利益关系,下列不属于股东和经营者利益冲突解决方式的是()。
行政复议期间,导致行政复议终止的情形有()。
下列各项中,属于法律行为的有()。
教师的医疗同当地国家公务员享受同等的待遇;()对教师进行身体健康检查,并因地制宜安排教师进行休养。
下列选项中,与“刘伯承和徐向前是元帅”的判断类型不同的一项是()。
Rosalikedmakingupstories.Shewasso【C1】______thatherclassmatesbelievedherfromtimetotime.Infact,thewholeclassb
不属于常用的局域网介质访问控制方法的是______。
最新回复
(
0
)