GESP 五级 · GESP 202312 C++ 五级 第 5 题

下面的 C++ 代码用于将字符串保存到带头节点的双向链表中，并对重复的计数，然后将最新访问的串的节点放在链头便于查找。横线处应填入代码是（ ）。

typedef struct Node{
    string str;
    int ref;
    struct Node *next, *prev;
}Node;
Node * Insert(Node *pHead, string s)
{
    Node *p = pHead->next;
    Node *q;
    while(p){
        if(p->str == s){
            p->ref++;
            p->next->prev = p->prev;
            p->prev->next = p->next;
            break;
        }
        p=p->next;
    }
    if(!p) {
        p = new Node;
        p->str = s;
        p->ref=0;
        p->next = p->prev = NULL;
    }
    ________________________________
    pHead->next = p, p->prev = pHead;
    return pHead;
}

这题考带头节点的双向链表插入。拿到题先别急着写代码，脑子里过一遍链表结构：头节点后面跟着数据节点。插入新节点 p 时，p 要插在头节点和原来的第一个数据节点之间。关键就是：原来的第一个节点（pHead->next）到底存不存在？如果链表是空的，pHead->next 就是 NULL，这时候千万别去动它的 prev 指针，否则直接崩。所以填空的核心就是加个判断，确认后面有节点再改指针。

最容易栽跟头的就是 C 选项。很多同学觉得代码写简洁就好，直接写了 p->next = pHead->next, pHead->next->prev = p;。看似逻辑通顺，但完全忽略了链表可能为空的情况。当链表为空时，pHead->next 是空指针，程序试图访问空指针的 prev 成员，立刻触发段错误（Segmentation Fault），程序直接崩溃。A 选项用 if(pHead) 判断，但 pHead 是形参，函数调用时传进来的指针永远非空，这个条件恒为真，属于画蛇添足，没抓到问题的本质。D 选项说会触发异常，这是概念混淆，C++ 里指针越界是运行时错误，不是抛出异常，除非你自己写了 try-catch，否则就是直接挂掉。只有 B 选项，先判断 pHead->next 是否为空，不为空才去修改指针，这才是链表操作的标准姿势。

【考点定位】 这道题出自 GESP 五级数据结构模块，核心考查双向链表的插入操作，特别是带头节点链表在空链表和已有链表两种状态下的指针调整逻辑。命题人专门设计这个坑，就是要区分考生是否真正理解链表操作的边界条件。

【概念拆解】 双向链表由节点结构体组成，每个节点有 str（字符串）、ref（引用计数）以及 next 和 prev 两个指针。带头节点意味着链表最前面有一个不存数据的哨兵节点，它的 next 指向第一个真实数据节点，prev 指向 NULL。插入新节点 p 时，p 应该位于头节点和原来的第一个数据节点之间。因此，p 的 next 要指向原来的第一个节点，而原来的第一个节点的 prev 要指向 p。

【命题视角与思考心法】 拿到这道题，不要一上来就盯着横线看，要先看上下文。函数 Insert 接收头节点指针 pHead 和新字符串 s。前面已经遍历链表，找到了重复节点（直接自增引用并移除）或者没找到（创建新节点 p）。现在 p 已经准备好了，需要把它插到头节点后面。

思考路径应该是： 1. 确定插入位置：头节点 pHead 和原第一个节点 pHead->next 之间。 2. 执行指针操作：p->next = pHead->next; pHead->next->prev = p; pHead->next = p; 3. 检查前提条件：第二步里的 pHead->next->prev 这一句，要求 pHead->next 必须非空。如果链表是空的，pHead->next 就是 NULL，访问它的 prev 就会崩溃。 4. 结论：必须加一个判断，确认 pHead->next 存在后再执行调整操作。

【逐空推演】 横线处需要填入的是插入新节点 p 后，将其与链表其他节点连接起来的代码。根据上面的分析，正确的逻辑分支应该是：如果 pHead->next 不为空，才执行指针修改；如果为空，跳过这一步（因为后面 pHead->next = p 会把 p 设为新的头节点，不需要改 prev）。

看选项： A. if(pHead) { ... }：pHead 是函数参数，传入时必然非空，这个 if 永远成立，属于无效判断，排除。 B. if(pHead->next) { p->next = pHead->next, pHead->next->prev = p; }：先判断原第一个节点是否存在，存在则执行插入逻辑。完美符合需求。 C. p->next = pHead->next, pHead->next->prev = p;：没有判断，直接访问 pHead->next->prev。如果链表为空，pHead->next 为 NULL，访问 NULL->prev 导致段错误。这是典型的“裸奔”写法，必错。 D. 触发异常：C++ 不会自动抛异常，只会崩溃，描述错误。

所以正确答案只能是 B。

【避坑指南】 链表题最大的坑就是空指针。在操作任何指针指向的节点成员之前，务必确认该指针非空。这道题里，pHead->next 就是那个“可能为空”的指针。很多同学会被 C 选项的简洁性迷惑，觉得多写一个 if 很啰嗦，但在链表操作中，啰嗦是安全的，省略才是致命的。记住：链表操作永远要先检查指针有效性。

【考频与趋势】 回顾历年真题数据，字符串、结构体、指针与链表是 GESP 五级的常客。其中链表考点在 2024 年爆发式增长（26 题），2025 年回落至 16 题，2026 年预测为 10 题，整体呈高位震荡后回归常态的趋势。带头节点的双向链表插入是链表模块中最基础也最容易出错的题型之一，过去三年（2023-2025）在 GESP 五级中几乎每年都有涉及，尤其是结合字符串或引用计数的综合题。命题人似乎特别喜欢在“插入”和“删除”这两个动作上挖空，考察学生对指针关系的动态理解。

【未来预测】 基于 2024 年链表题量激增（26 题）以及 2025 年略有回落（16 题）的数据，结合 GESP 五级对数据结构基础掌握的高要求，可以合理预测 2026 年链表相关题目数量会保持在 10 题左右的水平，但题型会更加灵活。可能会出现更多结合双向链表与字符串处理、引用计数更新的综合题，或者在链表操作中加入更复杂的指针调整逻辑（如链表合并、反转等）。因此，备考时不仅要熟练掌握基础的插入、删除操作，更要注重对指针移动过程的细致推演，特别是边界情况（空链表、单节点链表）的处理。