📚 栈、队列与链表专项强化练习题（共36题）

第一部分：栈 (Stack) 专项练习（12题）

1. [基础] 栈的特点是（ ）。 A. 先进先出 (FIFO) B. 后进先出 (LIFO) C. 只能在两端插入 D. 没有任何限制
2. [基础] 向一个空栈中依次压入元素 A, B, C, D，那么第一个弹出的元素是（ ）。 A. A B. B C. C D. D
3. [真题模拟] 元素入栈的顺序为 1, 2, 3, 4, 5，下列哪个是合法的出栈序列？ A. 5, 4, 3, 2, 1 B. 4, 5, 3, 1, 2 C. 3, 1, 4, 2, 5 D. 2, 3, 1, 5, 4
4. [真题模拟] 有 6 个元素，按照 6, 5, 4, 3, 2, 1 的顺序进入栈 S，下列哪个出栈序列是非法的？ A. 5, 4, 3, 6, 1, 2 B. 4, 5, 3, 1, 2, 6 C. 3, 4, 6, 5, 2, 1 D. 2, 3, 4, 1, 5, 6 (对应真题 ID: 2861)
5. [进阶] 若一个栈的输入序列是 1, 2, ..., n，其输出序列的第一个元素是 n，则第 $i$ 个输出的元素是（ ）。 A. $n-i$ B. $n-i+1$ C. $i$ D. 无法确定
6. [应用] 计算机在实现函数递归调用时，通常使用以下哪种数据结构来保存参数和返回地址？（ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 (对应真题 ID: 2131)
7. [表达式] 中缀表达式 a + b * c 对应的后缀表达式是（ ）。 A. a b c * + B. a b + c * C. + a * b c D. ab+c*
8. [表达式] 表达式 a * (b + c) - d 的后缀表达式是（ ）。 A. a b c * + d - B. a b c + * d - C. a b c * + d - D. - + * a b c d (对应真题 ID: 2112)
9. [容量计算] 现有栈 S 初始为空，长度为 4 的序列 a, b, c, d 依次入栈，期间可以任意次出栈。能得到的不同出栈序列共有多少种？ A. 12 种 B. 14 种 C. 24 种 D. 16 种
10. [栈与队列综合] 假设栈 S 和队列 Q 的初始状态为空。元素 e1, e2, e3, e4 依次进栈 S，并将从栈中弹出的元素依次压入队列 Q，最后从队列 Q 全部出队。出队的顺序是（ ）。 A. e1, e2, e3, e4 B. e4, e3, e2, e1 C. e3, e4, e1, e2 D. 随机
11. [代码模拟] 运行以下栈操作伪代码：push(1); push(2); pop(); push(3); push(4); pop();，此时栈顶元素是： A. 1 B. 2 C. 3 D. 4
12. [括号匹配] 用栈来检查表达式中的括号是否配对：((())())，在扫描到最右边的最后一个 ) 时，栈中还剩几个左括号 (？ A. 0 B. 1 C. 2 D. 3

第二部分：队列 (Queue) 专项练习（12题）

1. [基础] 队列的特点是（ ）。 A. 先进先出 (FIFO) B. 后进先出 (LIFO) C. 两端都可以出入 D. 随机访问
2. [基础] 元素 1, 2, 3, 4 依次进入一个初始为空的队列，那么第一个出队的元素是（ ）。 A. 4 B. 3 C. 2 D. 1
3. [真题模拟] 下列关于队列的说法中，错误的是： A. 队列可以用数组实现，也可以用链表实现
   B. 广度优先搜索（BFS）算法通常采用队列来存储待访问的节点
   C. 队列的队头和队尾指针都是固定不变的
   D. 办事大厅的排队叫号系统本质上就是队列的应用
4. [操作模拟] 某队列有效长度最大为 3。依次执行：入队 A、入队 B、入队 C，然后出队一个元素，再入队 D。此时队列中的元素从队头到队尾依次是： A. A, B, C B. B, C, D C. D, B, C D. A, C, D
5. [双端队列] 允许在两端进行插入和删除操作的线性表称为（ ）。 A. 栈 B. 队列 C. 双端队列 (Deque) D. 循环链表
6. [循环队列] 在容量为 $N$ 的循环队列中，若队头指针是 front，队尾指针是 rear，则判断队列为空的条件通常是： A. front == rear B. front == (rear + 1) % N C. front == rear + 1 D. front = 0
7. [算法应用] 图的广度优先遍历（BFS）在逐层扫描节点时，核心依赖的数据结构是： A. 栈 B. 队列 C. 堆 D. 散列表 (对应真题 ID: 2070)
8. [逻辑判断] 下列关于栈和队列的差异，说法不正确的是： A. 栈只允许在表的一端进行操作，队列在两端进行操作
   B. 栈是 LIFO，队列是 FIFO
   C. 栈和队列都可以用链式存储结构实现
   D. 队列可以用栈完全替代且没有任何效率损失
9. [出队序列] 元素 a, b, c, d 依次进入队列，且允许在入队过程中穿插出队操作（只要队列不空），下列不可能的出队序列是： A. a, b, c, d B. d, c, b, a C. a, c, b, d D. 以上均可能
10. [循环队列长度] 某循环队列的队头指针为 2，队尾指针为 6（指向队尾元素），容量为 10（下标 0~9）。队列中当前元素的个数为： A. 4 B. 5 C. 6 D. 3
11. [模拟推导] 初始队列为空，执行以下操作：push(1), push(2), pop(), push(3), pop(), push(4)，此时队列中元素个数为： A. 1 B. 2 C. 3 D. 4
12. [生活常识] 操作系统在处理打印机打印任务时，多个文档同时发送会排队等待打印，这是因为操作系统运用了（ ）机制。 A. 栈 B. 队列 C. 递归 D. 贪心

第三部分：链表 (Linked List) 专项练习（12题）

1. [基础] 链表在内存中的存储空间通常是： A. 连续的一段地址 B. 必须对齐 C. 连续或不连续都可以 D. 绝对随机且不可预测 (对应真题 ID: 674)
2. [基础] 链表中的每个节点至少包含两个域，一个是数据域，另一个是（ ）。 A. 指针域 (next) B. 下标域 C. 优先域 D. 根节点域
3. [优缺点] 与顺序表（数组）相比，链表的一个显著优点是： A. 可以随机访问任一元素 B. 插入和删除元素时不需要移动其他节点 C. 占用内存空间更少 D. 排序更方便 (对应真题 ID: 648)
4. [真题模拟] 链表和数组的区别，表述正确的是： A. 数组不能排序，链表可以
   B. 数组大小固定，链表大小可以动态调整
   C. 链表存储的信息量一定比数组多
   D. 以上说法均正确 (对应真题 ID: 2863)
5. [指针操作] 有如下指针赋值代码：p = q; 它的行为是： A. 把 q 的值赋给 p 所指向的变量
   B. 让 p 指向 q 所指向的同一地址（对象）
   C. 把 p 指向的内容复制给 q
   D. 释放 p 的内存空间 (对应真题 ID: 2862)
6. [单链表插入] 假设有一个单链表节点结构：struct Node { int data; Node* next; };。若要将一个新节点 newNode 插入到指针 p 指向的节点后面，正确的代码是： A. p->next = newNode; newNode->next = p->next;
   B. newNode->next = p->next; p->next = newNode;
   C. newNode = p->next; p->next = newNode->next;
   D. p->next = newNode->next; newNode->next = p;
7. [单链表删除] 在单链表中，若要删除指针 p 指向节点的后继节点（即删除 p 后面的那个节点），正确的代码是（设后继节点为 q = p->next）： A. p->next = p->next->next; delete q;
   B. p = p->next; delete p;
   C. p->next = q; delete q;
   D. p = q->next;
8. [双向链表] 双向链表节点中通常包含两个指针域，分别称为 llink（前驱）和 rlink（后继）。如果在双向链表中节点 p 后面插入节点 s，下列操作哪一项是正确的？ A. s->rlink = p->rlink; p->rlink->llink = s; p->rlink = s; s->llink = p;
   B. p->rlink = s; s->llink = p;
   C. s->llink = p; s->rlink = p->rlink;
   D. p->rlink = s->rlink;
9. [循环链表] 在单向循环链表中，判断链表为空（只有一个头指针 head 且无有效节点）的条件通常是： A. head == NULL B. head->next == NULL C. head->next == head D. head->data == 0
10. [性能分析] 在一个长度为 $n$ 的单链表中查找值为 x 的元素，在最坏情况下，其时间复杂度为： A. $O(1)$ B. $O(\log n)$ C. $O(n)$ D. $O(n^2)$
11. [头指针变化] 有一个带头结点的单链表。如果要向表头插入一个新元素（即作为第一个真正的数据节点），以下哪个说法是正确的？ A. 不需要修改头指针，只需要修改头结点的 next
    B. 必须修改头指针的值
    C. 只能在链表尾部插入
    D. 链表不支持头部插入
12. [综合应用] 下列关于线性结构存储方式的叙述中，正确的是： A. 顺序存储的物理地址必须连续，链式存储的物理地址可连续可不连续
    B. 链式存储空间利用率一定比顺序存储高
    C. 顺序存储比链式存储更适合频繁插入、删除的场景
    D. 链表可以通过下标直接访问第 k 个元素

---

📝 参考答案与精简解析

栈部分 (1-12)

1. B （后进先出）
2. D （最后压入的 D 最先弹出）
3. A （5全部压入后依次弹出即为 5,4,3,2,1）
4. C （当 3 先出时，6、5、4 都在栈内，轮到 4 或 5 出，不可能直接跳到 6）
5. B （元素 $n$ 第一个出，若按特定顺序，第 $i$ 个输出为 $n-i+1$）
6. B （函数递归利用系统的函数调用栈）
7. A （乘法优先于加法，后缀为 a b c * +）
8. B （b+c 先算，变 bc+，乘 a 变 abc+*，减 d 变 abc+*d-）
9. B （卡特兰数 $C_4 = \frac{1}{4+1}\binom{8}{4} = 14$）
10. B （栈是逆序 e4,e3,e2,e1，进队列后由于队列先进先出，出队顺序保持不变，依然是 e4,e3,e2,e1）
11. C （模拟：压1,压2,弹出2(剩1),压3(顶3),压4(顶4),弹出4(顶3)。当前栈顶是 3）
12. B （遍历到最后一个 ) 前，左括号依次入栈。由于 ((())()) 共有 4 个左括号，3 个右括号匹配抵消，最后栈内剩 1 个左括号）

队列部分 (13-24)

1. A （先进先出）
2. D （第一个进去的 1 最先出来）
3. C （队列的头尾指针随着出队入队会动态向后移动，并不是固定不变的）
4. B （初始 A,B,C，A 出队剩 B,C，入队 D 变成 B,C,D）
5. C （双端队列 Deck）
6. A （循环队列判空通常是 front == rear）
7. B （BFS 必备队列）
8. D （队列可以用栈模拟，但需要两个栈配合，且会带来时间开销，并非“没有任何效率损失”）
9. C （队列是严格先进先出的，a 必须比 c 先出，因此 a,c,b,d 违背了队列规则）
10. B （队尾 6，队头 2，元素个数 = $(6 - 2 + 10) \pmod{10} + 1$ 或根据具体循环队列公式算得 5 个：下标 2,3,4,5,6 共有 5 个元素）
11. B （模拟：push1(1), push2(1,2), pop(输出1,剩2), push3(2,3), pop(输出2,剩3), push4(3,4)。剩下 2 个元素）
12. B （打印任务先发先打印，符合队列）

链表部分 (25-36)

1. C （链表内存可以连续也可以不连续）
2. A （指针域 next）
3. B （链表最大优势是插删不用挪动元素）
4. B （数组大小静态固定，链表动态分配）
5. B （p = q 让指针 p 指向 q 所指向的内存地址）
6. B （必须先连后面：newNode->next = p->next; 再断开重连：p->next = newNode; 防止断链）
7. A （安全删除后继节点：让 p->next 指向下下个节点，然后 delete q）
8. A （双向链表插入要修改 4 个指针方向，A 选项逻辑完整严密）
9. C （循环链表头结点的 next 指向自己时为空）
10. C （链表不支持随机跳跃，最坏要查到尾部，时间复杂度 $O(n)$）
11. A （对于带头结点的链表，头指针永远指向头结点不变，插入新元素只需修改头结点的 next 指针即可）
12. A （顺序存储物理地址必须连续，链式存储任意）

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com