首页 > 试题广场 >

设顺序线性表的长度为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)
mmryziqi头像 mmryziqi

设分块查找中将长为 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)
miao_星人头像 miao_星人
分块查找又称索引顺序查找，由分块有序（每一块中的关键字不一定有序，但是前一块中的最大关键字必须小于后一块中的最小关键字，即分块有序。）的索引表和线性表组成。例如把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)
Lance217头像 Lance217
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)
jfjdjdjs头像 jfjdjdjs
(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)
sun倩头像 sun倩
不管块间采用顺序查找 还是折半查找 平均查找长度都是6.5
块间顺序查找是(b+1)/2+(s+1)/2
块间折半查找是log2(b+1)+(s+1)/2 （log2(b+1)上取整）
发表于 2022-12-12 16:07:32 回复(0)
牛客732606493号头像 牛客732606493号
发表于 2022-05-11 09:15:21 回复(0)
牛客803828780号头像 牛客803828780号
跟上题一样 快的平均查找5*(5+1)/2/5=3 快内平均6*7/2/6=3.5 总6.5
发表于 2022-01-05 20:56:43 回复(0)
notonlysql头像 notonlysql
分块查找中索引表查找可用二分或顺序。块内查找只能顺序。二分的平均时间 1+2+3/3
发表于 2021-10-07 12:01:41 回复(0)
ワBEros头像 ワBEros
😃
发表于 2020-01-16 19:47:03 回复(0)
高1头像 高1
(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)
sgbs头像 sgbs
有谁可以给解释下呢？？
发表于 2017-06-07 08:50:00 回复(0)
提交观点

问题信息

查找
上传者：阿奻_
难度：
18条回答 13035浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号