类比二分搜索算法，设计k分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素，……，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到

admin2009-02-15 58

问题类比二分搜索算法，设计k分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素，……，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为(57)，在最好情况下搜索失败的时间复杂度为(58)。

选项 A、O(logn)
B、O(nlogn)
C、O(log_kn)
D、O(nlog_kn)

答案C

解析与二分法查找类似，k分查找法可用k叉树来描述。k分查找法在查找成功时进行比较的关键个数最多不超过树的深度，而具有n个结点的k叉树的深度为　[log_kn(k+1)]+1，所以，k叉查找法在查找成功时和给定值进行比较的关键字个数至多为　[log_k　n]+1，即时间复杂度为O(log_k　n)。同时，k分查找法在查找不成功时，和给定值进行比较的关键字个数也至多为[log_kn(k+1)]+1，即时间复杂度为O(log_kn)。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

(7)是面向对象程序设计语言不同于其他语言的主要特点，是否建立了丰富的(8)是衡量一个面向对象程序设计语言成熟与否的重要标志之一。

计算机系统中广泛采用了RAID技术，在各种RAID技术中，磁盘容量利用率最低的是(67)。

活动目录(Active　Directory)是由组织单元、域、(36)和域森林构成的层次结构，安装活动目录要求分区的文件系统为(37)。

假设模拟信号的最高频率为5MHz，采样频率必须大于(14)，才能使得到的样本信号不失真，如果每个样本量化为256个等级，则传输的数据速率是(15)。

在下图所示的树型文件系统中，方框表示目录，圆圈表示文件，“/”表示路径中的分隔符，“/”在路径之首时表示根目录。图中，(8)。假设当前目录是A2，若进程A以如下两种方式打开文件f1：方式①fd1=open("(9)/f2"，o_RDONLY

在MIB-2功能组的接口组中，表征某个交换机端口的状态为故障时，对象(42)。

在X.25分组级协议(X.25PLP)中，分组类犁标志是由分组头的第三个字节组成的，若该字节最低一位是“0”，则表示该分组为(20)。

在面向对象分析过程中，用概念模型来详细描述系统的问题域，用(5)来表示概念模型。(6)关系用于表示类与类、接口与接口之间的继承关系；在Java中，用(7)关键字来直接表示这种关系。

支票户存入现金时，会计分录为()

男性，60岁，突发胸骨后压榨性疼痛2小时，并向左肩放射，伴多汗、恶心、气短首先应做下列哪项检查对确立初步诊断最重要

对X线性质的描述，错误的是

具有补火助阳、温通经脉作用的药物是具有温中回阳、温肺化饮作用的药物是

多为处于急性情绪危象，甚至精神崩溃或企图自杀的人提供的心理咨询形式为

刘女士34岁。阴道分泌物增多伴轻度外阴瘙痒2周。妇科检查见分泌物呈灰白色，均匀一致，并粘附于阴道壁，阴道黏膜无充血。对该病人进行检查时，正确的操作是

按《贷款通则》的规定，属于借款人违约的风险形式有()。

甲委托乙寄售行以该行名义将甲的一台仪器以3000元出售，除酬金外双方对其他事项未作约定。其后，乙将该仪器以3500元卖给了丙，为此乙多支付费用100元。根据合同法律制度的规定，下列各项中，正确的有()。

Aroundtheworldyoungpeoplearespendingunbelievablesumofmoneytolistentorockmusic.Forbesmagazineclaimsthat【C1】___

软件设计师上午基础知识考试

软考中级

(7)是面向对象程序设计语言不同于其他语言的主要特点，是否建立了丰富的(8)是衡量一个面向对象程序设计语言成熟与否的重要标志之一。

计算机系统中广泛采用了RAID技术，在各种RAID技术中，磁盘容量利用率最低的是(67)。

活动目录(Active Directory)是由组织单元、域、(36)和域森林构成的层次结构，安装活动目录要求分区的文件系统为(37)。

假设模拟信号的最高频率为5MHz，采样频率必须大于(14)，才能使得到的样本信号不失真，如果每个样本量化为256个等级，则传输的数据速率是(15)。

在下图所示的树型文件系统中，方框表示目录，圆圈表示文件，“/”表示路径中的分隔符，“/”在路径之首时表示根目录。图中，(8)。假设当前目录是A2，若进程A以如下两种方式打开文件f1：方式①fd1=open("(9)/f2"，o_RDONLY

在MIB-2功能组的接口组中，表征某个交换机端口的状态为故障时，对象(42)。

在X.25分组级协议(X.25PLP)中，分组类犁标志是由分组头的第三个字节组成的，若该字节最低一位是“0”，则表示该分组为(20)。

在面向对象分析过程中，用概念模型来详细描述系统的问题域，用(5)来表示概念模型。(6)关系用于表示类与类、接口与接口之间的继承关系；在Java中，用(7)关键字来直接表示这种关系。

支票户存入现金时，会计分录为()

男性，60岁，突发胸骨后压榨性疼痛2小时，并向左肩放射，伴多汗、恶心、气短首先应做下列哪项检查对确立初步诊断最重要

对X线性质的描述，错误的是

具有补火助阳、温通经脉作用的药物是具有温中回阳、温肺化饮作用的药物是

多为处于急性情绪危象，甚至精神崩溃或企图自杀的人提供的心理咨询形式为

刘女士34岁。阴道分泌物增多伴轻度外阴瘙痒2周。妇科检查见分泌物呈灰白色，均匀一致，并粘附于阴道壁，阴道黏膜无充血。对该病人进行检查时，正确的操作是

按《贷款通则》的规定，属于借款人违约的风险形式有()。

甲委托乙寄售行以该行名义将甲的一台仪器以3000元出售，除酬金外双方对其他事项未作约定。其后，乙将该仪器以3500元卖给了丙，为此乙多支付费用100元。根据合同法律制度的规定，下列各项中，正确的有()。

Aroundtheworldyoungpeoplearespendingunbelievablesumofmoneytolistentorockmusic.Forbesmagazineclaimsthat【C1】___

活动目录(Active　Directory)是由组织单元、域、(36)和域森林构成的层次结构，安装活动目录要求分区的文件系统为(37)。