GESP 七级 · GESP 202312 C++ 七级 第 13 题

用下面的邻接表结构保存一个有向图 $G$，InfoType 和 VertexType 是定义好的类。设 $G$ 有 $n$ 个顶点、$e$ 条弧，则求图 $G$ 中某个顶点 $u$（其顶点序号为 $k$）的度的算法复杂度是（ ）。

typedef struct ArcNode {
    int adjvex;           // 该弧所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条弧的指针
    InfoType *info;       // 该弧相关信息的指针
} ArcNode;
typedef struct VNode {
    VertexType data;      // 顶点信息
    ArcNode *firstarc;    // 指向第一条依附该顶点的弧
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
    int kind;             // 图的种类标志
} ALGraph;

拿到题先盯住‘有向图’和‘邻接表’两个关键词。邻接表里每个顶点的链表只存从它出发的弧，求某个顶点的度（出度）就是顺着这个链表走一遍数节点数，时间复杂度只跟链表里弧的总数有关。

很多考生会惯性思维，把‘度’当成无向图里的总度数，或者误以为要遍历整个顶点表 O(n) 才能找到某条边，从而选错 C 或 D。也有同学纠结于‘度’的定义，在有向图里默认指出的弧数，若题目没特指入度，直接按链表长度算即可，别想复杂。

【考点】邻接表存储结构｜出度统计｜时间复杂度分析

1. 考纲定位

本题考查《GESP 考试大纲》七级“图与树”模块的邻接表结构与遍历复杂度。命题人卡住的是考生对“度”在有向图中通常指“出度”的界定，以及邻接表只存出边导致遍历弧数而非顶点数的核心特征。