GESP 六级 · GESP 202312 C++ 六级 第 25 题

同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。（ ）

这题其实是在考你对‘排序复杂度’和‘链表遍历’关系的直觉。拿到题先想：冒泡排序到底在做什么？是两两比较并交换相邻元素，跟容器是数组还是链表没关系。再看链表：单链表从头走到尾要 n 步，双向链表虽然能往回走，但比较和交换相邻节点时，你依然得先定位到这两个节点，定位本身就要 O(n)。所以总步数都是 O(n²)，序列长度相同时，两种链表上的冒泡排序时间复杂度完全相同。

很多学生会误以为双向链表能‘省步骤’，觉得交换两个节点只需要改几个指针，比数组快多了，从而下意识选‘错误’。其实冒泡排序的瓶颈不在‘交换代价’，而在‘比较次数’。无论哪种链表，比较相邻元素都要先找到它们，找的过程就是 O(n)，交换也是 O(1) 的指针操作。题目里‘简单冒泡排序’是关键词，任何对数组与链表对比的常识都会在这里失效，别被‘双向’两个字带偏。

【考点】单链表遍历｜双向链表遍历｜冒泡排序复杂度

这题考的是 GESP C++语言与数据结构‘链表操作’模块，命题人特意用‘两种链表’来卡住考生对链表遍历与指针操作的本质理解，想看看你是不是真的懂链表，还是只背了数组上的冒泡排序。

解题思维：冒泡排序的核心动作就是两两比较并交换相邻元素。在单链表上，要比较第 i 个和第 i+1 个节点，你得从头遍历到 i，这需要 O(i) 步；交换时又要再遍历一次去改指针，还是 O(i)。整个排序要做 O(n²) 次比较，所以总复杂度是 O(n²)。双向链表看起来更强大，可以往回走，但‘比较相邻元素’这件事并没变：你依然得先定位到那两个节点。定位本身就要 O(n) 步（从任意一端走到目标位置），交换同样是 O(1) 的指针操作。因此，无论单链表还是双向链表，冒泡排序的总步数都是 O(n²) 量级。

陷阱拆解：错误选项 B 诱使考生把‘双向链表能更快交换’当通解，忽略了冒泡排序的瓶颈在于‘比较次数’而非‘交换代价’。链表交换的指针操作虽比数组略多，但仍是常数级，不改变二次方阶。题目里‘简单冒泡排序’是关键词，任何对数组与链表对比的常识都会在这里失效。

反命题思维：若把‘冒泡排序’换成‘插入排序’，同样 O(n²)；换成‘归并排序’则变成 O(n log n)。命题人想让你确认的是：对链表上的基础排序，遍历与交换的开销不会改变阶数。

考频与趋势：链表相关题目在题库中占比很高，共 81 题，覆盖 7 个考试级别。逐年来看，2024 年达到峰值 26 题，2025 年回落至 16 题，2026 年又回升到 10 题，说明链表仍是高频考点。分赛事看，GESP 五级 42 题、六级 11 题、七级 7 题，GESP 六级近年出题密度明显上升，2023 年单年就有 6 题涉及链表，2024 年更是 26 题，六级考生需格外重视链表操作的理解与实现。

预测：基于数据，未来 GESP 六级仍会持续考查链表与排序的结合，尤其是‘不同排序算法在链表上的复杂度对比’这类概念题。命题人可能会换用‘选择排序’或‘插入排序’来制造干扰，但核心逻辑不变：遍历开销决定阶数。暂无足够依据预测具体题型，但‘链表 + 排序复杂度’这一组合大概率仍是六级重点。