一道简单数据结构题

来源：百度知道 编辑：UC知道 时间：2024/05/15 06:05:07
对于表长为n的顺序表，在任何位置上插入和删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为？删除一个元素的需要移动的平均个数为？
希望给出分析过程，谢谢！

插入的话：
共有n+1个插入位置，每个概率是1/（n+1）
在最开始插入要移动n个
在末尾插入要移动0个
平均移动元素为：(1/(n+1))*[n+(n-1)+…+1+0]=n/2

删除的话：
共有n个删除位置
删除第一个要移动n-1
删除最后一个要移动0个
平均移动：（1/n）*[(n-1)+…+1]=(n-1)/2

求平均时候，有高中时候求期望的思想
琢磨琢磨 明白了把