考点拆分 03 · 链表 · 栈 · 队列（约 25 分）

来源：2024 回忆版
系统笔记：2.2 线性表 2.3 栈和队列

---

必背清单

• [ ] 顺序表插入/删除 O(n)；随机访问 O(1)
• [ ] 链式：数据域 + 指针域
• [ ] 带头结点空表：head->next == NULL
• [ ] 不带头空表：head == NULL
• [ ] 插在 p 后：s->next=p->next; p->next=s;（顺序不可反）
• [ ] 栈 LIFO；队列 FIFO；共同点：受限线性表
• [ ] 线性表：除首元外每元恰有一前驱

---

2024 真题回放

位置	答案	一句话
单选 12	C O(n)	顺序表插入后移
单选 16	D	数据域+指针域
单选 17	C	带头空表 next 空
单选 18	B 2	全入后弹：4,3,2,1
单选 20	D	标准后插两句
判断 5	×	栈队都是受限线性表
判断 10	√	前驱定义
简答 3	—	顺序表优缺点默写

---

简答模板：顺序表优缺点

优点

1. 随机访问 O(1)
2. 存储密度高（无指针开销）
3. 实现简单

缺点

1. 插删平均 O(n)
2. 需预分配，可能浪费/溢出
3. 要求连续内存

---

栈序速算

条件：1..n 依次入栈，允许任意时刻出栈。

2024 题：首出 4 ⇒ 1,2,3,4 已全入 ⇒ 出栈序列唯一 4 3 2 1。

---

同型自测

1. 不带头结点空表条件？
2. 将 s 插在 p 之前（已知 p 的前驱 pre）两句？
3. 1,2,3 入栈，能否得到出栈序 3,1,2？

答案

1. head == NULL
2. s->next = p; pre->next = s;
3. 不能。3 先出说明 1,2,3 全在栈，再出只能 2 然后 1，得不到 3,1,2

---

返回：_索引 · 全卷