Question

在长度为N的顺序表仲,插入一个新元素平均需要移动表中_______个元素?删除一个元素平均需要移动_______个

Answer 1

插入时,n/2；插入末尾,移动0个元素,插入表首移n个元素.平均就是n/2,(0+1+2……+n)/(n+1),因为有n+1个位置可供插入.删除时,最少0个,最多n-1个,结果是(0+1+2+……n-1)/n,因为有n个元素!