在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：此处Pi为表中第i个记录被查找的概率，Ci为查找第i个记录时同关键字比较的次数，n为表中记录数。以下叙述中均假定每一个记录被查找的概率相等，

admin2019-03-04 51

问题在查找算法中，可用平均查找长度(记为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₂n)
C、O(log₂n²)
D、O(nlog₂n)
E、O(n)

答案E

解析

转载请注明原文地址:https://kaotiyun.com/show/ztTZ777K

本试题收录于：数据库系统工程师上午基础知识考试题库软考中级分类

数据库系统工程师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

数据库系统工程师上午基础知识考试

软考中级

软件系统的版本号由3部分构成，即主版本号+次版本号+修改号。某个配置项的版本号是1，0，按照配置版本号规则表明(63)。

某项目计划投资1000万元，经过估算，投产后每年的净收益为200万元，则该项目的静态投资回收期为5年。如果考虑到资金的时间价值，假设贴现率为10％，那么该项目的动态投资回收期(56)。

已知网络图各段路线所需费用如下图所示，图中甲线和乙线上的数字分别代表相应点的有关费用。从甲线到乙线的最小费用路线有_(66)条，最小费用为_(67)。(67)

按照软件配置管理的基本指导思想，受控制的对象应是(62)。实施软件配置管理包括4个最基本的活动，其中不包括(63)。(63)

项目可行性研究阶段的项目论证和项目评估的关系是___________。

某项目范围基准发生变化，经(62)同意，对需求规格说明书进行变更，则该配置项的状态应从(63)。(63)

(2012上集管)数据库管理系统是操纵和管理数据库的大型软件，用于建立、使用和维护数据库。以下关于数据库管理系统的描述，______是不正确的。

(2007上系分)采用UML分析用户需求时，用例UC1可以出现在用例UC2出现的任何位置，那么UC1和UC2之间的关系是______。

ParisisthecapitaloftheEuropeannationofFrance.Itisoneofthemostbeautifuland【C1】______citiesintheworld.Par

男，36岁，右侧面部及颏部遭到重击后，出现开、闭口困难，伴右侧面部及耳颞部肿痛。检查见下颌中线偏右，左侧后牙早接触，左侧开。最可能的诊断是

A．克拉维酸B．舒巴坦C．甲氧苄啶D．西司他丁E．丙磺舒与磺胺类药合用，双重阻断细菌四氢叶酸的合成而产生协同作用的药物是

下列关于有限责任公司型基金股权转让退出的说法，正确的是()。

Somepessimisticexpertsfeelthattheautomobileisboundtofallintodisuse.Theyseeadayinthenot-too-distantfuture

“_，_”的思想是范仲淹一生的真实写照，可以说具有这种思想的人在上下五千年的中国历史上比比皆是，举不胜举，作为新时代的我们更不应该逊色，要继往开来，扬帆远行!

设f(x)=ex-∫0x(x-t)f(t)dt，其中f(x)连续，求f(x)．

TheHouseisexpectedtopassapieceoflegislationThursdaythatseekstosignificantlyrebalancetheplayingfieldforunions

数据库系统工程师上午基础知识考试

软考中级

软件系统的版本号由3部分构成，即主版本号+次版本号+修改号。某个配置项的版本号是1，0，按照配置版本号规则表明(63)。

某项目计划投资1000万元，经过估算，投产后每年的净收益为200万元，则该项目的静态投资回收期为5年。如果考虑到资金的时间价值，假设贴现率为10％，那么该项目的动态投资回收期(56)。

已知网络图各段路线所需费用如下图所示，图中甲线和乙线上的数字分别代表相应点的有关费用。从甲线到乙线的最小费用路线有___________(66)条，最小费用为___________(67)。(67)

按照软件配置管理的基本指导思想，受控制的对象应是__________(62)。实施软件配置管理包括4个最基本的活动，其中不包括__________(63)。(63)

项目可行性研究阶段的项目论证和项目评估的关系是___________。

某项目范围基准发生变化，经(62)同意，对需求规格说明书进行变更，则该配置项的状态应从(63)。(63)

(2012上集管)数据库管理系统是操纵和管理数据库的大型软件，用于建立、使用和维护数据库。以下关于数据库管理系统的描述，______是不正确的。

(2007上系分)采用UML分析用户需求时，用例UC1可以出现在用例UC2出现的任何位置，那么UC1和UC2之间的关系是______。

ParisisthecapitaloftheEuropeannationofFrance.Itisoneofthemostbeautifuland【C1】______citiesintheworld.Par

男，36岁，右侧面部及颏部遭到重击后，出现开、闭口困难，伴右侧面部及耳颞部肿痛。检查见下颌中线偏右，左侧后牙早接触，左侧开。最可能的诊断是

A．克拉维酸B．舒巴坦C．甲氧苄啶D．西司他丁E．丙磺舒与磺胺类药合用，双重阻断细菌四氢叶酸的合成而产生协同作用的药物是

下列关于有限责任公司型基金股权转让退出的说法，正确的是()。

Somepessimisticexpertsfeelthattheautomobileisboundtofallintodisuse.Theyseeadayinthenot-too-distantfuture

“_____________，_____________”的思想是范仲淹一生的真实写照，可以说具有这种思想的人在上下五千年的中国历史上比比皆是，举不胜举，作为新时代的我们更不应该逊色，要继往开来，扬帆远行!

设f(x)=ex-∫0x(x-t)f(t)dt，其中f(x)连续，求f(x)．

TheHouseisexpectedtopassapieceoflegislationThursdaythatseekstosignificantlyrebalancetheplayingfieldforunions

已知网络图各段路线所需费用如下图所示，图中甲线和乙线上的数字分别代表相应点的有关费用。从甲线到乙线的最小费用路线有_(66)条，最小费用为_(67)。(67)

按照软件配置管理的基本指导思想，受控制的对象应是(62)。实施软件配置管理包括4个最基本的活动，其中不包括(63)。(63)

“_，_”的思想是范仲淹一生的真实写照，可以说具有这种思想的人在上下五千年的中国历史上比比皆是，举不胜举，作为新时代的我们更不应该逊色，要继往开来，扬帆远行!