刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

单选题

对于长度为n的线性表(即n个元素构成的序列),若采用顺序存储结构(数组存储),则在等概率下,删除一个元素平均需要移动的元素数为( )。

A
n
B
(n-1)/2
C
N/2
D
Log n
使用微信搜索喵呜刷题,轻松应对考试!

答案:

B

解析:

对于长度为n的线性表,采用顺序存储结构时,删除一个元素需要移动的元素数取决于要删除的元素的位置。删除第一个元素时需要移动n-1个元素,删除最后一个元素时不需要移动任何元素。由于等概率下删除任何一个元素的概率是相同的,所以平均需要移动的元素数可以通过计算期望来得出。期望的公式为Edelete = Σ(i=1 to n) (i-1)*qi,其中qi是删除第i个元素的概率。由于等概率删除,所以qi=1/n,带入公式计算得到Edelete = (n-1)/2。因此,删除一个元素平均需要移动的元素数为(n-1)/2,选项B正确。

创作类型:
原创

本文链接:对于长度为n的线性表(即n个元素构成的序列),若采用顺序存储结构(数组存储),则在等概率下,删除一个

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share