Question

给定一个有n个元素的线性表。若采用顺序存储结构，则在等概率前提下，向其插入一个元素需要移动的元

给定一个有n个元素的线性表。若采用顺序存储结构，则在等概率前提下，向其插入一个元素需要移动的元素个数平均为____。
(5)A．n+l B．n/2 C．(n+l)/2 D.n

怎么算的？？？？？急急急
答案是B 我不明白怎么算出来的

Answer 1

楼主你好！
很高兴为你答题！
n个元素是吧，首先你要明白有n+1个位置可以插入，这个你可以理解吗？所以每个位置被插入入的概率为p=1/n+1，如果插入第一个位置需要移动n次，概率为pxn，插入第二个位置需要移动n-1次，概率为px(n-1)，以此类推，当插入第n+1个位置时，就不需要移动任何元素，我们可以得到这样的通项公式，当插入第i个位置（1<=i<=n+1）时候，需要移动的次数为n+1-i，概率为px（n+1-i），
所以平均的概率(一共n+1项)为 pxn+px(n-1)+······+px1+px0=px(n+0)x(n+1)x1/2=n/2
（p=1/n+1，这个是求前n项和公式，高中应该学过的！），所以选择B
不知道这样说你理解不？
希望我的回答对你有帮助！望采纳！

Answer 2

循序结构，概率相等，有n个元素，那么插入的位置为n+1,所以概率p=1/(n+1)，如果插入第一个位置则需要移动n次，插入到第i位置，则移动（n-i+1）（例如：n=10，i=3,则需要移动[3,10]这个区间的所有的数，一共是10-3+1个），移动次数的数学期望E=p*n+P*(n-1)+...+p*0=p*[n+(n-1)+...+0]=p*[n(n+1)/2]，所以E=[1/(n+1)]*[n(n+1/2)]=n/2

Answer 3

方法一：期望值是插在中间位置，一半要移，故n/2

方法二：最多移n个，最少移0个，等差数列，故平均1/2（n+0）=n/2