设A是一个线性表(a1...an)，采用顺序存储结构，在等概率的情况下，平均每插入一个元素需要移动多少元素呢？若插在ai和ai+1之间的概率为2*(n-i)/n*(n+1)，则平均每插入一个元素所要移动的元素个数又是多少呢？

表长为N的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个移动元素的平均个数是多少？删除一个呢？

请写出详细步骤，谢谢。

这个在一般的数据结构的书上都会有讲解吧，比如，严蔚敏的
LZ可以仔细学习一下。

用概率里的求数学期望的方法吧，

如果一个线性表有n个元素，

平均的移动次数是：p0*n+p1*(n-1)+p2*(n-2)+...+pn*0

从0-n到一共n+1个插入位置，pi是第i个位置的插入概率，你可以把你的概率函数带入到这个式子去求和就可以了...

ps:如果是等概率的情况实质就是一个古典概型的问题，即p0=p1=...=pn=1/(n+1),求和计算就更简单了

[[it] 本帖最后由 geninsf009 于 2008-9-25 09:26 编辑 [/it]]

插在0位置则要移动全部的N-1个数，以此类推，将总数加起来（就是等差数列）除总的数的个数（N）