现在假设对N个元素的链表做顺序查找时，若查找每个元素的概率相

[单选题]

现在假设对N个元素的链表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）？

```
(N+l)/2
```
```
N/2
```
```
N
```
```
[(1+N)*N]／2
```

查看正确选项

Supertan+

从表的一端开始，顺序扫描线性表，依次将扫描到的节点关键字和给定值k相比较。

等概率条件下...平均查找长度：ASL = (n+....+2+1)/n= (n+1)/2

发表于 2020-11-11 10:54:10 回复(0)

云之端201902272219279

我知道答案应该是（N + 1）/ 2，可我看A选项那不是个(N + l)/2吗，我还想哪来的l

发表于 2020-09-10 23:22:44 回复(1)

L201710091511469

第一个数的比较次数为1，第二个数的比较次数为2。。。以此类推第N个数的比较次数为N，所以总的比较次数为1+2+...+N=N(N+1)/2,平均比较次数为(N+1)/2,也即平均查找长度。

发表于 2019-12-19 17:26:33 回复(3)

阳光脆薄如纸

总长度n(n+1)/2除以总个数n

发表于 2019-11-28 15:57:51 回复(0)

pein531

第一个数的比较次数为1，概率为1/N；第二个数的比较次数为2，概率为1/N……以此类推第N个数的比较次数为N，概率为1/N。数学期望为：1/N*1 + 1/N*2 + ... 1/N*(N-1) + 1/N*N = 1/N*(1+2+...+N-1+N) = 1/N*(N+1)*N/2 = (N+1)/2

发表于 2020-10-21 15:09:53 回复(0)