已经有N个点了,再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动.
i的取值服从1到N+1的平均分布,即概率是1/(N+1).
求期望得N/2,即平均要移动N/2个结点
在N个结点的顺序表中插入一个结点,在等概率情况下,平均需要移动几个结点,为什么?
1个回答
相关问题
-
在循环双向链表中表头结点的左指针域指向（）结点,最后一个结点的右...
-
请问顺序表中插入结点时如平均移动次数为n/2,为什么说它的时间复杂程度O(n)而不是O(n/2)?
-
已知某树有2个2度结点,3个3度结点,4个4度结点,问有几个叶子结点?
-
设单链表L带头结点且非空,指针变量p指向L中的一个结点,且该结点既不是L中的第一个结点,也不是L中的最后一个结点,指针变
-
描述以下三个概念的区别：头指针、头结点、首结点,并说明在单链表中设置头结点的作用是什么?
-
3.一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,问它有几个度数为1的结点?
-
数据结构题目：在有n个叶子结点的完全二叉树中,最多有多少个结点?
-
在长度为N的顺序表仲,插入一个新元素平均需要移动表中_______个元素?删除一个元素平均需要移动_______个
-
已知带表头结点的单链表L,指针P指向L链表中的一个结点（非首、尾结点）：删除P结点的语句序列是?
-
数据结构问题：一棵完全二叉树有100个结点,度为一的结点有几个,叶子结点有几个?