GESP 五级 · GESP 202409 C++ 五级 第 16 题

在操作系统中，需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】数据结构｜环形链表｜进程调度

【解题思维】环形链表的核心特性是尾指针指向头结点，天然形成闭环。命题人把"时间片用完切换进程"对应到"链表遍历完回到起点"，这属于数据结构与系统设计的交叉考点——看到循环需求，第一反应必须是环形结构。通法：任何需要首尾相接的序列（队列、循环播放等），优先考虑环形链表或循环队列，而非普通链表。

【陷阱拆解】错误选项会诱导你用普通链表实现循环（需额外维护指针），或用栈/数组模拟。本题最阴险的是"循环"二字——普通链表无法自动循环，必须手动处理尾节点，而环形链表是标准解法。如果你只背"链表是线性结构"，就会忽略其环形变体，掉进"链表不能循环"的思维定式。

【反命题思维】命题人改题方向：把"环形链表"换成"循环队列"，答案不变；换成"普通链表+递归"，答案仍为A；换成"栈模拟循环"，答案变B。刷到类似题，先问自己："命题人想考我什么？"——数据结构与系统场景的映射关系。