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

admin2019-03-04 50

问题在查找算法中，可用平均查找长度(记为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/K3TZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

已知有6个村子，相互之间道路的距离如下图所示。现拟合建一所小学。已知甲村有小学生50人，乙村40人，丙村60人，丁村20人，戊村70人，己村90人。从甲村到己村的最短路程是(68)；小学应该建在_(69)村，使全体学

射频识别(RFID)是物联网中常用的无线通信技术，它通过__________识别特定目标并读写相关数据。

任何组织的能力都是有限的，任何组织的资源也都是有限的。公司在选择项目优先级时经常用到DIPP分析法。以下关于DIPP的理解中，不正确的是：()。

下图是一个选择出行路线的“决策树图”，统计路线1和路线2堵车和不堵车的用时和其发生的概率(P)，计算出路线1和路线2的加权平均用时，根据计算结果选择出行路线。以下结论中，正确的是：()。

(2009上集管)按照规范的文档管理机制，程序流程图必须在______两个阶段内完成。

(2012下项管)依照招标投标法，项目公开招标的资格预审阶段，在《资格预审须知》文件中可以______。

(2012上项管)配置管理中有一项工作是变更控制，其中配置状态的过程如下图所示：在这个状态变化过程中，图中的(1)、(2)、(3)三个状态依次为______。

地理标志

初产妇停经8周时，可以出现()

患者，女，42岁。己婚，患滴虫性阴道炎，需阴道灌洗局部治疗。为该患者作阴道灌洗应选择的溶液是

以下是必须经过国务院卫生行政部门批准方可生产的特殊用途化妆品的各种用途。不包括用于

患者，男性，70岁。近5年来乏力，尿频，每晚尿5～6次，但无尿痛，无尿急。昨大量饮酒后下腹部胀痛逐渐加重，查体在耳止骨联合上区可触到一圆形具有压痛的弹性肿物，临床诊断最可能是

借款人申请贷款时，除了借款人名称、企业性质、经营范围，申请贷款的种类、期限、金额、方式、用途，还需提供用款计划，还本付息计划等资料。()

一般选取()等指标来衡量目标区域信贷资产的流动性状况。

Ithasbeenarguedthatwhereschoolsbecomebureaucratized,theybecomeboundupwiththetechniquesandimplementationofthe