在N个结点的顺序表中插入一个结点,在等概率情况下,平均需要移动几个结点,为什么?

在N个结点的顺序表中插入一个结点,在等概率情况下,平均需要移动几个结点,为什么?
在N个结点的顺序表中插入一个结点,在等概率情况下,平均需要移动几个结点,为什么?

在N个结点的顺序表中插入一个结点,在等概率情况下,平均需要移动几个结点,为什么?
已经有N个点了,再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动.
i的取值服从1到N+1的平均分布,即概率是1/(N+1).
求期望得N/2,即平均要移动N/2个结点