假设顺序表的长度为n,则在第i(1<=i<=n+1)个元素之前插入一个新元素x所需移动元素的个数为( )。

假设顺序表的长度为n,则在第i(1<=i<=n+1)个元素之前插入一个新元素x所需移动元素的个数为( )。


【正确答案】:N-I+1
【题目解析】:

插入算法的基本步骤是:首先将结点ai~an依次向后移动一个元素的位置,这样空出第i个数据元素的位置;然后将x置入该空位,最后表长加1。由顺序表的存储特点可知,元素的移动只能按an,an-1,…,ai的次序进行,即按从右到左的次序先将an右移一位,再将an-1右移一位到an原来的位置上,依次类推,直到将ai右移到ai+1原来的位置上。故需移动n-i+1个元素。



Top