我要招人

去企业版

首页 > 试题广场 >

一个文件包含了200个记录，若采用分块查找法，每块长度为4，

[单选题]

一个文件包含了200个记录，若采用分块查找法，每块长度为4，则平均查找长度为多少？

```
30
```
```
28
```
```
29
```
```
32
```

查看答案及解析

推荐

zt_xcyk

我觉得要看这50个块之间是否是有序的。

要是有序，可以二分查找，然后确定在那一个块中((n+1)log2(n+1))/n - 1 ，然后在这个块中查找

要是无序，则顺序查找，平均查找长度就是（1+50）/2=25.5，然后块中查找(1+4)/2=2.5 总共28

编辑于 2019-05-05 14:19:55 回复(5)

Lith

查找块(1+50)*50/2*50=26

在一个四个大小的块里查找需要2次

26+2

发表于 2015-09-04 11:56:10 回复(0)

已注销

设关键字个数为n,在各关键字等概率查找的前提下, 1、顺序查找的平均查找长度ASL=(n+1)/2, 2、在n趋于无穷大时,折半查找的ASL=((n+1)log2(n+1))/n - 1,当n大于50时,ASL约等于log2(n+1)-1 3、设分块查找中将长为 n 的表分成均等的 b 个块,每块 s 个元素,则 b = (n / s)上取整,如果索引表中采用顺序查找,则ASL=(b+1)/2+(s+1)/2；如果索引表中采用折半查找,则ASL=(s+1)/2+log2(b+1)-1

发表于 2020-02-25 09:01:55 回复(0)

DAY&DREAMER

(50+1)/2+(4+1)/2=28

发表于 2019-07-09 17:16:14 回复(1)

忆梦＆....

ASL = (n/s + s)/2 + 1

(200/4+4)/2+1=28

发表于 2015-01-26 16:09:17 回复(0)

牛客905435118号

这里没有说块索引是有序的，就当作是无序的，需要对块做顺序查找，评论(50+1)/2=25.5次，再对子块进行顺序查找，平均(4+1)/2=2.5，所以一共是28

发表于 2020-12-24 01:06:08 回复(0)

云云云一飞冲天

主要是开始认为使用分块查找本身就要求：每一块中的数据元素不必有序，但块与块之间必须“按块有序”，可能容易让人迷惑；

这里因为说的是200个记录，并没强调有序，更多的是让我们使用分块查找的思想来解题；

所以自然有：从50个块中顺序查找：(1+50)/2=25.5，然后在块中顺序查找：(1+4)/2=2.5

发表于 2022-08-21 00:20:02 回复(0)

Nathan-Chen

分块查找平均时间公式：（n/ s+ s）/2+1

发表于 2021-08-21 20:52:29 回复(0)

牛客571626675号

ASL=1/2（m+t）+1m是块数，t是每个块中存放的记录条数

发表于 2021-04-14 17:50:27 回复(0)

牛客801282807号

我觉得有问题如果索引表采用二分这里面平均查找长度8

发表于 2022-08-10 11:18:10 回复(0)

已注销

B （n/s+s）/2+1

发表于 2020-11-17 10:41:56 回复(0)

Simon..

<p>没说索引有序！</p>

发表于 2020-11-16 21:50:38 回复(0)

牛客526642506号

ASL，是查找算法的查找成功时的平均查找长度的缩写
设关键字个数为n,在各关键字等概率查找的前提下, 1、顺序查找的平均查找长度ASL=(n+1)/2, 2、在n趋于无穷大时,折半查找的ASL=((n+1)log2(n+1))/n - 1,当n大于50时,ASL约等于log2(n+1)-1 3、设分块查找中将长为 n 的表分成均等的 b 个块,每块 s 个元素,则 b = (n / s)上取整,如果索引表中采用顺序查找,则ASL=(b+1)/2+(s+1)/2；如果索引表中采用折半查找,则ASL=(s+1)/2+log2(b+1)-1

发表于 2020-09-28 10:12:09 回复(0)

be19

应该是折半加上顺序查找时间

发表于 2020-08-28 09:07:41 回复(0)

拧巴小麻花

ASL=(b+1)/2+(s+1)/2

发表于 2020-07-06 15:38:48 回复(0)

牛客818246740号

<p>分块查找是。两个。时间加起来的、我只算了一个的时间</p>

发表于 2020-06-30 15:53:38 回复(0)

牛客218196695号

则平均查找长度为块间二分：公式 ASL=((n+1)log2(n+1))/n - 1,

                               块内顺序:                   AsL= n*(n+1)/2*n;

发表于 2020-05-16 09:46:58 回复(0)

牛客215999200号

200/4=50;

（50+1)/2+(1+2+3+4)/4=28

发表于 2020-02-24 11:29:19 回复(0)

aguo718

笔记：分块查找、平均查找长度

发表于 2020-01-08 22:28:58 回复(0)

提交观点

问题信息

腾讯查找

上传者：乎乎

难度：

19条回答 818收藏 10511浏览

一个文件包含了200个记录，若采用分块查找法，每块长度为4，

问题信息

热门推荐

相关试题