首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在查找算法中,可用平均查找长度(记为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
51
问题
在查找算法中,可用平均查找长度(记为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
软件设计师上午基础知识考试
软考中级
相关试题推荐
TCP/IP在多个层次引入了安全机制,其中TLS协议位于__________。(2008年下半年试题)
ISP分配给某公司的地址块为199.34.76.64/28,则该公司得到的地址数是__________。(2011年上半年试题)
主机host1和host2进行域名查询的过程如下图所示,下列说法中正确的是__________。(2013年上半年试题)[*]2
决定局域网特性的主要技术要素是网络拓扑、传输介质和__________。
CIDR技术的作用是(50)。
DNS服务器中提供了多种资源记录,其中__________定义了区域的邮件服务器及其优先级。(2012年上半年试题)
利用报文摘要算法生成报文摘要的目的是__________。(2013年上半年试题)
N-ISDN有两种接口:基本速率接口(2B+D)和基群速率接口(30B+D),有关这两种接口的描述中,正确的是__________。(2005年上半年试题)
下图是一个软件项目的活动图,其中顶点表示项目里程碑,联结顶点的边表示包含的活动,则里程碑(1)在关键路径上,活动FG的松弛时间为(2)。(2)
阅读以下说明和C函数,将(1)~(5)空缺处的字句填写完整。[说明]计算机在处理算术表达式时,首先将其转换为后缀表达式。例如,表达式“46+5*120-37)”的后缀表达式形式为“46512037-*+”。计算后缀表达式时,
随机试题
worldcompany
有助于鉴别细菌性感染和病毒性感染的实验检查
商业银行交易账户的项目通常按历史成本定价。()
下列关于绝对购买力平价和相对购买力平价关系的说法中,正确的是()。
为研究植物之间的信息是通过地上还是地下部分进行交流,有研究者设计了如下实验:将11株盆栽豌豆等距排列,6~11号植株在根部有管子相通,1~6号的根部不联系(图6)。用高浓度的甘露醇(一种天然糖类,模拟维管植物干旱刺激的常用物质)浇灌,来刺激6号植株,15
有位历史老师教学生记忆明朝迁都北京的历史年代,指导学生把1421记成“一事二益”,这种方法是()。
发展经济和保护环境,关系到人类的前途和命运,成为全球普遍关注、亟待解决的重大问题。西方工业社会_________了第二次世界大战以来经济和社会迅猛发展的人间喜剧,_________了科技革命给人类带来的空前无限的风光.但也亲身体验了环境破坏所带来的生态危机
固定增长的股息贴现模型需要以下哪个作为前提()。Ⅰ.股息以固定速度增长Ⅱ.股息增长率不断变化Ⅲ.要求贴现率小于股息增长率
Access数据库的结构层次是()。
TheroadfromMilduratoMerbein,innorth-westVictoria,isasadsight.Manyofitsfarmsarecoveredwithwinegrapes,dying
最新回复
(
0
)