GESP 八级 · GESP 202312 C++ 八级 第 12 题

下面的程序使用出边的邻接表表达有向图，则下列选项中哪个是它表达的图？（ ）。

#include <iostream>

struct Edge {
    int e;
    Edge * next;
};

struct Node {
    Edge * first;
};

int main() {
    Edge e[5] = {{1, nullptr}, {2, &e[2]},
                 {3, nullptr}, {3, nullptr}, {0, nullptr}};
    Node n[4] = {&e[0], &e[1], &e[3], &e[4]};
    // 其他处理
    return 0;
}


这题考的是邻接表存储有向图，但代码里藏了个‘偷梁换柱’的坑：节点数组 n 并没有按顺序指向 e[0]~e[3]，而是跳着指向了 e[0]、e[1]、e[3]、e[4]。拿到题先别急着画箭头，第一步必须把 n 数组里的指针逐一拆开，确认每个顶点到底挂着哪几条边，这才是解题的钥匙。

最容易栽跟头的地方是默认认为 n[0]~n[3] 对应 e[0]~e[3]，或者看到 e 数组里有两个值都是 3，就以为它们属于同一个顶点。其实命题人故意把 n[2] 指向了 e[3]，把 n[3] 指向了 e[4]，这种索引错位是专门用来考验你是否真的读懂了代码。另外，e[1] 的 next 指向 e[2]，意味着顶点 1 有两条出边，很多考生会漏掉这一条，导致把顶点 1 的边数算少，或者把顶点 2 的边误认为是顶点 1 的。

【考点】图的邻接表存储｜数据结构遍历｜索引映射

1. 考纲定位

GESP 8 级《数据结构与算法》模块。命题人卡住的是考生对‘头结点数组 + 边数组’双数组结构的理解薄弱——很多人背会了邻接表定义，但看到具体实例时，分不清哪个数组存节点、哪个存边，更搞不清索引的对应关系。这题尤其狡猾，它没有按常规顺序排列节点指针，而是故意打乱了 n 数组的指向，用来测试你是否真的读懂了代码，而不是机械地套用模板。