有向图 G=(V,E) 采用邻接表存储，求某点入度的时间复杂度为？

A. O(|V|) B. O(|E|) C. O(|V|)·|E|) D. O(|V|+|E|)

[tag_link]

正确答案：D

【解析】 在邻接表存储中，求某点的入度需要检查所有顶点的出边链表，统计指向该点的边数。这需要访问所有∣V∣个顶点以及所有∣E∣条边，因此时间复杂度为O(∣V∣+∣E∣)。由于O(∣V∣+∣E∣)与O(max(∣V∣,∣E∣))等价，故选项 D 正确。其他选项均不能完整描述该时间复杂度。