首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为: 此处Pi为表中第i个记录被查找的概率,Ci为查找第i个记录时同关键字比较的次数,n为表中记录数。 以下叙述中均假定每一个记录被查找的概率相等,即Pi=1/n
在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为: 此处Pi为表中第i个记录被查找的概率,Ci为查找第i个记录时同关键字比较的次数,n为表中记录数。 以下叙述中均假定每一个记录被查找的概率相等,即Pi=1/n
admin
2019-06-12
42
问题
在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为:
此处P
i
为表中第i个记录被查找的概率,C
i
为查找第i个记录时同关键字比较的次数,n为表中记录数。
以下叙述中均假定每一个记录被查找的概率相等,即P
i
=1/n(i=1,2,…,n)。当表中的记录连续有序存储在一个一维数组中时,采用顺序查找与折半查找方法查找的ASL值分别是(11)。
选项
A、O(n),O(n)
B、O(n),O(1bn)
C、O(n1bn),O(n)
D、O(1bn),O(1bn)
答案
B
解析
顺序查找的基本思想是:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键字和给定值k相比较。若当前扫描到的结点关键字与k相等,则查找成功;若扫描结束后,仍未找到关键字等于k的结点,则查找失败。顺序查找方法既适用于线性表的顺序存储结构,也适用于线性表的链式存储结构。
成功的顺序查找的平均查找长度如下:
ASL=
=np
1
+(n-1)p
2
+…+2p
n-1
+p
n
在等概率情况下,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=[(lowd+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<k,则要查找的k必在mid的右子表R[mid+1,…,high]中,即新的查找区间是右子表R[low,…,high],其中low=mid+1。
若R[mid].key=k,则查找成功,算法结束。
(3)下一次查找针对新的查找区间进行,重复步骤(1)和(2)。
(4)在查找过程中,low逐步增加,而high逐步减少。如果high<low,则查找失败,算法结束。
因此,从初始的查找区间R[1,…,n]开始,每经过一次与当前查找区间中点位置上结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。重复这一过程,直至找到关键字为k的结点,或直至当前的查找区间为空(即查找失败)时为止。查找的时间复杂度为:O(1ogEn)。
转载请注明原文地址:https://kaotiyun.com/show/spRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
某校园网的地址是202.115.192.0/19,要把该网络分成30个子网,则子网掩码应该是()。
在Linux中,可以使用命令()针对文件newfiles.txt为所有用户添加执行权限。
路由器Console端口默认的数据速率为()。
对高级语言源程序进行编译或解释的过程可以分为多个阶段,解释方式不包含(6)阶段。
(66)针对TCP连接进行攻击。
面向对象开发方法的基本思想是尽可能按照人类认识客观世界的方法来分析和解决问题,()方法不属于面向对象方法。
把路由器当前配置文件存储到NVRAM中的命令是_________。
下面是家庭用户安装ADSL宽带网络时的拓扑结构图,图中左下角的X是(1)设备,为了建立虚拟拨号线路,在用户终端上应安装(2)协议。(2)
在Linux中,某文件的访问权限信息为“-rwxr-r-”,以下对该文件的说明中,正确的是__________。(2011年下半年试题)
请填充图4-1中的空缺(1)、(2)和(3)处。对于本题的作业处理问题,用图4-1的贪心算法策略,能否求得最高收益?(6)。用贪心算法求解任意给定问题时,是否一定能得到最优解?(7)。
随机试题
在工程验收过程中,发现个别检验批试块强度不满足要求,但是请具有资质的法定检测单位检测鉴定后,鉴定结果能够达到设计要求。这种情况下应()。
马克思主义认为,社会生活在本质上是()
符合浅Ⅱ度烧伤评估标准的是()
吴茱萸汤《伤寒论》原方生姜的用量是
对于发行分期付息、到期一次还本债券的企业来说,采用实际利率法摊销债券折溢价时(不考虑相关交易费用),下列表述正确的是()。
道德评价是我们依据一定的道德原则和规范,对自己和他人的言行所进行的()。
环境经济学要解决的问题如下:人们做出经济上的决定是不会爽快地把环境因素,例如清洁的空气、濒临灭绝的生物的生存,与其他的成本和收益作比较。就像环境经济学家认识到的那样,解决这个问题需要赋予环境一定的金钱价值。但是环境的金钱价值源自人们未做出经济上的决定而对成
有以下程序:#include<stdio.h>#include<string.h>typedefstruct{charname[9];charsex;floatscore[2];}STU;voidf(S
A、Becausenineisanoddnumber.B、Becausetheelevatorgotstuck.C、Becausetherearetoomanypeopleintheelevator.D、Becaus
Beforetheportrayalofthehumanbodycanbecritiqued,youmustunderstandtheartist’sculture.Asman【S1】______overcenturi
最新回复
(
0
)