对长度为n的有序单链表,若搜索每个元素的概率相等,则顺序搜索到表中任一元素的平均

题库2022-08-02  29

问题 对长度为n的有序单链表,若搜索每个元素的概率相等,则顺序搜索到表中任一元素的平均搜索长度为()。A.n/2B.(n+1)/2C.(n-1)/2D.n/4

选项 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。
转载请注明原文地址:https://tihaiku.com/gongwuyuan/2554995.html

最新回复(0)