在n个结点的顺序表中插入一个结点需平均移动几个结点

Question

如题所述

Answer 1

已经有N个点了，再加一个就是N+1个。假设新加的结点插在第i位，那么后面N+1-i个结点都要往后移动。

期望有计算公式，这里等于(N+1-1)*1/(N+1)+(N+1-2)*1/(N+1)+(N+1-3)*1/(N+1)+...+(N+1-N-1)*1/(N+1)=N/2。

i的取值服从1到N+1的平均分布，即概率是1/(N+1)。

扩展资料：

包括一个数据元素及若干个指向其它子树的分支；例如，A，B，C，D等。在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。

在C语言中，链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址，即指针域和数据域。

数据结构中的每一个数据结点对应于一个储存单元，这种储存单元称为储存结点，也可简称结点。

参考资料来源：百度百科-结点

Answer 2

讲期望未必麻烦了一点。
通俗的来说：有n个结点，即有n+1个位置可以插入。插在最后空位，需要移动的次数为0；插在第一个，需要移动的次数为n，等差数列求和，得到一共可能移动的总次数为(n*(n+1))/2。再除以n+1个位置，则平均需要移动的点为n/2。本回答被网友采纳

Answer 3

插入到第一个节点前面是n次，插入到第一个节点后面是n-1次。。。插入到最后一个节点后面是0次故（n+0）*n/2

Answer 4

是n/2，具体移动的元素个数与表长和该元素 在表中的位置有关。

Answer 5

最少0, 最大n , 线性, 所以平均是 (0+n)/2 = n/2本回答被网友采纳