首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为: 此处Pi为表中第i个记录被查找的概率,Ci为查找第i个记录时同关键字比较的次数,n为表中记录数。 以下叙述中均假定每一个记录被查找的概率相等,
在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为: 此处Pi为表中第i个记录被查找的概率,Ci为查找第i个记录时同关键字比较的次数,n为表中记录数。 以下叙述中均假定每一个记录被查找的概率相等,
admin
2019-03-04
42
问题
在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为:
此处P
i
为表中第i个记录被查找的概率,C
i
为查找第i个记录时同关键字比较的次数,n为表中记录数。
以下叙述中均假定每一个记录被查找的概率相等,即P
i
=//n(i=1,2,…,n)。当表中的记录连续存储在一个一维数组中时,可采用顺序查找与折半查找方法(折半查找要求表是按关键字有序排列的)。顺序查找时的ASL为(19),折半查找时的ASL为(20)。记录的关键字有序时,用二叉排序树查找记录,在最坏的情况下,ASL为(21)。当二叉排序树是一棵平衡树时,ASL为(22)。在平衡树上删除一个结点后可以通过旋转使其平衡,最坏的情形下需(23)次旋转。
选项
A、O(1)
B、O(log
2
n)
C、O(log
2
n
2
)
D、O(nlog
2
n)
E、O(n)
答案
B
解析
顺序查找的基本思想是:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键字和给定值k相比较。若当前扫描到的结点关键字与k相等,,则查找成功;若扫描结束后,仍未找到关键字等于k的结点,则查找失败。顺序查找方法既适用于线性表的顺序存储结构,也适用于线性表的链式存储结构。
成功的顺序查找的平均查找长度如下:
ASL=
p
i
c
i
=
(n-i+1)=np1+(n-1)p2+…+2pn-1+pn
在等概率情况下,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=[(low+high)/2]。
(2)将待查的k值与R[mid].key比较,若相等,则查找成功并返回此位置,否则需确定新的查找区间,继续二分查找,具体方法如下:
.若R[mid].key>k,则由表的有序性可知R[mid,…,n].key均大于A,因此若表中存在关键字等于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(log2n)。
在二叉排序树上查找,和二分法查找类似,也是一个逐步缩小查找范围的过程。在二叉排序树上进行查找时,若查找成功,则是从根结点出发,走了一条从根到待查结点的路径。若查找不成功,则是从根结点出发,走了一条从根到某个叶子的路径。与二分法查找类似,这种方法中和关键字比较的次数不超过树的深度。
二分查找法查找长度为n的有序表,其判定树是唯一的。含有n个结点的二叉排序树却不唯一。对于含有同样一组结点的表,由于结点插入的先后次序不同,所构成的二叉排序树的形态和深度也可能不同,这与在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关。
(1)在最坏的情况下,二叉排序树是通过把一个有序表的n个结点依次插入而生成的,此时所得的二叉排序树退化为一棵深度为n的单支树,它的平均查找长度和单链表上的顺序查找相同,也是(n+1)/2。
(2)在最好的情况下,二叉排序树在生成的过程中,树的形态比较匀称,最终得到的是一棵形态与二分法查找的判定树相似的二叉排序树,此时它的平均查找长度大约是 log2n。
对于平衡的二叉排序树查找,平衡二叉排序树中的每个结点的左、右子树高度差不大于1,n个结点的平衡树的深度和log2n是同数量级的。对二叉排序树来说,它的查找时间与树的深度成正比。因此,平衡二叉排序树的平均查找时间为O(log2n)。
在平衡树上删除或插入结点往往会破坏树的平衡。通过旋转又可使其重新成为一棵平衡树。在最坏情况下,从叶子开始一直调整到根为止,需进行的旋转次数与树的深度一致,等于O(log2n)次。
转载请注明原文地址:https://kaotiyun.com/show/d3TZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
以下关于外包及外包管理的叙述中,(49)是不正确的。
除了测试程序之外,黑盒测试还适用于测试(11)阶段的软件文档。
已知有6个村子,相互之间道路的距离如下图所示。现拟合建一所小学。已知甲村有小学生50人,乙村40人,丙村60人,丁村20人,戊村70人,己村90人。从甲村到己村的最短路程是__________(68);小学应该建在___________(69)村,使全体学
质量控制的方法、技术和工具有很多,其中(1)可以用来分析过程是否稳定、是否发生了异常情况。(2)直观地反映了项目中可能出现的问题与各种潜在原因之间的关系。(1)
为了保护网络系统的硬件、软件及其系统中的数据,需要相应的网络安全工具。以下安全工具中,()被比喻为网络安全的大门,用来鉴别什么样的数据包可以进入企业内部网。
(2010上项管)某软件开发项目计划设置如下基线:需求基线、设计基线、产品基线。在编码阶段,详细设计文件需要变更。以下叙述中,______是正确的。
(2007上监理)按照软件配置管理的原始指导思想,受控制的对象应是_____(1)。实施软件配置管理包括4个最基本的活动,其中不包括_____(2)。(2)
(2009下项管)在描述复杂关系时,图形比文字叙述优越得多。下列四种图形工具中,不适合需求分析阶段使用的是______。
(2013下集管)(2010上系分)项目管理是保证项目成功的核心手段,在项目实施过程中具有重大作用。_____(1)是项目管理的重要元素,是项目实施的基础;_____(2)要确定哪些工作是项目应该做的,哪些工作不应该包含在项目中;_____(3)采用科学的
(2005下项管)一个产业的竞争状态取决于五种基本竞争力量:新竞争者的进入、替代品的威胁、买方的讨价还价能力、供应者的讨价还价能力以及______。
随机试题
焊缝线能量大时,焊缝金属的_____就差。
论述侵权行为的民事责任与违约责任的区别。
下列关丁mRNA的叙述,不正确的是()(2006年)
肝肾阴虚,风阳上扰的治法为( )。中风后遗症,半身不遂的治法为( )。
各种不同账务处理程序的主要区别是()。
下列不属于评估战略备选方案通常使用的标准的是()。
该市2005年6月的总保费收入、比去年同期约增长了()。与上一年同期相比保费收入增幅最大的是()。
甲从/4地步行到B地,出发1小时40分钟后,乙骑自行车也从A地出发,骑了10公里时追到甲。于是,甲改骑乙的自行车前进,共经5小时到达B地,这恰是甲步行全程所需时间的一半。问骑自行车的速度是多少公里/小时?(甲、乙骑自行车速度一样)
A、Tocompletehis/herpersonalinformation.B、Tomakeacoverletterwiththese.C、Toimpresstheemployers.D、Todistinguishth
Bynowyouknowthat【C1】______yourmoney’sworthisnotjustamatterofluck.Itismoreoftenthe【C2】______of’buyingskill.【
最新回复
(
0
)