首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在查找算法中,可用平均查找长度(记为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
76
问题
在查找算法中,可用平均查找长度(记为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
软件设计师上午基础知识考试
软考中级
相关试题推荐
设有下面4条路由:196.34.129.0/24、196.34.130.0/24、196.34.132.0/24和196.34.133.0/24,如果进行路由汇聚,能覆盖这4条路由的地址是______。
如果子网172.6.32.0/20被划分为子网172.6.32.0/26,则下面的结论中正确的是____________。
某单位IP地址需求数如下表所示,给定地址192.168.1.0/24,按照可变长子网掩码的设计思想,部门3的子网掩码为__________。
利用三重DES进行加密,以下说法正确的是__________。(2013年上半年试题)
王某是一名软件设计师,按公司规定编写软件文档,并上交文件存档,这些软件文档属于职务作品,且__________。(2013年上半年试题)
总线复用方式可以______。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的值表示完成活动所需要的时间,则关键路径长度为__________。(2011年下半年试题)
李工是某软件公司的软件设计师,每当软件开发完成均按公司规定申请软件著作权,该软件的著作权()。
阅读以下说明和C语言函数,将应填入(n)处的字句写在答题纸的对应栏内。【说明】一棵非空二叉树中“最左下”结点定义为:若树根的左子树为空,则树根为“最左下”结点;否则,从树根的左子树根出发,沿结点的左孩子分支向下查找,直到某个结点不存在左孩
面向对象方法可用公式:面向对象方法;对象(11)表示。
随机试题
Pickouttheappropriateexpressionsfromtheeightchoicesbelowandcompletethefollowingdialogsbyblackeningthecorrespon
A.血浆因子Ⅻ亚基抗原测定B.凝块稳定性试验C.定性试验D.定量试验E.确证试验血浆因子ⅩⅢ亚基抗原测定是
墨旱莲的功效是()茜草的功效是()
证券公司向信用交易投资者收取的佣金、融资融券利息及其他相关费用,由证券公司通过()扣收。
某大厦筹建处以大厦的名义与某旅行社签订了客房租赁合同,约定从开业时起出租20套客房给该旅行社,此合同因()而无效。
如果一个人的人格和他扮演的角色不一致,这属于()上的问题。
虽然翻拍要比重新创作或“另起灶炉”显得容易些.但也不能因为翻拍就忽略了剧本的质量,胡编乱造更是行不通。创作是第一要务,是翻拍成败的基础,翻拍要是失败了,失掉的不仅是观众,还会带来对原有成功形象的瓦解和品牌贬值。这段文字意在强调翻拍:
A、 B、 C、 D、 CSTR(<数值表达式>[,<长度<[,<小数位数>]]),将<数值表达式>的值转换成字符串,转换时根据需要自动进行四舍五入。返回字符串的理想长度L应该是<数值表达式>值的整数部分位数
Wheatpricesweregenerallylowintheautumn,sofarmerscouldnotwaitformarketstoimprove.
A、Classicalgroup.B、Popgroup.C、Jazzgroup.D、Rockgroup.B根据女士的回答“Theyareapopgroup”可知,愚人花园是个流行乐队组合,故选B。
最新回复
(
0
)