若长度为n的线性表采用顺序存储结构,在等概率假设的情况下,删除一个数据元素,需要先依次移动【 】个数据元素。

admin2009-02-13  42

问题 若长度为n的线性表采用顺序存储结构,在等概率假设的情况下,删除一个数据元素,需要先依次移动【  】个数据元素。

选项

答案(n-1)/2

解析 令Edl(n)表示在长度为n的顺序表中进行一次删除操作时所需进行“移动”元素个数的期望值(即平均移动个数),则

   其中,qi是删除第i个元素的概率,n-i是删除第i个元素时所需移动元素的个数。同样假设在n个可能进行删除的位置i=1,2,…,n机会均等,则

   由此,在上述等概率的假设下,
转载请注明原文地址:https://kaotiyun.com/show/9b1p777K
0

最新回复(0)