长度为N的顺序表在任何位置上(添加)删除一个元素的概率相等,（添加）一个元素时平均移动多少个元素

如题所述

推荐答案 2012-12-12

添加到第1个，移动N个；
添加到第2个，移动(N-1)个；
……
添加到第N个，移动1个；
添加到第(N+1)个，移动0个

平均：(0+1+2+……+N)/(N+1)=N/2

删除第1个，移动(N-1)个；
删除第2个，移动(N-2)个；
……
删除第N个，移动0个

平均：[0+1+……+(N-1)]/N=(N-1)/2

温馨提示：答案为网友推荐，仅供参考

当前网址：http://44.wendadaohang.com/zd/3ZDKGKKRZ.html

其他回答

第1个回答 2012-12-12

添加：[N+(N-1)+(N-2)+...+1+0]/（N+1）=N/2 添加有N+1种位置情况
删除：[(N-1)+(N-2)+...+1+0]/N=(N-1)/2 删除只有N种位置情况

相似回答

顺序表中插入和删除需要的平均移动次数,怎么算啊?请求大神们回答。求...答：我们假设顺序表长度为n，由于顺序表的结点之间逻辑关系为邻接关系，所以当我们要将一个结点插入时，这个插入位置的后面的结点每一个都要移动以给新插入的结点让出位置，同时顺序表的长度加一，所以顺序表插入一个结点，平均需要移动n/2个结点，由于移动了n/2个结点我们插入一个结点的移动次数就是n/2。...

在长度为N的顺序表仲,插入一个新元素平均需要移动表中___个元素?删除...答：插入时，n/2；插入末尾，移动0个元素，插入表首移n个元素。平均就是n/2,，(0+1+2……+n)/(n+1)，因为有n+1个位置可供插入。删除时,最少0个，最多n-1个，结果是(0+1+2+……n-1)/n,因为有n个元素！

在顺序表中插入和删除一个元素,平均需要移动多少个元素答：……添加到第N个,移动1个；添加到第(N+1)个,移动0个平均：(0+1+2+……+N)/(N+1)=N/2 删除第1个,移动(N-1)个；删除第2个,移动(N-2)个；……删除第N个,移动0个平均：[0+1+……+(N-1)]/N=(N-1)/2

在一个长度为n的顺序表中答：已知顺序表（a1,a2,...,an)1.在第i（i=1...n+1)个元素之前插入一个元素的概率pi为1/(n+1),故在长度为n的插入一个元素时所许移动元素次数的期望为：Ei=∑pi(n-i+1) ,i=1...n+1 所以 Ei=n/2 2.删除第i（i=1...n)个元素的概率pi为1/n,故在长度为n的删除一个元...

大家正在搜

在一个长度为n的顺序表的任一位置在长度为n的顺序表的第i个位置上向一个有128个元素的顺序表在长度为a的线段上任取两点M和N 对于顺序存储的长度为N 如果两个序列的长度分别为N和链表和顺序表的一些区别散列表的平均查找长度链表相对于顺序表的优点