04　数组、栈与队列

随机访问、插入删除、LIFO 与 FIFO

对应本节 16 道题。点击题目展开答案和理由，保留此前生成的详细解析。

第 01 题　数组与下标

有数组 data = [12, 7, 25, 3, 18]。请回答：

data[3] 是多少？
设数组起始位置为 base、每个元素占用空间为 w，写出第 i 个元素的位置表达式。
为什么按下标访问通常是 O(1)？

答案：data[3] = 3；元素位置为 base + i × w；按下标访问通常为 O(1)。

分解

下标从 0 开始：下标 0、1、2、3 分别对应 12、7、25、3。
基本模型中元素顺序存放；知道起点和单个元素的空间，就能直接计算第 i 个元素的位置。
定位目标不需要从头逐个检查，因此操作次数不随数组长度 n 增长。

易错点：下标 3 指第 4 个元素，不是第 3 个元素。

第 02 题　Python 的 list 与 array

scores = [12, 7, 25, 3, 18]
scores[2] = 100
print(scores)

写出打印结果。
list 能否保存不同类型的对象？
如果只保存同一种基础数值类型，原文介绍的标准库容器是什么？

答案：打印 [12, 7, 100, 3, 18]；list 可以保存不同类型的对象；同类型基础数值可用标准库的 array.array。

分解

scores[2] 指向原来的 25，赋值后该位置变为 100；列表长度和其他位置不变。
原文给出的混合类型示例是 [10, "hello", 3.14, True]，说明 list 比固定类型数组灵活。
from array import array 后，array("i", [...]) 是原文展示的同类型整数数组示例。

易错点：array.array 与常用的 list 不是同一个容器；原文后续示例主要用 list。

第 03 题　二维数组的访问与遍历

matrix = [[1, 2, 3],
          [4, 5, 6]]
print(matrix[1][2])

打印结果是什么？请分别说明两个下标的含义。
若矩阵有 n 行、n 列，完整遍历的时间复杂度是多少？

答案：打印 6；第一个下标 1 选第 2 行，第二个下标 2 选该行第 3 个元素；n × n 矩阵完整遍历为 O(n²)。

分解

matrix[1] 得到 [4, 5, 6]，再取它的 [2] 得到 6。若有 n 行，每行 n 个元素，两层遍历共访问 n × n = n² 个位置。

易错点：两层下标分别选行和行内位置；两层完整遍历不能算作 O(n)。

第 04 题　基本操作复杂度

以 Python list 为例，填写每项操作的典型时间复杂度。涉及追加或末尾删除时，请注明是否为“摊销”。

操作	复杂度
按下标读取 `data[k]`
`len(data)`
末尾 `append(x)`
中间 `insert(k, x)`
末尾 `pop()`
开头 `pop(0)`

再任选一项 O(n) 操作，说明它为什么可能随列表长度增长而变慢。

操作	答案	原因
`data[k]`	`O(1)`	可直接定位。
`len(data)`	`O(1)`	列表保存了长度信息。
末尾 `append(x)`	摊销 `O(1)`	预留空间；偶尔扩容。
中间 `insert(k, x)`	`O(n)`	后面的元素可能要后移。
末尾 `pop()`	摊销 `O(1)`	只删除最后一个元素。
开头 `pop(0)`	`O(n)`	其余元素要前移。

分解

任选 insert(k, x) 或 pop(0) 作解释即可：当列表很长且操作位置靠近开头时，可能有接近 n 个元素需要移动，所以成本随 n 增长。

易错点：append 的结论是“摊销 O(1)”，并非每一次追加都保证常数成本。

第 05 题　在中间插入

numbers = [12, 7, 25, 3, 18]
numbers.insert(2, 99)

执行后 numbers 是什么？原列表中哪些元素需要后移？
如果手动逐个后移，为什么要从后往前移动？
在列表开头附近插入的最坏时间复杂度是多少？

答案：[12, 7, 99, 25, 3, 18]；原来的 25、3、18 后移；手动移动应从后往前；最坏 O(n)。

分解

新元素进入下标 2，原下标 2～4 的三个元素分别移到下标 3～5。
若从前往后赋值，先把 25 写到原来存 3 的位置，会覆盖尚未搬走的 3；从后向前可避免覆盖。
在开头附近插入时，需要移动的元素数量随列表长度增长，最坏为 O(n)。

易错点：insert 语法很短，不代表底层没有元素移动。

第 06 题　删除元素与保持顺序

下面两段操作分别从原始列表 [12, 7, 25, 3, 18] 开始，互不影响。

执行 removed = numbers.pop(2)：removed 和剩余列表分别是什么？为保持顺序，哪些元素要前移？
若删除下标 1 的元素，并允许用最后一个元素覆盖它，删除后的列表是什么？
比较这两种删除方式的时间复杂度及顺序变化。

答案：有序删除下标 2：返回 25，得到 [12, 7, 3, 18]，3、18 前移，最坏 O(n)。无序删除下标 1：返回 7，得到 [12, 18, 25, 3]，可为 O(1)，但顺序改变。

分解

pop(2) 删除的是下标 2 的 25；要让列表连续，右侧的 3、18 向左补位。
允许打乱顺序时，先把末尾的 18 放到下标 1，再删掉末尾的旧 18；无需移动中间的整段元素。
第一种做法的移动量可能随 n 增长；第二种只改一个位置并删末尾，按原文为 O(1)。

易错点：两小题都从原始列表开始；无序删除能否使用，取决于程序是否要求保持元素顺序。

第 07 题　线性搜索

使用原文的 linear_search(data, target)：从左到右检查，找到就返回下标，否则返回 -1。

linear_search([12, 7, 25, 3, 18], 25) 返回什么？
将目标改为 99，返回什么？
分别说明最好情况和最坏情况的时间复杂度。

答案：搜索 25 返回 2；搜索 99 返回 -1；最好 O(1)，最坏 O(n)。

分解

算法依次比较下标 0、1、2……的元素。25 出现在下标 2；99 不存在，检查完整个列表才返回 -1。如果第一个元素就匹配，只检查一次；如果目标在最后或不存在，最多要检查全部 n 个元素。

易错点：返回的是下标，不是“第几个”；找不到时原文函数返回 -1。

第 08 题　二分搜索的过程

在有序列表 [1, 4, 7, 12, 18, 25, 31, 40] 中搜索 25。使用原文算法，初始 left = 0、right = 7，每次取 middle = (left + right) // 2。

依次访问哪些 middle 下标及其值？最终返回什么？
使用二分搜索需要满足哪两个前提？时间复杂度是多少？

答案：先访问下标 3 的 12，再访问下标 5 的 25；返回 5。前提是数据有序且能快速访问中间位置；复杂度 O(log n)。

分解

初始 left=0、right=7，所以 middle=(0+7)//2=3。data[3]=12<25，舍去下标 0～3，改为 left=4。
此时 middle=(4+7)//2=5，data[5]=25，返回 5。
每轮把待查范围缩小约一半，因此是 O(log n)。

易错点：不能直接把这套二分判断用于无序列表；也需要能迅速读取中间元素。

第 09 题　动态数组与扩容

按原文的“容量按倍数增长”示意模型：一个动态数组当前有 8 个元素，容量也为 8，此时再追加一个元素。

预留空间用完后，扩容通常需要做什么？这一次操作为什么可能是 O(n)？
若持续追加 n 个元素，总成本和平均每次追加的摊销复杂度分别是什么？

答案：空间用完时申请更大的空间，并复制旧元素；这次可能复制 O(n) 个元素。若容量按倍数增长，连续追加 n 个元素的总成本为 O(n)，平均每次追加的摊销成本为 O(1)。

分解

当前 8 个槽位都已使用，再追加就需要扩容。在题设的倍增模型里，可把容量从 8 增到 16，并搬动原有 8 个元素。这样的昂贵操作并非每次追加都会发生；扩容后有新的预留空间，所以把一长串追加的总成本平均到每次，仍接近常数。

易错点：8 → 16 是题设与原文的示意模型，不是对 Python list 真实容量数值的保证；“单次最坏”与“摊销”要分开说。

第 10 题　综合应用：有序列表

列表 data = [1, 4, 7, 12, 18, 25, 31, 40] 始终保持升序。

用二分搜索查找 18，返回哪个下标？搜索的时间复杂度是多少？
将 10 插入合适位置后，列表是什么？原列表中哪些元素要后移？插入的最坏复杂度是多少？
为什么“搜索快”不能直接推出“维护这个有序列表的所有操作都快”？

答案：18 的下标是 4，二分搜索 O(log n)；插入 10 后为 [1, 4, 7, 10, 12, 18, 25, 31, 40]，12、18、25、31、40 后移，插入最坏 O(n)。

分解

列表升序且可按下标访问，满足二分搜索的两个前提；18 原本位于下标 4。
要保持升序，10 应放在 7 与 12 之间，即下标 3。原下标 3～7 的五个元素都要向右挪一位。
二分搜索减少的是查找比较次数；插入仍要为新元素腾出位置。因此查找可以是 O(log n)，维护顺序的插入仍可能是 O(n)。

重复外层列表不会创建独立行；二维数组需要关注别名。