二、线性表（第 9-18 题）
9. 线性表采用顺序存储，若第一个元素的存储地址是100，每个元素的长度为3，则第5个元素的存储地址是( )
标签：【互联网/国企笔试超高频】
A. 110 B. 118 C. 114 D. 112
答案：D
【结论】 按地址公式计算得 LOC(a₅) = 100 + (5−1) × 3 = 112，选 D。
【推导过程】 顺序表连续存储，任意元素的地址可直接算出
LOC(aᵢ) = LOC(a₁) + (i − 1) × L
代入:LOC(a₅) = 100 + (5 − 1) × 3 = 100 + 12 = 112【逐项辨析】
- A 110：偏移量算成了 10，元素长度用错。
- D 112：正确。 偏移量是 (i−1) 个元素，每个 3 字节，共 12 字节。
- C 114：凑数干扰项，不对应任何固定错法（若真按 i × L = 5 × 3 = 15 会得到 115，选项里并没有 115）。别硬凑错因，直接用「偏移量是 (i−1) 个元素」把它排除。
- B 118：重复累加或误用 (i+1) × L。
【知识点】 顺序存储的两个核心公式（必背）：
| 公式 | 表达式 | 说明 |
|---|---|---|
| 地址公式 | LOC(aᵢ) = LOC(a₁) + (i−1) × L | L 为单个元素长度 |
| 偏移量 | 元素 aᵢ 的偏移 = (i−1) × L | 从首地址起算 |
由此得到顺序表最重要的特性 —— 随机访问：知道首地址、下标、元素长度，就能 O(1) 直接算出任意元素地址，无需从头遍历。这正是“数组按下标访问是 O(1)”的底层原因。
【记忆锚点】 “首地址加偏移，偏移是 (i−1) 个格子”——关键是 i−1 而不是 i。
【易混对比】 与链表对照：顺序表求第 i 个元素地址是 O(1)；链表求第 i 个结点必须从头走 i−1 步，是 O(n)。“顺序表靠算，链表靠走” 是两者最本质的分野（见第 12 题）。
【自测】 若首地址为 200、元素长度为 4，则 a₁₀ 的地址是多少？
答：200 + (10−1) × 4 = 236。与第 12 题（链表访问第 i 个元素 O(n))对照记忆。
【知识关联】
- 同库连考：与第 12 题（链表访问 O(n))对照 —— 「顺序表靠算，链表靠走」；与第 75 题（完全二叉树顺序存储下标）同属「数组下标公式」。
- 工程实现:Java
ArrayList.elementData[i]本质就是base + i * scale;JVM 里array[i]的机器码就是「基址 + 下标×元素宽度」。理解本题才能理解为何数组访问是 O(1)。 - 408 / 国企真题：国网、银行科技岗「地址计算」填空/选择原题；408 线性表章节必背公式。
- 面试追问:①「多维数组 a[3][4] 按行优先，a[2][1] 偏移多少？」（2×4+1=9 个元素）；②「为什么链表不能 O(1) 求第 i 个？」（结点不连续，无公式）。
【拓展延伸】
变式问法:
- 首地址 1000，元素占 4 字节，求第 100 个：1000+(100−1)×4 = 1396。
- 已知 LOC(a₁)=200, LOC(a₅)=212，求 L:212=200+(5−1)L → L=3。
- 二维数组 A[0..5][0..6] 按行存（每行 7 个元素），每个 int 4 字节，A[0][0]=100，则 A[3][4]=100+(3×7+4)×4=100+25×4=200（偏移 3×7+4=25 个元素，×4B=100B；100+100=200，不是 204）。
完整验算:
LOC(aᵢ) = LOC(a₁) + (i−1)×L
本题:100 + (5−1)×3 = 100+12 = 112 ✓
反查:若误用 i×L → 100+15=115(选项无,故排除该错法)工程应用：文件系统簇号、数据库页偏移、GPU 纹理寻址都是同一公式；理解 (i−1) 而非 i，是 off-by-one 事故的根源。
10. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( )存储方式最节省时间。
标签：【互联网/国企笔试高频】
A. 顺序表 B. 单链表 C. 双链表 D. 单循环链表
答案：A
【结论】 频繁随机存取 + 尾部插删，顺序表最省时间，选 A。
【逐项辨析】
- A 顺序表：正确。 按序号存取是 O(1) 随机访问；在表尾插入 / 删除只改 length，不移动任何元素，也是 O(1)。
- B 单链表：按序号访问必须从头遍历，为 O(n)；虽有尾指针时尾部插入为 O(1)，但“随机存取”这一条完全不满足。
- C 双链表：双向指针只解决“找前驱”问题，按序号访问仍是 O(n)。
- D 单循环链表：循环只让尾结点能找到头结点，按序号访问依旧 O(n)。
【知识点】 选择存储结构的方法 —— 先看哪种操作最频繁:
| 主要操作 | 最优存储结构 | 时间复杂度 |
|---|---|---|
| 按序号随机存取 | 顺序表 | O(1) |
| 尾部插入 / 删除 | 顺序表（带尾指针的链表也可） | O(1) |
| 任意位置插入 / 删除 | 链表 | O(1)（已知位置） |
| 求表长 | 顺序表（直接读 length） | O(1) |
本题两种主要操作（随机存取、尾部插删）都是顺序表的强项，故顺序表最优。
【记忆锚点】 “随机访问为主 → 顺序表；频繁任意插删 → 链表”。
【易混对比】 注意与第 11 题区分：第 11 题问“任意位置插入删除效率最高”，答案是链表；本题问“随机存取 + 尾部插删”，答案是顺序表。同一组选项，题干场景不同，答案相反 —— 这类题必须逐字读题。
【自测】 若某线性表最常用的操作是在任意位置插入和删除元素，应选用哪种存储结构？
答：链表。任意位置插删只需改指针，顺序表则要移动大量元素。与第 11 题连考。
【知识关联】
- 同库连考：与第 11 题（任意位置插删→链表）是「同一组选项、场景相反」的经典对题；与第 13 题(ArrayList vs LinkedList)同一考点的 Java 版。
- 工程实现:Java
ArrayList尾部add均摊 O(1)（容量不足时 1.5 倍扩容复制）；get(i)O(1)。这正是本题场景的工业标准答案。 - 408 / 国企真题：国网「线性表」选型题高频；408 考过「操作集决定存储结构」。
- 面试追问:①「尾部频繁 add 为什么还可能变慢？」（扩容复制均摊 O(1)，单次最坏 O(n));②「何时该用 LinkedList？」（大量头插/已有迭代器位置插删）。
【拓展延伸】
变式：若「头部插删 + 不需要随机访问」→ 链表（或 ArrayDeque 头部也高效）；若「随机访问 + 中间插删频繁」→ 仍是 ArrayList 但可考虑「批量 + 索引结构」，单纯换 LinkedList 通常更慢。
工程应用:StringBuilder 底层是顺序表；消息队列的环形缓冲区是顺序表+循环下标；LRU 用哈希+双向链表正是因为要 O(1) 删中间结点。
11. 在线性表中进行插入和删除操作时，效率最高的存储结构是( )
标签：【互联网/国企笔试高频】
A. 顺序表 B. 链表 C. 队列 D. 栈
答案：B
【知识点】 插入/删除的代价对比与前提（设元素个数 n）：
| 结构 | 插入/删除代价 | 是否移动元素 | 前提 |
|---|---|---|---|
| 顺序表 | 平均移动 n/2（插）、(n−1)/2（删） | 需要 | — |
| 链表 | 改 2~3 个指针 | 不需要 | 已定位到目标结点或前驱 |
链表「O(1) 插删」的隐藏前提是位置已知。若只知序号 i，还要先 O(n) 定位，总代价仍是 O(n)。顺序表则无论是否知道位置，插入删除都要搬元素（除非在表尾）。另注意：队列、栈是操作受限的线性表，只能在端点插删，不参与「任意位置效率」比较。
【逐项辨析】
- A 顺序表：插入 / 删除后需移动后续所有元素，平均为 O(n)。
- B 链表：正确。 在已知插入 / 删除位置（或已定位到该结点）时，只需改指针，为 O(1)，且不移动任何元素。
- C 队列：队列是操作受限的线性表，只能在队尾入队、队头出队，不以“任意位置插删效率”为比较目标，属干扰项。
- D 栈：同样是操作受限的线性表，只能在栈顶插删，也是干扰项。
【知识点】 插入 / 删除的代价对比（设元素个数 n）：
| 结构 | 插入 / 删除的代价 | 是否移动元素 |
|---|---|---|
| 顺序表 | 平均移动 n/2 个元素 | 需要 |
| 链表 | 改 2~3 个指针 | 不需要 |
但要注意一个前提：链表“O(1) 插入删除”指的是已定位到目标位置。若还要先按序号查找，则查找本身要 O(n)，总代价仍是 O(n)。
【记忆锚点】 “顺序表靠搬，链表靠改”——搬元素慢，改指针快。
【易混对比】 三组数字务必分清：①顺序表插入平均移动 n/2 个元素；②顺序表删除平均移动 (n−1)/2 个元素；③链表插删本身 O(1)（不含查找）。这三组是国企笔试“线性表”最高频的对照考点（见第 17 题）。
【自测】 在单链表中，已知指针 p 指向某结点，在其后插入一个新结点 s 的时间复杂度是？
答：O(1)。只需
s->next = p->next; p->next = s;两条语句。与第 18 题（删后继）连考。
【知识关联】
- 同库连考：与第 10 题对读；与第 12 题（链表按序号 O(n))、第 17 题（顺序表插入平均移动 n/2）构成代价三角。
- 工程实现:Java 中「已知节点引用时 O(1) 插删」对应
LinkedList.ListItr或LinkedHashMap把哈希结点串成双向链表 —— 正是为了在已有引用上 O(1) 改链。 - 408 / 国企真题：国网原题；408 线性表比较题。
- 面试追问:①「链表插删 O(1) 有前提吗？」（已定位到结点/前驱）；②「只给待删结点指针不给前驱，单链表能 O(1) 删吗？」（非尾结点可以「值覆盖+删后继」）。
【拓展延伸】
变式：双链表相对单链表的优势不是插删本身仍是 O(1)，而是已知结点可 O(1) 找前驱，删除更方便；单链表找前驱要 O(n)。
完整对照:
顺序表插入:平均移动 n/2 → O(n)
单链表插删(已知 p):改 1~2 个指针 → O(1)
单链表删第 i 个(不知前驱):定位 O(n) + 改指针 O(1) → 总 O(n)工程应用：操作系统进程就绪队列、图的邻接表、哈希链地址法都是「改指针不搬数据」。
12. 在单链表中，访问第i个元素的时间复杂度为( )
标签：【互联网/国企笔试常考】
A. O(1) B. O(log n) C. O(n) D. O(n²)
答案：C
【结论】 单链表不支持随机访问，访问第 i 个元素需从头遍历，时间复杂度 O(n)，选 C。
【逐项辨析】
- A O(1)：这是顺序表按下标访问的复杂度，链表做不到。
- B O(log n)：链表没有可“折半”的随机访问能力，无法二分。
- C O(n)：正确。 必须从头结点开始逐个
p = p->next，最坏走 n 步。 - D O(n²)：单次访问不需要双层结构，不可能到平方级。
【知识点】 链表的“按序号访问”本质是顺序访问:
head → [a₁] → [a₂] → [a₃] → ... → [aᵢ] → ...
1 2 3 i
访问 aᵢ 要走 i−1 步,最坏 i = n 时走 n−1 步 → O(n)对照表
| 操作 | 顺序表 | 单链表 |
|---|---|---|
| 按序号访问 aᵢ | O(1) | O(n) |
| 查找某值 | O(n) | O(n) |
| 表头插入 / 删除 | O(n) | O(1) |
| 表尾插入（无尾指针） | O(1) | O(n) |
【记忆锚点】 “顺序表能跳，链表只能走”——链表没有下标，只能靠指针一步步挪。
【易混对比】 链表“按序号访问 O(n)”与“按值查找 O(n)”数值相同，但原因不同：前者是定位代价，后者是比较代价。链表的优势在插入删除，不在查找。
【自测】 在长度为 n 的单链表中，删除第 i 个结点（已知 i）的时间复杂度是？
答：O(n)。要先从头找到第 i−1 个结点，定位代价 O(n)；找到后改指针本身是 O(1)。与第 18 题连考。
【知识关联】
- 同库连考：与第 9 题（顺序表地址 O(1))、第 13 题(LinkedList get O(n))对照；与第 74、76 题（折半需要随机访问）连考 —— 链表不能二分的原因就是本题。
- 工程实现:Java
LinkedList.get(i)实现是「若 i < size/2 从头走，否则从尾走」—— 双向链表把常数减半，但阶仍是 O(n)。 - 408 / 国企真题:408 与国网均考「单链表是否支持随机访问」。
- 面试追问:①「为什么双向链表 get 仍是 O(n)？」（仍是遍历，只是方向可选）；②「跳表怎么把查找降到 O(log n)？」（多级索引）。
【拓展延伸】
变式：循环链表、双向链表按序号访问都是 O(n);带索引的链表（跳表）才能近似 O(log n)。
完整验算：访问第 i 个结点需走 i−1 次 next，期望 (n+1)/2 次，最坏 n−1 次 → O(n)。
工程应用：链表结点常常「按值删除」而非「按序号访问」（如 LRU）；设计 API 时避免对 LinkedList 写 for (int i) list.get(i) 这种 O(n²) 遍历，应使用迭代器。
13. 下列关于 ArrayList（动态数组）与 LinkedList（双向链表）的比较，正确的是( )
标签：【互联网笔试·Java 高频】
A. ArrayList 在头部插入元素的时间复杂度为 O(1) B. LinkedList 支持通过下标进行 O(1) 随机访问 C. LinkedList 的存储密度高于 ArrayList D. ArrayList 随机访问为 O(1),LinkedList 在已知节点位置时插入删除为 O(1)
答案：D【结论】 ArrayList 随机访问 O(1)、LinkedList 已知位置插删 O(1)，选 D。
【逐项辨析】
- A错：ArrayList 底层是数组，头部插入需把全部元素后移，为 O(n)。
- B错：LinkedList 底层是双向链表，不支持按下标 O(1) 随机访问，按序号访问需 O(n)。
- D 对:ArrayList 底层数组 → 支持 O(1) 随机访问；LinkedList 底层双向链表 → 已知节点指针时插删为 O(1)。
- C错：链表每个节点除数据外还要存前后两个指针，存储密度（有效数据占比）低于数组。
【知识点】 两者底层结构决定性能（必背对照）：
| 维度 | ArrayList | LinkedList |
|---|---|---|
| 底层结构 | 动态数组 | 双向链表 |
| 随机访问 aᵢ | O(1) | O(n) |
| 头部插入 / 删除 | O(n) | O(1) |
| 尾部插入 | 均摊 O(1) | O(1) |
| 存储密度 | 高（只存数据） | 低（多存两个指针） |
| 扩容 | 需扩容 + 复制（1.5 倍） | 无需扩容 |
记忆主线：数组查快改慢，链表改快查慢。
【记忆锚点】 “ArrayList 是数组的皮，LinkedList 是链表的皮”——看穿底层结构，性能差异自然推得。
【易混对比】 常见陷阱：“LinkedList 插入删除一定比 ArrayList 快” —— 这是错的。LinkedList 要先按序号找到位置，定位 O(n)；只有头部插入或已持有节点引用时，才真正体现 O(1) 优势。Java 岗笔试 / 面试超高频，常与 Vector（线程安全、方法加 synchronized）一起对比考查。
【自测】 需要频繁按索引读取数据、很少插入删除，应选哪个？
答：ArrayList。随机访问 O(1) 是它的核心优势。与第 15 题（顺序表 vs 链表）同考点。
【知识关联】
- 同库连考：与第 10、11、15 题（顺序表 vs 链表）是同一考点的 Java 工程版；与第 98 题(HashMap/Hashtable/ConcurrentHashMap)同属「Java 集合」笔试模块。
- 工程实现:
ArrayList:Object[] elementData，默认容量 10，扩容 1.5 倍(old + old>>1);LinkedList:Node{item, prev, next}双向链表 + 头尾指针；-Vector：类似 ArrayList 但方法synchronized，已少用；-CopyOnWriteArrayList：写时复制，读无锁。
- 408 / 国企真题：国企 Java 岗笔试「集合框架」必考；408 不直接考 Java 类，但底层结构完全同构。
- 面试追问:①「ArrayList 扩容为什么是 1.5 倍不是 2 倍？」（摊还分析与内存碎片折中；2 倍也可，1.5 更省一点可复用旧空间）；②「LinkedList 为什么很少在生产中优于 ArrayList？」（CPU 缓存局部性差 + 每个结点多 2 指针）。
【拓展延伸】
变式问法:
- 「随机访问 + 尾部 add」→ ArrayList（本题）；
- 「大量队列语义操作」→
ArrayDeque优于LinkedList作为队列；3. 「频繁在迭代器位置 remove」→ArrayList的Itr.remove仍要搬后续元素，LinkedList更优。
缓存视角：数组连续内存对 CPU cache line 友好，链表指针追逐 miss 率高 —— 即使理论都是 O(1) 改指针，实测 ArrayList 往往更快。面试高分点。
14. 在一个长度为 n 的数组中，依次求每个长度为 k 的滑动窗口内的最大值，要求总时间复杂度为 O(n)，则最优解法所使用的辅助数据结构是( )
标签：【互联网面试高频】
A. 栈 B. 哈希表 C. 最小堆 D. 双端队列（单调队列）
答案：D【结论】 求滑动窗口最大值且要求 O(n)，应使用单调双端队列，选 D。
【逐项辨析】
- A 栈：栈只能在一端进出，无法同时完成“左端淘汰过期元素、右端新增元素”的两端操作。
- D 双端队列（单调队列）：正确。 两端都能进出，可同时维护“右侧入队新元素、左侧淘汰过期元素”。
- C 最小堆：最小堆堆顶是最小值，求窗口最大值至少要换成最大堆；且堆无法 O(1) 判断堆顶元素是否已滑出窗口（需懒删除），取最值与删除均为 O(log n)，总复杂度 O(n log n)，达不到题要求的 O(n)。
- B 哈希表：哈希表只做映射，不具备“维护最值”的能力。
【知识点】 单调队列求滑动窗口最大值的算法
维护一个存下标的双端队列 dq,队头始终是当前窗口最大值的下标
1. 右端入队:新元素 x 入队前,把队尾所有 ≤ x 的元素弹出(它们永远不可能是最大值)
2. 左端淘汰:若队头下标已小于窗口左边界 i−k+1,弹出队头
3. 取最大值:队头下标对应的元素即为当前窗口最大值逐步示意（窗口大小 k = 3，序列 1, 3, −1, −3, 5, 3, 6）：
| 窗口 | 单调队列（存下标对应值） | 窗口最大值 |
|---|---|---|
| [1, 3, −1] | 3, −1 | 3 |
| [3, −1, −3] | 3, −1, −3 | 3 |
| [−1, −3, 5] | 5 | 5 |
| [−3, 5, 3] | 5, 3 | 5 |
| [5, 3, 6] | 6 | 6 |
每个元素至多入队、出队各一次，总时间复杂度 O(n)。
【记忆锚点】 “大数进门，小数全走”——新元素入队时把队尾所有比它小的弹出，队列始终单调递减。
【易混对比】 与第 93 题(TopK)区分：滑动窗口最大值用单调队列（保持顺序、两端操作）；TopK 用堆（只关心大小、不关心顺序）。两者都是“维护最值”的高频题，但结构选择不同。
【自测】 滑动窗口最大值若改用暴力法（每个窗口遍历求最大），时间复杂度是多少？
答：O(n·k)（n 个窗口 × 每窗口 k 个元素）。单调队列把每窗口的 O(k) 降到均摊 O(1)。字节、腾讯、华为等大厂笔试 / 面试高频题。
【知识关联】
- 同库连考：与第 26 题（栈/队列应用）、第 29 题（最小栈）、第 93 题（TopK 堆）同属「用特定结构维护最值/顺序」；与第 20~22 题（栈/双端队列）结构基础相连。
- 工程实现:单调队列真正用在滑动窗口最值这一类问题上——LeetCode 239 窗口最大/最小值、LeetCode 862「和至少为 K 的最短子数组」（前缀和 + 单调队列）、多重背包的单调队列优化（每一层由 O(V·n) 降到 O(V)）、图像形态学的膨胀/腐蚀（窗口 max/min）。别把这几处错认成单调队列：Linux
O(1)调度器是优先级数组 + 位图找首个非空队列（CFS 用红黑树），Netty 的流量控制是窗口字节计数 + autoRead/writability watermark，限流器的滑动窗口计数是时间戳队列——都没有「队内单调」这一要求。Java 无内置单调队列类，需手写ArrayDeque。 - 408 / 国企真题:408 不常考；国企一般不考；属互联网面试/笔试编程与概念题。
- 面试追问:①「为什么堆做不到 O(n)？」（堆顶过期后要删任意元素，堆不支持 O(1) 删任意）;②「单调队列和单调栈差在哪？」（一端 vs 两端；窗口问题用队列，直方图最大矩形用栈）。
【拓展延伸】
完整验算（k=3，序列 2,1,3,−1,−3,5）：
窗口[2,1,3] dq:2→弹2,1 → [3] max=3
窗口[1,3,-1] dq:[3,-1] max=3
窗口[3,-1,-3] dq:[3,-1,-3] max=3
窗口[-1,-3,5] dq:[5] max=5
（n=6、k=3 → 窗口数 n−k+1 = 4，到上一行为止）
每个元素至多入队出队各一次 → O(n) ✓变式：求滑动窗口最小值 → 单调递增队列；求「窗口内第 k 大」→ 对顶堆或权值线段树，不再是单调队列。
工程应用：实时监控「最近 5 分钟最大延迟」、游戏「最近 N 帧最大帧耗时」。
15. 以下关于顺序表和链表的比较，说法正确的是( )
标签：【互联网/国企笔试高频】
A. 顺序表插入删除不需要移动元素 B. 链表可以随机访问任意位置的元素 C. 顺序表存储密度高于链表 D. 链表支持按下标 O(1) 随机访问
答案：C
【结论】 顺序表只存数据、链表还要存指针，故顺序表存储密度更高，选 C。
【逐项辨析】
- A 错：顺序表插入删除需要移动元素，链表才不需要。
- B 错：链表不支持随机访问，访问第 i 个元素需 O(n) 遍历。
- C 对：顺序表只存储数据本身；链表每个节点除数据外还要存指针，有效数据占比更低。
- D 错：链表不支持按下标 O(1) 随机访问。
【知识点】 存储密度的定义与对比
存储密度 = 数据本身占用的空间 / 结点占用的总空间
顺序表:数据占 100%,存储密度 = 1
单链表:每个结点 = 数据 + 1 个指针,存储密度 < 1
双链表:每个结点 = 数据 + 2 个指针,存储密度更低顺序表 vs 链表完整对照（必背）：
| 维度 | 顺序表 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 插删（已知位置） | O(n)（要移动） | O(1)（改指针） |
| 存储密度 | 高(= 1) | 低(< 1) |
| 空间是否连续 | 连续 | 可不连续 |
| 扩容 | 需重新分配 + 复制 | 动态申请结点 |
【记忆锚点】 “顺序表空间全用来存数据，链表要拿一部分存指针”——所以顺序表存储密度高。
【易混对比】 存储密度与“空间复杂度”不是一回事：存储密度衡量的是单个结点里有效数据的占比，与算法运行所需的辅助空间无关。国企笔试常把“存储密度”“随机访问”“插删效率”三组特性交叉设置干扰项。
【自测】 下列哪一项是链表的优势？ A. 存储密度高 B. 支持随机访问 C. 已知位置时插删快 D. 空间连续
答：C。A、B、D 都是顺序表的优势。与第 10、11 题连考。
【知识关联】
- 同库连考：与第 9~13 题同一「顺序表 vs 链表」专题；与第 13 题 C 选项（LinkedList 存储密度低于 ArrayList）直接对应。
- 工程实现:Java 对象数组里每个引用 4/8 字节，链表每个结点再加 prev/next 两个引用 + 对象头，存储密度显著更低；
ArrayList对int若用Integer[]密度也会下降（装箱），int[]才高密度。 - 408 / 国企真题:408「存储密度」定义题；国网真题库高频辨析。
- 面试追问:①「存储密度和空间复杂度是一回事吗？」（不是，前者是结点内有效数据占比，后者是算法辅助空间）；②「怎样提高链表存储密度？」（单链表、存储器池、数据域紧凑）。
【拓展延伸】
变式：若元素很大而指针相对很小，链表密度下降比例变小；若元素是指针本身（如图邻接表存顶点编号），密度损失更明显。无完美结构，只有场景取舍。
完整对照表已在知识点中给出；记忆时把「密度=1」绑给顺序表，把「+指针开销」绑给链表。
16. 将两个有序链表合并为一个有序链表，最坏情况下的时间复杂度为( )，其中两个链表长度分别为m和n。
标签：【互联网/国企笔试超高频】
A. O(m+n) B. O(1) C. O(m×n) D. O(max(m,n))
答案：A
【知识点】 合并两个有序表是归并排序的核心原语:
| 环节 | 操作 | 代价 |
|---|---|---|
| 比较 | 每轮比两表当前结点 | 最多 m+n−1 次 |
| 最好 | 一表全部先耗尽 | min(m,n) 次 |
| 挂链/赋值 | 较小者接入结果 | 每次 O(1) |
| 总计 | 两表各扫一遍、不回头 | O(m+n) |
归并排序总复杂度 = 合并层数 × 单层合并代价 = O(log n) × O(n) = O(n log n)。理解本题才能真正推懂归并为何不是 O(n²)。空间上合并需要 O(m+n) 辅助（链表可原地但易错，顺序表通常开辅助数组）。
【推导过程】 合并过程：用两个指针分别指向两链表的当前结点，每次比较取较小者接到结果链表尾部，再移动该指针。
链表1:m 个结点,链表2:n 个结点
每轮比较 → 输出 1 个结点 → 总输出 m+n 个结点
比较次数 ≤ m + n − 1 → O(m+n)【逐项辨析】
- B O(1)：合并必须遍历全部结点，不可能常数时间。
- A O(m+n)：正确。 与两条链表的长度之和成正比。
- C O(m×n)：这是“双重循环”的量级，合并只需单次扫描。
- D O(max(m,n))：漏掉了另一条链表也要走完。
【知识点】 合并两个有序表是归并排序的核心操作:
| 环节 | 操作 | 代价 |
|---|---|---|
| 比较 | 每轮比较两表当前结点 | 合计 ≤ m+n−1 次 |
| 挂链 | 把较小者接到结果尾部 | 每次 O(1) |
| 总计 | — | O(m+n) |
关键：两条链表各自只被扫描一遍，不回头。 这与“两两比较”的 O(m×n) 有本质区别。
【记忆锚点】 “各走一遍，边走边挑”——两条链表都只遍历一次，总代价就是两段长度之和。
【易混对比】 归并排序总复杂度 = 合并层数 × 单层合并代价 = O(log n) 层 × O(n) = O(n log n)。理解本题的 O(m+n)，才能推得归并排序的 O(n log n)（见第 80 题）。
【自测】 若两个有序表分别有 m、n 个元素，合并后最坏需要比较多少次？
答：m + n − 1 次。最后一个元素无需比较即可确定位置。与第 80 题（归并排序）连考。
【知识关联】
- 同库连考：与第 80 题（归并排序 O(n log n))直接母子关系 —— 本题是「一层合并的代价」，归并是「log n 层 × 本题代价」；与第 11 题（链表改指针）合并时也只改指针。
- 工程实现:Java
Collections.sort底层 TimSort 的 merge 步骤、数据库多路归并、外部排序大文件合并，核心都是本题。 - 408 / 国企真题:408 归并排序分析必用；国网「排序」模块常考合并趟数与比较次数。
- 面试追问:①「最好情况比较次数？」(min(m,n)，一表先耗尽）;②「最坏？」(m+n−1);③「k 个有序表合并复杂度？」（用堆 O(n log k))。
【拓展延伸】
完整验算:
L1: 1,3,5 L2: 2,4
比较:1<2→1;3>2→2;3<4→3;5>4→4;剩5
比较 4 次 = m+n−1 = 3+2−1 ✓
最坏总比较 m+n−1 → O(m+n)变式:
- k 路归并朴素 O(k·n)，败者树/堆 O(n log k)。
- 合并 m 个、n 个、p 个有序表 → O(m+n+p)。
- 若两表无序，合并不能 O(m+n)，需先排序或改哈希。
工程应用:MapReduce 的 shuffle 归并、LSM-Tree 的 SSTable merge、Git 三方合并的基线思想同源。
17. 在长度为 n 的顺序表中，等概率地在任意位置插入一个元素，平均需要移动的元素个数为( )
标签：【国企笔试超高频】
A. n/2 B. (n+1)/2 C. n D. n-1
答案：A
【结论】 等概率插入的平均移动次数为 n/2，选 A。
【推导过程】 长度为 n 的顺序表共有 n+1 个可插入位置（第 1 个元素之前到第 n 个元素之后）：
在第 i 个位置插入,需向后移动 n−i+1 个元素
位置 1 → 移动 n 个;位置 2 → 移动 n−1 个;...;位置 n+1 → 移动 0 个
等概率(每位置概率 1/(n+1))下:
平均移动 = [n + (n−1) + ... + 1 + 0] / (n+1)
= [n(n+1)/2] / (n+1)
= n/2【逐项辨析】
- A n/2：正确。 插入的平均移动次数。
- B (n+1)/2：这是顺序查找的平均比较次数，与插入移动无关（见第 68 题）。
- C n：这是“在最坏位置（表头）插入”的移动次数，不是平均。
- D n−1：接近但不对 —— 可插入位置有 n+1 个，分母是 n+1 而非 n。
【知识点】 顺序表三大平均代价对照（国企笔试最爱考的一组数字）：
| 操作 | 平均移动 / 比较次数 | 推导要点 |
|---|---|---|
| 插入 | n/2 | 位置数 n+1，移动数从 n 递减到 0 |
| 删除 | (n−1)/2 | 位置数 n，移动数从 n−1 递减到 0 |
| 顺序查找 | (n+1)/2 | 比较次数从 1 递增到 n |
插入:[n + (n−1) + ... + 1 + 0] / (n+1) = n/2
删除:[(n−1) + (n−2) + ... + 1 + 0] / n = (n−1)/2
查找:[1 + 2 + ... + n] / n = (n+1)/2【记忆锚点】 “插 n/2，删 (n−1)/2，查 (n+1)/2”——插入位置比删除多一个（有“表尾之后”），所以分子分母都略大；查找从 1 开始累加，所以是 (n+1)/2。
【易混对比】 这三个数字极易被交叉设置成干扰项。区分诀窍：看操作对象是“位置”还是“元素” —— 插入有 n+1 个位置、删除有 n 个位置、查找有 n 个元素。2025 年国家电网计算机类笔试同型题。
【自测】 长度为 n 的顺序表，等概率删除一个元素，平均需要移动多少个元素？
答：(n−1)/2 个。删除第 i 个元素需移动 n−i 个，等概率下平均 = [(n−1)+(n−2)+…+0]/n = (n−1)/2。与本题对照记忆。
【知识关联】
- 同库连考：与「删除平均 (n−1)/2」「顺序查找 (n+1)/2」构成国企必背三连；与第 11 题（链表插删）对照 —— 顺序表插入的代价来源就是「搬元素」。
- 工程实现:Java
ArrayList.add(index, e)会System.arraycopy搬后续元素，平均搬 n/2 个引用 —— 这就是本题的工程实现。大数据量下应避免中间插入。 - 408 / 国企真题:2025 年国网计算机类笔试同型原题；408 线性表分析题。
- 面试追问:①「为什么分母是 n+1 不是 n？」（可插入位置有 n+1 个）；②「表尾插入平均搬多少？」（0，若不扩容）。
【拓展延伸】
完整验算与对照:
插入位置 1..n+1,移动 n, n-1, ..., 1, 0
平均 = [n+(n-1)+...+0]/(n+1) = n(n+1)/2 / (n+1) = n/2 ✓
删除位置 1..n,移动 n-1, n-2, ..., 1, 0
平均 = (n-1)n/2 / n = (n-1)/2
顺序查找成功:比较 1..n 次
平均 = n(n+1)/2 / n = (n+1)/2变式:
- 若只允许在前 n 个位置插（无表尾后）：平均 = n/2 近似或略变；2. 删除后有时要求压缩，代价另计；3. 链表插入本身 O(1)，但若「按序号定位再插」总代价 O(n)，平均定位 (n+1)/2 步。
工程应用：解释了为何批量构建列表用 add 尾插，而「按位置 insert」在日志、消息处理中要避免。
18. 已知指针 p 指向单链表中的某个结点（p 不是尾结点），要删除 p 所指结点的后继结点，正确的操作是( )
标签：【国企笔试超高频】
A. p->next = p->next->next; free(p->next); B. q = p->next; p->next = q->next; free(q); C. q = p->next->next; p->next = q; free(q); D. p->next = NULL; free(p->next);
答案：B
【结论】 正确顺序是先用临时指针 q 保存待删结点，再断链、最后释放，选 B。
【逐项辨析】
- A错：
p->next = p->next->next;先改链，此时p->next已指向“后继的后继”，再free(p->next)释放的是错误的结点，真正的目标结点脱离链表却未被释放，造成内存泄漏。 - B 对:
q = p->next; p->next = q->next; free(q);—— 先保存、再断链、后释放，顺序正确。 - C错：
q = p->next->next;让 q 直接指向后继的后继，p->next = q把这条链挂上，原后继结点脱离链表且从未被释放，等于“跳删”。 - D错：
p->next = NULL;丢失了整条后缀链，且free(NULL)什么也没释放。
【知识点】 单链表删除操作的黄金三步:
第 1 步 保存:q = p->next; // 先记住要删谁
第 2 步 断链:p->next = q->next; // 把前驱接到后继的后继
第 3 步 释放:free(q); // 归还这块内存指针变化示意（删除 p 的后继 q）：
删除前: p ──→ q ──→ r ──→ ...
删除后: p ─────────→ r ──→ ... (q 被摘除并释放)顺序不可颠倒 —— 必须先保存 q，否则断链后再也找不到待删结点，无法释放。
【记忆锚点】 “先记住、再断链、后释放”（保存 → 断链 → 释放），三步缺一不可。
【易混对比】 与“在 p 之后插入结点 s”对照：s->next = p->next; p->next = s; —— 插入是“先接后断”，删除是“先存后断”，两者的指针赋值顺序都不可颠倒。2025 年国家电网计算机类笔试同型题。
【自测】 若只给出指向待删结点 p 本身的指针（不给前驱），能否 O(1) 删除它？
答：可以，但前提是 p 不是尾结点。 做法：把后继结点的值复制到 p，再删除后继 ——
p->data = p->next->data; q = p->next; p->next = q->next; free(q);。若是尾结点则无解，只能从头找前驱。大厂面试高频追问。
【知识关联】
- 同库连考：与第 11 题（已知位置插删 O(1))、第 12 题（定位 O(n))配合读；与第 49 题（快慢指针）同属「指针操作细节」面试高频。
- 工程实现:C/C++ 手写链表必须先保存再 free;Java 由 GC 接管，但
LinkedList.remove仍要把 prev/next 置空帮助 GC，思路同源。LinkedHashMap淘汰结点时也是「先摘链再交给 GC」。 - 408 / 国企真题:2025 年国网计算机类笔试同型；408 链表操作题常考指针顺序。
- 面试追问:①「只给待删结点、无前驱、单链表，能 O(1) 删除吗？」（非尾结点：值覆盖+删后继）；②「删除尾结点为何必须 O(n)？」（要找前驱）；③「双向链表为何就能 O(1) 删任意非哨兵结点？」（有 prev）。
【拓展延伸】
变式代码对照:
// 删除后继(本题)
q = p->next; p->next = q->next; free(q);
// 在 p 后插入 s(对照,先接后断)
s->next = p->next; p->next = s;
// 头插
s->next = head->next; head->next = s;易错变式:
free(p->next); p->next = p->next->next;→ use-after-free，未定义行为；- 双链表删除还需q->next->prev = q->prev; q->prev->next = q->next;四步。
工程应用：数据库页链表、文件系统 inode 链、内核 list_head 都要求「摘链顺序正确」，否则环或泄漏。