第一问答网»论坛 › 中问网 › 问答 › 一道简单数据结构题

一道简单数据结构题

[复制链接]

11 |

1 | 2008-10-26 20:33:24 | 显示全部楼层 |阅读模式

对于表长为n的顺序表，在任何位置上插入和删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为？删除一个元素的需要移动的平均个数为？
希望给出分析过程，谢谢！

使用道具举报

千问 | 2008-10-26 20:33:24 | 显示全部楼层

插入的话：共有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 求平均时候，有高中时候求期望的思想琢磨琢磨明白了把...

使用道具举报

返回列表发新帖

千问

主题	0 回帖	4882万积分

论坛元老

Rank: 8 Rank: 8

积分: 48824836

回复楼主返回列表

问答

热门排行