题目部分（共 90 题）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第一部分：单链表（SINGLY LINKED LIST）—— 第 1 - 30 题
1. 定义单链表节点 struct Node { int data; Node* next; }; 若要创建一个值为 5 的新节点，正确的代码是？
A. Node* p = new Node; p->data = 5; p->next = NULL;
B. Node p; p.data = 5; p.next = NULL;
C. Node* p = (Node*)malloc(sizeof(Node)); p.data = 5;
D. Node p = new Node(5);
2. 在单链表中，判断当前节点 p 是否为链表最后一个节点的条件是？
A. p == NULL
B. p->next == NULL
C. p->data == 0
D. p->next == p
3. 若头指针为 head，遍历单链表并打印所有节点的循环条件应为？
A. while (head)
B. while (head->next)
C. for (auto p = head; p != NULL; p = p->next)
D. while (p->next != NULL)
4. 单链表的头插法（在头部插入新节点 s）的正确操作序列是？
A. s->next = head; head = s;
B. head = s; s->next = head;
C. s->next = head->next; head->next = s;
D. head->next = s; s->next = NULL;
5. 在单链表中，已知节点 p（非尾节点），要在 p 之后插入节点 s，正确的操作是？
A. s->next = p; p->next = s;
B. p->next = s; s->next = p->next;
C. s->next = p->next; p->next = s;
D. p->next = s->next; s->next = p;
6. 删除单链表头节点的正确操作（头指针为 head）是？
A. head = head->next;
B. Node* temp = head; head = head->next; delete temp;
C. delete head; head = head->next;
D. head->next = head;
7. 迭代反转单链表时，需要用到几个指针？
A. 1 个
B. 2 个
C. 3 个
D. 4 个
8. 递归反转单链表的终止条件通常是？
A. head == NULL
B. head == NULL || head->next == NULL
C. head->next == NULL
D. head->data == -1
9. 已知某单链表 1->2->3->4->5，将其向右旋转 2 位（rotateRight(2)）后，结果应为？
A. 3->4->5->1->2
B. 4->5->1->2->3
C. 2->1->4->3->5
D. 5->4->3->2->1
10. 使用快慢指针判断单链表是否有环，若快指针每次走 2 步，慢指针每次走 1 步。若无环，快指针到达空的条件是？
A. fast == NULL
B. fast->next == NULL
C. fast == NULL || fast->next == NULL
D. fast->next->next == NULL
11. 在有环链表中，快慢指针相遇后，将慢指针重置到头节点，快指针留在相遇点，两者都每次走 1 步。它们再次相遇的节点是？
A. 链表尾节点
B. 链表头节点
C. 环的入口节点
D. 第一次相遇的节点
12. 使用快慢指针找单链表的中间节点（偶数长度时返回第二个中间节点），慢指针每次走 1 步，快指针应如何移动？
A. 快指针每次走 1 步
B. 快指针每次走 2 步，且条件为 fast && fast->next
C. 快指针每次走 2 步，且条件为 fast->next && fast->next->next
D. 快指针每次走 3 步
13. 给定一个非尾节点指针 p（不提供头节点），删除该节点的“狸猫换太子”做法是？
A. p = p->next;
B. p->data = p->next->data; p->next = p->next->next; delete ...;
C. free(p);
D. p->next = NULL;
14. 删除单链表中所有值为 target 的节点，需要维护几个指针？
A. 1 个（当前指针）
B. 2 个（当前指针 + 前驱指针）
C. 3 个（前驱、当前、后继）
D. 4 个
15. 删除已排序单链表中的重复元素（保留一个），若当前节点为 cur，判断条件应为？
A. if (cur->data == cur->next->data)
B. if (cur->data == cur->next->data) { cur->next = cur->next->next; }
C. if (cur->next && cur->data == cur->next->data)
D. 以上都需要先判空
16. 合并两个有序单链表，时间复杂度为？
A. O(1)
B. O(n)
C. O(n log n)
D. O(n^2)
17. 将链表按值 x 分割为小于 x 和大于等于 x 两部分，且保持原顺序，通常采用什么方式？
A. 直接在原链表上交换节点
B. 使用两个哑节点（dummy）分别构建两个子链表，最后连接
C. 使用数组存储后重新链接
D. 使用递归反转
18. 合并 K 个有序链表，使用优先队列（小根堆）时，队列中最多同时存储多少个节点？
A. K 个
B. 总节点数
C. 1 个
D. K/2 个
19. 对单链表进行归并排序，其空间复杂度为（不考虑递归栈）？
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
20. 判断单链表是否为回文（要求 O(1) 空间），核心思路是？
A. 复制到数组再判断
B. 使用栈存储前半部分
C. 找中点，反转后半部分，比较前后两半
D. 递归比较首尾
21. 在 C++ 中，若链表节点包含 std::string 成员，释放节点时使用 delete 会？
A. 只释放节点内存，不调用 string 析构
B. 调用 string 析构函数，正确释放内部资源
C. 导致内存泄漏
D. 编译报错
22. 以下哪个是浅拷贝导致的问题？
A. 两个链表对象共享同一组节点，析构时重复释放（double free）
B. 节点值被错误修改
C. 无法遍历链表
D. 头指针丢失
23. 若函数的形参为 ListNode* head，在函数内部对 head 重新赋值（如 head = head->next），外部实参是否会受影响？
A. 会，因为传递的是指针
B. 不会，因为传递的是指针的副本
C. 会，但仅限于修改节点内容时
D. 编译错误
24. 以下哪种情况容易导致单链表操作的死循环？
A. 尾节点 next 指向自身（循环）
B. 头节点 next 指向 NULL
C. 删除中间节点
D. 查找不存在的值
25. 已知两个单链表相交（Y 型），求交点最常用的方法是？
A. 暴力双重循环
B. 哈希表存储节点地址
C. 计算两个链表长度差，对齐后同步遍历
D. 使用快慢指针
26. 链表反转递归写法中，newHead = reverse(head->next); head->next->next = head; 如果忘记将 head->next = NULL，会导致什么？
A. 反转失败，但无环
B. 新链表尾节点指向旧头节点，形成环
C. 内存泄漏
D. 段错误
27. 对于单链表，查找某个值是否存在的时间复杂度最坏是？
A. O(1)
B. O(log n)
C. O(n)
D. O(n^2)
28. 使用哑节点（Dummy Node）的主要目的是？
A. 减少内存使用
B. 统一头节点和普通节点的插入/删除逻辑，减少边界判断
C. 加快查找速度
D. 实现循环链表
29. 计算单链表长度，迭代法时间复杂度 O(n)，若使用递归法并处理 100 万个节点，可能的风险是？
A. 堆溢出（Heap Overflow）
B. 栈溢出（Stack Overflow）
C. 内存泄漏
D. 编译失败
30. 如果单链表的头指针 head 为 NULL，以下哪个操作一定安全？
A. head->data = 0;
B. if (head->next == NULL) ...
C. if (head == NULL) return;
D. delete head->next;
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二部分：链式栈（LINKED STACK）—— 第 31 - 60 题
31. 链式栈的栈顶指针通常指向？
A. 链表的头节点
B. 链表的尾节点
C. 链表的中间节点
D. 一个独立的哑节点
32. 链式栈入栈（push）操作相当于单链表的什么操作？
A. 头插法
B. 尾插法
C. 在中间插入
D. 删除头节点
33. 链式栈出栈（pop）操作的正确步骤是（栈顶为 top）？
A. Node* temp = top; top = top->next; delete temp;
B. top = top->next;
C. delete top; top = NULL;
D. top = top->next; delete top;
34. 链式栈判空的条件是？
A. top == NULL
B. top->next == NULL
C. size == 0 && top != NULL
D. top->data == -1
35. 相比于顺序栈（数组实现），链式栈最大的优势是？
A. 访问速度快
B. 不易产生栈溢出（不会因容量固定而满）
C. 内存连续
D. 支持随机访问
36. 链式栈的 peek（查看栈顶元素）操作，若栈为空，正确的是？
A. 返回 top->data
B. 抛出异常或返回错误值
C. 返回 0
D. 自动入栈一个默认值
37. 若链式栈类未提供拷贝构造函数，执行 Stack s2 = s1; 时会发生？
A. 编译报错
B. 默认浅拷贝，两个对象共享同一底层链表
C. 自动深拷贝
D. 移动语义被触发
38. 在链式栈的析构函数中释放所有节点，最安全的方式是？
A. 递归调用析构
B. while(top) { Node* temp = top; top = top->next; delete temp; }
C. 调用 free(top)
D. 不释放，依赖操作系统回收
39. 实现链式栈的移动构造函数（Move Constructor），通常将源对象的 top 指针设置为？
A. NULL
B. 指向源对象的拷贝
C. 指向自身
D. 不修改
40. 重载链式栈的赋值运算符时，处理自赋值（s = s）最恰当的方式是？
A. 直接返回 *this
B. 先判断 if (this == &s) return *this;
C. 不做判断，会导致死循环
D. 先释放自身再拷贝，导致数据丢失
41. 用链式栈判断括号匹配，当遇到右括号 ')' 时，正确的操作是？
A. 直接入栈
B. 检查栈顶是否为左括号 '('，若匹配则弹出，否则失败
C. 将栈顶弹出并忽略
D. 清空栈
42. 后缀表达式 3 4 + 5 * 的值为？
A. 35
B. 23
C. 15
D. 60
43. 中缀表达式转后缀时，遇到运算符，若栈顶运算符优先级高于或等于当前运算符，则？
A. 将当前运算符入栈
B. 弹出栈顶运算符直到满足条件，再将当前运算符入栈
C. 忽略当前运算符
D. 直接输出当前运算符
44. 使用链式栈模拟十进制转二进制，输出的二进制字符串是？
A. 入栈顺序
B. 出栈顺序（即逆序）
C. 随机顺序
D. 中序遍历
45. 设计最小栈（MinStack），辅助栈中存储的是？
A. 当前所有元素的副本
B. 每次入栈时的最小值（或最小值指针）
C. 原栈元素的索引
D. 随机值
46. 用两个链式栈实现队列，pop 操作时，若输出栈为空，应该？
A. 返回 -1
B. 将输入栈的所有元素依次弹出并压入输出栈
C. 交换输入栈和输出栈
D. 清空输入栈
47. 用两个栈实现队列的 push 和 pop 均摊时间复杂度为？
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
48. 判断出栈序列合法性：入栈序列为 1,2,3,4，以下哪个出栈序列不可能？
A. 4,3,2,1
B. 1,2,3,4
C. 3,1,2,4
D. 2,1,4,3
49. 浏览器的前进后退功能使用两个栈，后退栈存储已访问页面，当点击前进时，是从哪里弹出页面？
A. 后退栈
B. 前进栈
C. 当前页面
D. 书签
50. 使用链式栈模拟递归求斐波那契数列 fib(5)，栈中保存的是？
A. 计算出的结果
B. 函数调用帧（参数和返回地址）
C. 全局变量
D. 只有数字 5
51. 若链式栈节点使用 new 动态分配，频繁 push/pop 可能导致什么问题？
A. 编译错误
B. 内存碎片（Memory Fragmentation）
C. 栈溢出
D. 数据竞争
52. 为了避免频繁 new/delete，链式栈可以采用什么设计？
A. 使用静态数组
B. 使用对象池（Object Pool）预分配节点
C. 使用 malloc 代替 new
D. 使用全局变量
53. 使用 std::optional<int> 作为 pop 返回值的目的是？
A. 提高性能
B. 明确表达“可能无值”的语义，避免使用 -1 等魔法数字
C. 必须使用 C++20
D. 自动释放内存
54. 链式栈的 size 成员变量，在 pop 操作中应如何变化？
A. size++
B. size--
C. 不变
D. 重置为 0
55. 若 push 参数为 const T& value，传入一个临时对象时，会发生？
A. 编译报错
B. 临时对象被销毁，节点存储副本（拷贝构造）
C. 节点直接绑定临时对象
D. 性能最优
56. 实现 push 的右值引用版本 push(T&& value) 并配合 std::move，目的是？
A. 减少一次拷贝，直接移动构造节点内部数据
B. 强制参数为右值
C. 避免内存分配
D. 与左值版本无区别
57. 链式栈在深度优先搜索（DFS）中作为辅助结构，其操作特性匹配的是？
A. 先进先出（FIFO）
B. 后进先出（LIFO）
C. 优先级最高先出
D. 随机访问
58. 汉诺塔问题中，三根柱子用栈模拟，移动规则的核心是？
A. 只能移动最大的盘子
B. 小盘子必须在大盘子之上
C. 可以任意移动
D. 一次移动两个盘子
59. 计算字符串括号最大嵌套深度时，遇到左括号执行 push，遇到右括号执行 pop，最大深度指的是？
A. 栈的容量
B. 栈曾经达到的最大 size
C. 栈的最小 size
D. 栈顶元素值
60. 若链式栈的 top 指针被意外修改为 NULL 但 size 不为 0，会导致？
A. 内存泄漏
B. 程序崩溃
C. 无法访问已入栈元素（内存泄漏）
D. 自动修复
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第三部分：双向链表与循环链表（链式列表 / LIST）—— 第 61 - 90 题
61. 双向链表节点包含 prev 和 next。在节点 p 之后插入节点 s，正确操作顺序是（先处理 s 的指针）？
A. s->prev = p; s->next = p->next; p->next->prev = s; p->next = s;
B. p->next = s; s->prev = p; s->next = p->next;
C. s->next = p; s->prev = p->prev;
D. p->prev = s; s->next = p;
62. 在双向链表中删除已知节点 p（非头尾哑节点），操作是？
A. p->prev->next = p->next; p->next->prev = p->prev; delete p;
B. p->prev = p->next;
C. p->next = p->prev;
D. delete p;
63. 在已知节点 p 的情况下，双向链表的前驱插入（在 p 前插入 s）时间复杂度为？
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
64. 删除双向链表头节点（有哑头 dummy）时，需要更新的指针数量是？
A. 1 个
B. 2 个
C. 3 个
D. 4 个
65. 反转双向链表的核心是？
A. 只反转 next 指针
B. 交换每个节点的 prev 和 next 指针
C. 头尾交换即可
D. 删除所有节点重建
66. 双向链表的正向迭代器执行 ++ 操作，底层实现是？
A. ptr = ptr->prev;
B. ptr = ptr->next;
C. ptr = ptr;
D. ptr = NULL;
67. 反向迭代器执行 ++（实际向前移动），底层是？
A. ptr = ptr->next;
B. ptr = ptr->prev;
C. 调用 std::reverse_iterator
D. 无法实现
68. 若双向链表的 end() 迭代器指向哑尾节点，则遍历判断条件通常为？
A. it != end()
B. it->next != NULL
C. it != begin()
D. 使用计数器
69. 在循环链表中，判断是否遍历完一圈的条件是？
A. p == NULL
B. p->next == NULL
C. p == head
D. p->data == -1
70. 循环链表（无头节点）为空的条件是？
A. head == NULL
B. head->next == head
C. head == head->next
D. head == NULL 或 (head && head->next == head) 取决于定义
71. 约瑟夫环问题中，删除报数为 m 的节点后，下一次报数应从哪个节点开始？
A. 被删除节点的前驱
B. 被删除节点的后继
C. 头节点
D. 任意节点
72. 在有序循环链表中插入新节点，需要处理的核心边界是？
A. 插入到末尾时，要维护头尾循环
B. 不需要特殊处理
C. 只需插入到头部
D. 禁止插入
73. 循环链表的长度计算，若 head 不为空，终止条件为？
A. while(p != head)
B. while(p->next != head)
C. while(p->next != NULL)
D. for(int i=0; i<100; i++)
74. 实现 LRU 缓存时，哈希表存储的是 key 到 节点指针 的映射，其作用是？
A. 快速判断 key 是否存在并获取节点位置（O(1)）
B. 排序 key
C. 备份数据
D. 统计访问次数
75. LRU 缓存中，当缓存满时，需要删除哪个节点？
A. 头节点（最新）
B. 尾节点（最久未使用）
C. 中间节点
D. 随机节点
76. 使用双向链表实现双端队列（Deque），push_front 的时间复杂度为？
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
77. 扁平化多级双向链表（LeetCode 430）的核心思路是？
A. 使用栈保存每层的下一个节点，深度优先遍历
B. 使用队列广度优先
C. 递归反转
D. 拆分为多个单链表
78. std::list（双向链表）与 std::vector 相比，以下哪个操作 std::list 更快？
A. 随机访问 operator[]
B. 在中间位置插入元素
C. 遍历元素
D. 排序
79. std::list::splice 操作的作用是？
A. 复制节点
B. 将另一个链表的节点转移（剪切）到当前链表，不复制不分配
C. 合并排序
D. 删除重复元素
80. std::list::sort 底层使用的算法是？
A. 快速排序
B. 归并排序（迭代归并）
C. 插入排序
D. 堆排序
81. std::list 的迭代器在插入元素时，哪些迭代器会失效？
A. 所有迭代器
B. 被插入位置的迭代器
C. 没有任何迭代器失效
D. 尾迭代器
82. std::forward_list（单向链表）相比 std::list，节省的空间主要是？
A. 数据域
B. 一个指针（prev）
C. 头节点
D. 尾节点
83. 自定义双向链表类，若想支持 C++11 范围 for 循环，必须实现哪些成员函数？
A. push_back 和 pop_back
B. begin() 和 end() 返回迭代器
C. size() 和 empty()
D. operator[]
84. 在双向链表中交换两个不相邻节点，需要修改多少个指针的指向？
A. 2 个
B. 4 个
C. 6 个
D. 8 个（涉及前后节点共 4 个节点，每个改 2 个指针）
85. 双向链表的归并排序中，找到中间节点的方法是？
A. 计算长度再遍历一半
B. 使用快慢指针
C. 使用哈希表
D. 随机选择
86. 将有序双向链表转换为平衡二叉搜索树（BST），需要选取哪个节点作为根？
A. 头节点
B. 尾节点
C. 中间节点
D. 随机节点
87. 若双向链表带有哑头节点（Dummy Head），插入第一个有效节点时，dummy->next 和 newNode->prev 的关系是？
A. dummy->next = newNode; newNode->prev = dummy;
B. newNode->prev = dummy; dummy->next = newNode;
C. 无需设置 prev
D. A 和 B 都可以，但 B 顺序更安全
88. 循环链表实现“音乐播放列表”时，“随机播放”（打乱）的最有效方式是？
A. 将节点复制到数组，打乱数组，重建链表
B. 交换链表节点中的数据域（不修改指针）
C. 使用哈希表
D. 反转链表
89. 如果双向链表的 prev 指针在插入时赋值顺序错误（例如先修改了 p->next 导致丢失 p->next->prev），最可能的结果是？
A. 内存泄漏
B. 链表断裂或形成环
C. 程序立即崩溃
D. 值被覆盖
90. 关于链式列表（双向链表）的内存占用，说法正确的是？
A. 每个节点比单链表多占用一个指针大小的内存
B. 比单链表少占用内存
C. 和单链表一样
D. 占用内存是单链表的两倍
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
答案部分（共 90 题）
1. A
2. B
3. C
4. A
5. C
6. B
7. C
8. B
9. B
10. C
11. C
12. B
13. B
14. B
15. D
16. B
17. B
18. A
19. A
20. C
21. B
22. A
23. B
24. A
25. C
26. B
27. C
28. B
29. B
30. C
31. A
32. A
33. A
34. A
35. B
36. B
37. B
38. B
39. A
40. B
41. B
42. A
43. B
44. B
45. B
46. B
47. A
48. C
49. B
50. B
51. B
52. B
53. B
54. B
55. B
56. A
57. B
58. B
59. B
60. C
61. A
62. A
63. A
64. B
65. B
66. B
67. B
68. A
69. C
70. A
71. B
72. A
73. A
74. A
75. B
76. A
77. A
78. B
79. B
80. B
81. C
82. B
83. B
84. D
85. B
86. C
87. D
88. B
89. B
90. A
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
打个广告：点此进入
单链表、链式栈、链式队列核心知识点汇总
