04　数组、栈与队列

数组与下标

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

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

Python 的 list 与 array

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

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

二维数组的访问与遍历

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

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

基本操作复杂度

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

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

在中间插入

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

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

删除元素与保持顺序

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

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

线性搜索

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

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

二分搜索的过程

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

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

动态数组与扩容

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

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

综合应用：有序列表

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

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

补充练习

栈依次 push(10)、push(20)、push(30)、pop()、pop()，返回值与剩余内容是什么？

补充练习

为什么 list.append()/末尾 pop() 比 pop(0) 更适合列表栈？

补充练习

deque 中队列入队和出队可分别用什么操作？

补充练习

容量 4 的环形队列初始 front=rear=size=0，入队 10,20,30，出队一次，再入队 40,50，最终指针及逻辑内容？

补充练习

front==rear 能独立判断带 size 的环形队列为空吗？

补充练习

matrix=[[0]3]2 后 matrix[0][0]=9，会影响另一行吗？如何避免？