题目
在长度为 n 的顺序表的第 i (1≤i≤n+1) 个位置上插入一个元素,元素的移动次数为 。A. n-i+1B. n-IC. iD. i-1
在长度为 n 的顺序表的第 i (1≤i≤n+1) 个位置上插入一个元素,元素的移动次数为 。
A. n-i+1
B. n-I
C. i
D. i-1
题目解答
答案
A. n-i+1
解析
考查要点:本题主要考查顺序表插入操作中元素移动次数的计算,需要理解顺序表的物理结构特点及插入操作的具体实现过程。
解题核心思路:
顺序表是基于数组实现的线性表,插入元素时需要将插入位置及之后的所有元素依次向后移动一位。移动次数取决于插入位置,具体为插入位置之后(含插入位置本身)的元素个数。
破题关键点:
- 插入位置
i的取值范围是1 ≤ i ≤ n+1(n为原表长度)。 - 插入位置
i之后的元素个数为n - i + 1(例如:插入位置为n+1时,无需移动元素)。
顺序表插入元素时,需将第 i 个位置及之后的所有元素依次后移一位。原表共有 n 个元素,插入后总长度变为 n+1。此时:
-
插入位置
i的含义:- 若
i = 1,需移动所有n个元素。 - 若
i = n+1,无需移动元素。 - 一般情况下,插入位置
i之后的元素个数为n - i + 1。
- 若
-
公式推导:
移动次数 = 插入位置之后的元素个数 =n - i + 1。
选项验证:
- 选项 A:当
i = 1时,移动次数为n - 1 + 1 = n(正确);当i = n+1时,移动次数为n - (n+1) + 1 = 0(正确)。 - 其余选项均无法同时满足上述边界条件。