为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

admin2021-08-17 50

问题为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

选项 A、10
B、14
C、20
D、21

答案B

解析首先需要知道折半查找成功的平均查找长度为log₂(n+1)-1。为使查找效率最高，可对有65 025个元素的有序顺序表分块，每块有

=255个元素。为每一块建立一个索引项，索引表共255个索引项。若对索引表和每一块都采用折半查找，则查找效率最高，计算可得 ASL_{IndexSeqSearch}=ASL_Index+ASL_Block=log₂(255+1)一1+log₂(255+1)一1=14
下面补充一些关于折半查找的概念。
补充(1)：折半查找的时间复杂度为O(log₂n)。
补充(2)：折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。
补充(3)：对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高度为 h=[log₂(n+1)]或者h=[log₂(n+1)]+1

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

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

计算机408

学硕统考专业

为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()。

UNIX文件系统中，索引节点(i-node)其本质是()。

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数；(2)画出散列表；(

如果一个没有内存映射的IO设备与主存之间交换数据，希望这种数据交换不经过CPU来完成，那么，可以采用的方法是()。

相对于硬布线控制器，微程序控制器的特点是()。

[x]补=1．x1x2)x3x4，则当满足()时，x>一1／2成立。

75岁男性，因外伤失血性休克，快速输血输液治疗，当休克纠正后不久出现头痛，呼吸急促，发绀，咳嗽并咳出血性泡沫痰，此时应考虑

按经脉属络关系，手少阳属

已知A气体含量为80％时，其峰高为100mm，现加入一个等体积待测样品，得到峰高为70mm，使用单点校正法可知该样品中A气体的体积百分含量是

四环素牙主要是由于四环素沉积在

水难溶性药物或注射后要求延长药效作用的固体药物，可制成注射剂的类型是

根据宪法和法律，下列哪些对人大代表或人大常委会委员的罢免行为是合法的?()

有担保流动资金贷款的受理时，对于有共同申请人的，必需要求担保责任大的申请人提交有关申请材料。()

设函数z=z(x，y)由方程x2+y2+z2=xyf(z2)所确定，其中f是可微函数，计算并化成最简形式．

Atabirthdayparty,halftheguestsdrinkcola,aquarterhavelemonade,asixthhaveorangejuice,andtheremainingthreehav