题目
34.（4.0分）向一个有129个元素的顺序表[1]中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为____。
34.（4.0分）向一个有129个元素的顺序表[1]中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为____。
题目解答
答案
### 问题解析
题目要求在一个有129个元素的顺序表中插入一个新元素，并保持原来的顺序不变。我们需要计算平均需要移动的元素个数。
1. **顺序表的插入操作**：
- 在顺序表中插入一个新元素时，为了保持顺序不变，需要将插入位置及其之后的所有元素向后移动一个位置。
- 假设插入位置为 $ i $（从0开始计数），则需要移动 $ 129 - i $ 个元素。
2. **插入位置的可能情况**：
- 插入位置可以是0到129之间的任意一个位置，共有130种可能的情况。
- 每个位置插入的概率是相等的，即 $ \frac{1}{130} $。
3. **计算平均移动的元素个数**：
- 平均移动的元素个数可以通过求所有可能情况的移动次数的期望值来计算。
- 期望值 $ E $ 可以表示为：
\[
E = \sum_{i=0}^{129} \left( \frac{1}{130} \times (129 - i) \right)
\]
- 这个求和可以简化为：
\[
E = \frac{1}{130} \sum_{i=0}^{129} (129 - i)
\]
- 由于 $ \sum_{i=0}^{129} (129 - i) $ 实际上是等差数列的和，可以进一步简化为：
\[
\sum_{i=0}^{129} (129 - i) = \sum_{i=0}^{129} i = \frac{129 \times 130}{2}
\]
- 因此：
\[
E = \frac{1}{130} \times \frac{129 \times 130}{2} = \frac{129}{2} = 64.5
\]
### 答案
平均要移动的元素个数为 **64.5**。