对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为()。
- A.n/2
- B.(n+1)/2
- C.(n-1)/2
- D.n/4
正确答案及解析
正确答案
B
解析
所有元素的搜索长度之和为1+2+…+n=n(n+1)/2。搜索每个元素的概率都是1/n，所以平均搜索长度为：n(n+1)，2×(1/n)=(n+1)/2。
对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为()。
所有元素的搜索长度之和为1+2+…+n=n(n+1)/2。搜索每个元素的概率都是1/n，所以平均搜索长度为：n(n+1)，2×(1/n)=(n+1)/2。
