设顺序线性表的长度为 30,分成 5 块,每块 6 个元素,如果采用分块查找,则其平均查找长度为( )。
(A) 6 (B) 11 (C) 5 (D) 6.5
分块查找:对块和块内进行顺序查找。
先找块:一共5块,查找的总长度为Σ(i=1...5) i = (5 * (5 + 1)) / 2【等差求和公式】 = 15------>故而选块的平均查找长度为15 / 5 = 3。
然后找块内元素:单个块内有6个元素,查找总长度为Σ(i=1...6) i = (6 * (6 + 1)) / 2 = 21------>故而块内查找元素的平均查找长度为21 / 6 = 3.5。
即该顺序线性表的分块查找平均查找长度为3+3.5 = 6.5。
21*5+6(1+2+3+4+5)=195 195/30=6.5
3+3.5
平均查找长度 = (1+5)/2+ (6 + 1) /2= 3+3.5 =6.5
平均查找长度 = √(30/6) + 6 - 1 = √5 + 6 - 1 ≈ 6.24
D
用户登录可进行刷题及查看答案
登录后提交答案