题目
对于长度为n的线性表（即n个元素构成的序列），若采用顺序存储结构（数组存储），则在等概率下，删除一个元素平均需要移动的元素数为（ ）。 A.nB.（n-1）/2C. N/2D.Log n
对于长度为n的线性表（即n个元素构成的序列），若采用顺序存储结构（数组存储），则在等概率下，删除一个元素平均需要移动的元素数为（ ）。 A.nB.（n-1）/2C. N/2D.Log n
题目解答
答案
B
解析
步骤 1：理解线性表的顺序存储结构
线性表的顺序存储结构是指将线性表的元素按照顺序存储在一段连续的内存空间中，每个元素占用相同的存储空间。这种存储方式使得元素的访问非常高效，但插入和删除操作需要移动元素。
步骤 2：分析删除操作
在顺序存储结构中，删除一个元素需要将该元素之后的所有元素向前移动一个位置，以填补被删除元素的位置。如果删除的是第i个元素（从1开始计数），则需要移动n-i个元素。
步骤 3：计算平均移动的元素数
在等概率下，每个元素被删除的概率相同，即每个元素被删除的概率为1/n。因此，删除第i个元素时，平均需要移动的元素数为(n-i)/n。将所有可能的删除操作的移动元素数求和，再除以n，得到平均移动的元素数。
\[ \text{平均移动的元素数} = \frac{1}{n} \sum_{i=1}^{n} (n-i) = \frac{1}{n} \sum_{i=1}^{n} (n-i) = \frac{1}{n} \left( \sum_{i=1}^{n} n - \sum_{i=1}^{n} i \right) = \frac{1}{n} \left( n^2 - \frac{n(n+1)}{2} \right) = \frac{1}{n} \left( \frac{2n^2 - n^2 - n}{2} \right) = \frac{1}{n} \left( \frac{n^2 - n}{2} \right) = \frac{n-1}{2} \]
线性表的顺序存储结构是指将线性表的元素按照顺序存储在一段连续的内存空间中，每个元素占用相同的存储空间。这种存储方式使得元素的访问非常高效，但插入和删除操作需要移动元素。
步骤 2：分析删除操作
在顺序存储结构中，删除一个元素需要将该元素之后的所有元素向前移动一个位置，以填补被删除元素的位置。如果删除的是第i个元素（从1开始计数），则需要移动n-i个元素。
步骤 3：计算平均移动的元素数
在等概率下，每个元素被删除的概率相同，即每个元素被删除的概率为1/n。因此，删除第i个元素时，平均需要移动的元素数为(n-i)/n。将所有可能的删除操作的移动元素数求和，再除以n，得到平均移动的元素数。
\[ \text{平均移动的元素数} = \frac{1}{n} \sum_{i=1}^{n} (n-i) = \frac{1}{n} \sum_{i=1}^{n} (n-i) = \frac{1}{n} \left( \sum_{i=1}^{n} n - \sum_{i=1}^{n} i \right) = \frac{1}{n} \left( n^2 - \frac{n(n+1)}{2} \right) = \frac{1}{n} \left( \frac{2n^2 - n^2 - n}{2} \right) = \frac{1}{n} \left( \frac{n^2 - n}{2} \right) = \frac{n-1}{2} \]