首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在查找算法中,可用平均查找长度(记为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
79
问题
在查找算法中,可用平均查找长度(记为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
软件设计师上午基础知识考试
软考中级
相关试题推荐
《计算机软件产品开发文件编制指南》(GB 8567-88)是(22)标准。
汇聚层交换机应该实现多种功能,下面选项中,不属于汇聚层功能的是()。
网络200.105.140.0/20中可分配的主机地址数是__________。(2010年上半年试题)
假设系统中进程的三态模型如下图所示,图中的a、B和C的状态分别为______。
以下关于程序设计语言的叙述中,错误的是_____________。
下面4种编码方式中属于差分曼彻斯特编码的是(15)。
阅读下列说明和C++代码,填写程序中的空(1)~(6),将解答写入答题纸的对应栏内。【说明】以下C++代码实现一个简单绘图工具,绘制不同形状以及不同颜色的图形。部分类及其关系如图7所示。【C++代码】#includ
电视系统采用的颜色空间中,其亮度信号和色度信号是相分离的。下列颜色空间中,(58)颜色空间不属于电视系统的颜色空间。
对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行(61)遍历可以得到一个
采用连续播放静止图像的方法产生运动的效果,即使用计算机产生图形、图像运动的技术称为(37)。(38)采用实时绘制的方式显示一幅矢量图,当图形放大或缩小时,都保持光滑的线条,不会影响质量,也不会改变文件的容量。
随机试题
女性,18岁,体检发现心脏杂音来诊。平时不能耐受较大的体力活动,无双下肢水肿及夜间呼吸困难史,易感冒。查体:血压:130/80mmHg,心率90次/分。S1↓,S2稍↑。A:SM3/6反流样向左腋下传导,L4、5可闻收缩期Click音,下蹲位站立后Cli
红细胞上无H抗原称为
下列方法中,对Rh血型系统较为敏感的是
制备肠溶胶囊时,使用甲醛处理的目的是
下列关于价值工程的含义描述不正确的是( )。
科学管理的标志之一是()。
在下列账目中,出纳人员可以登记的是()。
王某现年17岁,高二学生,平时创新能力极强,其研究创造的一个小发明获得专利,并且经济价值较高。专利权的申请、使用和由此所获取的收入的处理一概由王某的父亲予以安排,王某的父亲从事的下列各种行为中,违背了监护责任的是()。
A、 B、 C、 D、 AA项可由左侧图形折成;B项,直线应与阴影相接,错误;C项,左侧面中三角形应含阴影,错误;D项,右侧面中阴影三角形应在上部,错误。
2017年4月1日,中共中央、国务院决定在此设立的国家级新区。设立雄安新区()
最新回复
(
0
)