在表长为n的顺序表中,当在任何位置删除一个元素的概率相同时,删除一个元素所需移动的平均个数为( )。
A. (n-1)/2 B. n/2 C. (n+1)/2 D. n
这种题目理解后很简单写的:
当删除第1个节点时候,剩下2~n这些n-1个节点都需要向前移动,所以次数是n-1;
删除第2个节点,除了第1个节点外剩下3~n这n-2(这个数是这么算的n-3+1,其他的同理)个节点都需要向前移动,所以次数是n-2;
依此类推......
当删除第n个节点时,由于它是最后一个节点了,所以不需要移动,那么次数是0;
需要算删除一个节点的平均移动个数,那么将删除每个节点所需要的移动个数相加,在除以n(总节点数)即可得到答案(类似于你每天学习x个小时,然后算一段时间的内每天平均学习多久一样)。
那么我们先算总数sum,这里需要用到高中的等差数列求和的知识(会用到很多,一定要会)
sum = 0 + 1 + ... + n-1
这里公差为1,首项0,末项n-1,项数n(0~n-1,相对于1~n,就是n个,懂了之后可以直接n-1+1,这种加上1的形式在计算机领域里面用的很多,因为下标一般是从0开始的),一个公式Sn = [项数 / 2] * (首项 + 末项) = n / 2 * (0 + n - 1)
所以sum = n * ( n - 1 ) / 2
即平均数ave = sum / n = (n - 1) / 2 ----->选A
看懂了嘛,希望对你有所帮助,加油嗷~~~
第一个元素被删除,有n-1个元素移动,最后一个元素被删除,没有元素需要移动,同理可得 平均为(n-1)/2
[(n-1+0)*(n-1-0+1)/2]*1/n
MSjJustin 回复 MSjJustin: 首删:n-1个移动;末删:0个移动;平均:n-1/2 首插:n个移动; 末插:0个移动; 平均:n/2
n(n-1)/2✘1/n
A
用户登录可进行刷题及查看答案
登录后提交答案