题目

对于一个具有20个元素的顺序表[1]执行插入操作，则其结点[2]的移动次数最好情况下是（）次，最坏情况下是（）次，平均情况是（）次。

对于一个具有20个元素的顺序表[1]执行插入操作，则其结点[2]的移动次数最好情况下是（）次，最坏情况下是（）次，平均情况是（）次。

题目解答

答案

对于一个具有20个元素的顺序表，插入操作需要将插入位置及其之后的所有元素后移。

  1. 最好情况：当插入位置为表尾（即第21个位置）时，无需移动任何元素，移动次数为0次。
  2. 最坏情况：当插入位置为表头（即第1个位置）时，需要将所有20个元素后移，移动次数为20次。
  3. 平均情况：假设插入位置是等概率的（1到21），则平均移动次数为：
    $\frac{0 + 1 + 2 + \cdots + 20}{21} = \frac{\frac{20 \times 21}{2}}{21} = 10$
    因此，平均移动次数为10次。

答案：
第1空：0次
第2空：20次
第3空：10次

解析

顺序表插入操作的结点移动次数主要取决于插入位置的选择：

  • 最好情况：当插入位置为表尾时，无需移动任何元素，移动次数为0次。
  • 最坏情况：当插入位置为表头时，需要移动所有20个元素，移动次数为20次。
  • 平均情况：假设插入位置等概率分布在1到21个位置，则平均移动次数为总移动次数的平均值。

最好情况

插入位置为第21个位置（表尾），此时无需移动任何元素，移动次数为：
$0 \text{次}$

最坏情况

插入位置为第1个位置（表头），此时需要将所有20个元素后移，移动次数为：
$20 \text{次}$

平均情况

插入位置共有21种可能（1到21），总移动次数为：
$0 + 1 + 2 + \cdots + 20 = \frac{20 \times 21}{2} = 210$
平均移动次数为：
$\frac{210}{21} = 10 \text{次}$