首页 > 试题广场 >

设顺序线性表的长度为30,分成5块,每块6个元素,如果采用分

[单选题]

设顺序线性表的长度为30,分成5块,每块6个元素,如果采用分块查找,则其平均查找长度为()。

  • 6
  • 11
  • 5
  • 6.5
二分查找的平均时间不是(1+2+3)/3=2;吗
顺序查找时间不是(1+6)/2=3.5吗
结果怎么是6.5。
那里弄错了啊
发表于 2017-06-01 16:42:37 回复(2)
更多回答
找块:(1+2+3+4+5)/5=3
在块内找元素:   (1+2+3+4+5+6)/6=3.5 
合计:3+3.5=6.5
发表于 2018-01-08 15:07:02 回复(4)

设分块查找中将长为 n 的表分成均等的 b 个块,每块 s 个元素,则 b = (n / s)上取整。
如果索引表中采用顺序查找,则ASL=(b+1)/2+(s+1)/2;
如果索引表中采用折半查找,则ASL=(s+1)/2+log2(b+1)-1;
没说清楚块间查找用何种方式。

发表于 2017-07-25 11:47:53 回复(2)
这道题认为分块查找采用块间块内都采用顺序查找,虽然块内可以二分,故平均查找长度为(5+1)/2+(6+1)/2
编辑于 2017-06-13 23:23:05 回复(0)
分块查找又称索引顺序查找,由分块有序(每一块中的关键字不一定有序,但是前一块中的最大关键字必须小于后一块中的最小关键字,即分块有序。)的索引表和线性表组成。例如把r【1....n】分为 b 块,则前 b-1 块节点数为 s = 【n/b】,最后一块允许小于或等于s。索引表是一个递增有序表。 平均查找长度分为两部分,索引表的查找+块内的查找。(索引表能够用二分法和顺序查找,块内无序,所以只能用顺序查找) 如果以二分查找来确定块,则 ASL = log2(b+1)-1 + (s+1)/2。 如果以顺序查找来确定块,则 ASL = (b+1)/2 + (s+1)/2。 如果以哈希查找来确定块,则ASL=1 + (s+1)/2。
编辑于 2019-09-20 16:07:57 回复(0)
ASL =∑PiCi (Pi 为查找第i个记录的概率,Ci为找到第i个记录数据需要比较的次数,Ci随查找过程的不同而不同。),Pi为常数。
索引表平均查找长度:ASL(索) =∑PiCi=Pi∑Ci=(1/5)*(1+2+3+4+5)=3
分块查找的平均查找长度:ASL(块)=∑PiCi=Pi∑Ci=(1/6)*(1+2+3+4+5+6)=3.5
则其总过程平均查找长度为ASL=ASL(索)+ASL(块)=3+3.5=6.5
发表于 2018-06-24 21:19:35 回复(0)
5块,可能性为1/5
6个,可能性为1/6
所以 (1+2+3+4+5)*1/5 为查找到块的平均
所以 (1+2+3+4+5*6)*1/6 为查找到个的平均

快速计算,首相加末相乘以相数除二

发表于 2020-03-20 06:19:57 回复(0)
(s²+2s+n)/2s
发表于 2019-11-25 18:53:38 回复(0)
块:(5+1)/2=3 块内:(6+1)/2=3.5 ASL=3+3.5=6.5
发表于 2025-03-06 14:21:13 回复(0)
不管块间采用顺序查找 还是折半查找 平均查找长度都是6.5
块间顺序查找是(b+1)/2+(s+1)/2
块间折半查找是log2(b+1)+(s+1)/2 (log2(b+1)上取整)
发表于 2022-12-12 16:07:32 回复(0)
发表于 2022-05-11 09:15:21 回复(0)
跟上题一样 快的平均查找5*(5+1)/2/5=3 快内平均6*7/2/6=3.5 总6.5
发表于 2022-01-05 20:56:43 回复(0)
分块查找中索引表查找可用二分或顺序。块内查找只能顺序。二分的平均时间 1+2+3/3
发表于 2021-10-07 12:01:41 回复(0)
😃
发表于 2020-01-16 19:47:03 回复(0)
(n/t+1)/2+1
n为总记录个数,t是每块的记录数
发表于 2019-04-20 22:28:42 回复(0)

我认为是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

发表于 2018-11-24 15:26:50 回复(0)
分块查找:如果以顺序查找来确定块,则 ASL = (b+1)/2 + (s+1)/2、(b为块数,s为前b-1块中的节点数)。
发表于 2017-07-13 22:15:22 回复(0)
有谁可以给解释下呢??
发表于 2017-06-07 08:50:00 回复(0)