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

admin2021-08-17 54

问题为提高查找效率，对有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

学硕统考专业

若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。先来先服务算法；

如下图所示为一个网络连接的示意图，主机1到主机2采用了SLIP网络连接，SLIP网络可以传输的最大数据段是296字节，主机2和主机3使用了以太网连接。请问：主机3可以在TCP包中承载多少数据?

图1-2是某存储芯片的引脚图，请回答：(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根，存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别?(

图2-2所示的CPU逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位)，数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout)控制命令，但图中未标出。(

下列关于中断I／O方式和DMA方式比较的叙述中，错误的是

下面的地址中，属于单播地址的是()。

患儿，男性，12岁。头痛、发热4小时，伴呕吐、抽搐，以“流行性脑脊髓膜炎”入院。查体温39．2℃，脉搏110次／分，查体过程中患者又连续抽搐两次。针对患者目前的情况。下列各项措施中，不恰当的是

麻疹病人出疹至哪一部位表示出齐

某妇女主诉外阴部瘙痒，护士应建议她

A、0B、1C、2D、3A故选A。

依据《中华人民共和国环境影响评价法》，对环境有重大影响规划实施后，组织实施环境影响跟踪评价的单位是()。

在生产过程中要进行检验和试验，以保证生产过程的正常和稳定，为此供方应建立进行检验和试验活动的文件化工作程序，这些工作程序包括(　　)检验和试验的工作程序。

某外贸公司对外由CFR报价,如果该公司先将货物交到货站或使用滚装与集装箱运输时,应采用什么为宜()

当今教育评价存在的主要问题有()。

我国对农业社会主义改造的途径是()

•ReadthispartofafaxfromMsSophiaLin,theconferenceorganizer.Wehavepleasureininvitingyoutoourannualco

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

计算机408

学硕统考专业

若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。先来先服务算法；

如下图所示为一个网络连接的示意图，主机1到主机2采用了SLIP网络连接，SLIP网络可以传输的最大数据段是296字节，主机2和主机3使用了以太网连接。请问：主机3可以在TCP包中承载多少数据?

图1-2是某存储芯片的引脚图，请回答：(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根，存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别?(

图2-2所示的CPU逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位)，数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout)控制命令，但图中未标出。(

下列关于中断I／O方式和DMA方式比较的叙述中，错误的是

下面的地址中，属于单播地址的是()。

患儿，男性，12岁。头痛、发热4小时，伴呕吐、抽搐，以“流行性脑脊髓膜炎”入院。查体温39．2℃，脉搏110次／分，查体过程中患者又连续抽搐两次。针对患者目前的情况。下列各项措施中，不恰当的是

麻疹病人出疹至哪一部位表示出齐

某妇女主诉外阴部瘙痒，护士应建议她

A、0B、1C、2D、3A故选A。

依据《中华人民共和国环境影响评价法》，对环境有重大影响规划实施后，组织实施环境影响跟踪评价的单位是()。

在生产过程中要进行检验和试验，以保证生产过程的正常和稳定，为此供方应建立进行检验和试验活动的文件化工作程序，这些工作程序包括( )检验和试验的工作程序。

某外贸公司对外由CFR报价,如果该公司先将货物交到货站或使用滚装与集装箱运输时,应采用什么为宜()

当今教育评价存在的主要问题有()。

我国对农业社会主义改造的途径是()

•ReadthispartofafaxfromMsSophiaLin,theconferenceorganizer.Wehavepleasureininvitingyoutoourannualco

在生产过程中要进行检验和试验，以保证生产过程的正常和稳定，为此供方应建立进行检验和试验活动的文件化工作程序，这些工作程序包括(　　)检验和试验的工作程序。