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

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

admin2019-12-10  74
问题 为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行(    )次关键字比较。
选项 A、10
B、14
C、20
D、21
答案B
解析 首先需要知道折半查找成功的平均查找长度为log2(n+1)—1。
为使查找效率最高，可对有65025个元素的有序顺序表分块，每块有=255个元素。为每一块建立一个索引项，索引表共255个索引项。若对索引表和每一块都采用折半查找，则查找效率最高，计算可得
ASLIndexSeqSearch=ASLIndex+ASLBlock=log2(255+1)—1+log2(25 5+1)—1=14
下面补充一些关于折半查找的概念。
补充(1):折半查找的时间复杂度为O(log2n)。
补充(2):折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。
补充(3):对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高度为
h=[log2(n+1)]或者h=[log2(n+1)]+1
例1：在具有15个记录的有序连续顺序文件上采用折半查找法查找一个文件中不存在的记录，需要进行(    )次关键字的比较。
A．0   B．4
C．5
D．1 5
解析：此题可以利用补充(3)的判定树的高度来解答。由于n=15，可知判定树的高度为4。一棵高度为4，具有15个结点的二叉树为一棵满二叉树，所以查找一个不存在的结点需要比较4次。
例2：对一个长度为50的有序表进行折半查找，最多比较(    )次就能查找出结果。
A．6
B.7
C.8
D.9
解析：与例1类似，可以得到判定树的高度为6，所以最多比较6次就能查找出结果。
转载请注明原文地址:https://www.kaotiyun.com/show/9s3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)