设顺序线性表的长度为30,分成5块,每块6个元素,如果采用分块查找,则其平均查找长度为()。
6
11
5
6.5
设分块查找中将长为 n 的表分成均等的 b 个块,每块 s 个元素,则 b = (n / s)上取整。如果索引表中采用顺序查找,则ASL=(b+1)/2+(s+1)/2;如果索引表中采用折半查找,则ASL=(s+1)/2+log2(b+1)-1;没说清楚块间查找用何种方式。
我认为是2.8+3.5=6.3,请大神们指教。3.5没问题,问题在块的查找。
块一共5个:先与第1块的最后一个比较;若大了,再与第2块的最后一个比较;若大了,再与第3块的最后一个比较;若大了,再与第4块的最后一个比较;若大了,只能在第5个块里,或者没有。(没有的情况可以交给块内查找来处理。)
查找的值若在第1块中则需要比较1次;若在第2块中则需要比较2次;若在第3块中则需要比较3次;若在第4块或第5块中则需要比较4次。1/5 * (1+2+3+4+4) = 2.8
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题