2.2 选择题讲评：移动次数、访问成本与边界条件

顺序表题常把“操作本身”“定位位置”“扩容”混算。先固定题设：长度 $n$、容量是否足够、位序是否已知、元素是否有序，再计算。

单选 1：长度 $n$ 的顺序表在第 $i$ 位插入，容量足够，移动次数为多少？答案 $n-i+1$。原第 $i$ 到第 $n$ 个都要让位。若 $i=n+1$，结果为 0，正好是尾插。

单选 2：删除第 $i$ 个元素移动多少次？答案 $n-i$。删除表尾 $i=n$ 时无需移动。插入与删除公式差 1，是因为插入前有 $n$ 个元素，删除后只需搬原第 $i+1$ 至第 $n$ 个。

多选：关于顺序表，正确的是：A 按位访问 $O(1)$；B 按值查找一定 $O(\log n)$；C 中间插入最坏 $O(n)$；D 动态扩容后首地址一定不变。答案 A、C。B 需要有序等前提，D 与重新分配相冲突。

计算题：合法插入位序等概率时，平均移动量为
$$\frac{1}{n+1}\sum _{i=1}^{n+1}(n-i+1)=\frac{n}{2}.$$
合法删除位序等概率时为
$$\frac{1}{n}\sum _{i=1}^n(n-i)=\frac{n-1}{2}.$$
若题目给出各位置不同概率，必须按加权期望算，不能套等概率公式。

错解反馈：把数组下标当位序会造成所有边界差一；见“查找”就选 $O(1)$，忽略按位与按值的区别；只凭平均复杂度否认尾插常数成本，混淆个例、平均和最坏。

迁移题：长度 10 的表，在第 4 位插入后再删除第 7 位，两次各移动多少？答案插入移动 $10-4+1=7$ 次，新长度 11；删除移动 $11-7=4$ 次。验收要求写出每个公式使用时的表长。