我要招人

去企业版

首页 > 试题广场 >

在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表

[单选题]

在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（）。

```
(n+1)/2
```
```
n
```
```
3n/4
```
```
n/4
```

查看正确选项

赞花婆

正确答案： A 解析：【解析】在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为 1 ；在最坏情况下，最后一个元素才是要找的元素，则比较次数为 n 。两种情况平均即（ 1+n ） /2 。故本题答案为 A 选项。

发表于 2017-04-28 13:29:49 回复(2)

sunlight_run

这道题假设了查找的元素一定在表中，在最坏情况下，查找n-1次，而不是n次，所以答案为n/2似乎更妥

发表于 2017-06-30 09:21:00 回复(3)

不要浮于表面

如果最后一个才是要找的数字，就不用比较了啊，最差是n-1次，最好是1次，平均应该是n/2次吧

发表于 2019-05-31 10:21:19 回复(1)

wangChaoNK

解析:
因为每一个位置出现的几率相同故为p=1/n
n的位置查找的总次数为A=n*(1+n)/2
平均下来的次数=p*A=(n+1)/2

发表于 2017-05-24 12:27:21 回复(5)

易大侠

我数学好一点，用数学思路给你们解答，假设有n个元素，既有n种可能的结果，结果分别是是，1次，2次，3次，到n次，既总共可能次数为sum=1+2+3+4+..+n。换算公式后为，sum=n（n+1）/2次，这里得到的是总可能次数，我们再除以可能的结果n，得到平均每次可能的次数为（n+1）/2

发表于 2019-08-16 16:10:46 回复(0)

牛客556088594号

你这也没说顺序查找啊有序的话折半查找有点不太好算

发表于 2022-04-20 15:43:17 回复(0)

牛客986092316号

个人感觉没有正确答案，题目设定了元素一定在表中，所以当查到n-1个元素还没有找到时，第N次就没必要查找了，所以总的次数应该是 n（n+1）/2 -1

平均此时再除以2

发表于 2022-03-04 22:44:31 回复(0)

牛客946053006号

有没有可能，最快是查找1次，最慢是查找n-1次，但是n-1次分为第n-1次查到了该元素和没有查到该元素，因此，次数应该是1，2，3，4，...，n-2，n-1，n-1，平均次数为((1+n-1)*(n-1)/2+n-1)/n

发表于 2022-02-22 15:47:53 回复(0)

WannaLearning

解法 (1)：设X表示比较次数的随机变量；则X的样本空间包括{1,2,3,...,n};

由于待查找元素在序列中等可能性出现，即均匀分布。我们知每个事件是等可能性。

即满足 $\sum_{x=1}^{x=n}p\left(X=x\right)=1$ ,因此为每个事件发生的概率为1 / n。

故期望为 1 / n * (1 + 2 + .... + n)

解法 (2) : 详细写出每个事件等可能性的计算流程：

当查找一次就命中: $\frac{C_1^1}{{C_n}^1}$

当查找两次就命中: P(第一次不命中) * P(第二次命中|第一次不命中) = $\frac{C_{n-1}^1}{{C_n}^1}*\frac{C_1^1}{{C_{n-1-1+1}}^1}=\frac{C_1^1}{{C_n}^1}$

当查找三次就命中: P(前两次不命中) * P (第三次命中|前两次不命中)= $\frac{C_{n-1}^2}{{C_n}^2}*\frac{C_1^1}{{C_{n-1-2+1}}^1}=\frac{1}{n}$

..... 依次下去每个事件的概率都是 1 / n.

注释：(在 ${C_{n-1-1+1}}^1$ 中, n-1表示非正确元素的数目，n-1-1表示取走1个非正确元素后的剩余非正确元素数目，n-1-1+1表示加上1个正确元素）

发表于 2022-02-16 20:22:53 回复(0)

哄哄冲鸭！

（1+n）*n /2上式 * 1/n

发表于 2020-07-28 19:52:20 回复(0)

哦豁起飞？

需要查找的元素一定在表中，当倒数第二个元素也不是要找的，说明最后一个元素不需要比较就可以知道一定是需要查找的。这么说最坏情况是n-1 平均情况应该是((1+n)*n/2-1)/n 题目不严谨

发表于 2020-07-19 20:55:01 回复(0)

牛客818246740号

是最好的情况加最坏的情况。/2

发表于 2020-07-02 12:22:20 回复(0)

阳光脆薄如纸

程序进行到索引为n-1时还未找到，根据题意，我们是该直接返回索引n的值，还是再对n进行比较是否相等？我觉得应该是直接输出n的,所以这个题还有争议吧。

发表于 2020-03-23 11:37:03 回复(0)

Moomin201905061338823

最好情况下查找1次

最坏情况查找n次

发表于 2019-09-05 11:22:46 回复(0)

提交观点

问题信息

查找

上传者：赞花婆

难度：

14条回答 204收藏 7993浏览

在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表

问题信息

热门推荐

相关试题