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

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

2025-02-24 13:41:49

推荐回答（2个）

回答1：

添加到第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

回答2：

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