GESP 八级 · GESP202609 C++ 八级第 11 题

选择题 · 答案 A · 考点：算法、最短路径

题目

在使用小根堆（优先队列）优化的 Dijkstra 算法中，堆中每个元素通常存储的是（　　）。

答案：A

算法最短路径

看到"小根堆优化 Dijkstra"先想：堆里存什么能让每次弹出当前距离最小的顶点？Dijkstra 核心是维护每个顶点到源点的当前最短距离，用堆加速查找最小距离顶点。因此堆元素必然包含"距离"和"顶点标识"，按距离排序。

选项 B 把"边权"当堆元素，混淆了松弛操作与堆存储；选项 C"入度"是图静态属性，与动态距离无关；选项 D"父结点"是路径重建信息，不在堆中。命题人用这些干扰项测试考生是否真正理解 Dijkstra 的数据结构。

本题考查《GESP 考试大纲》八级"图论与最短路径"模块中的"优先队列优化 Dijkstra 算法"知识点。命题人专门放这道题，是因为绝大多数考生能背出 Dijkstra 流程，却混淆了"堆里存什么"——这是区分"会用算法"和"懂数据结构"的关键卡点。

比如从源点 S 出发，初始堆里只有 (0, S)。弹出 S 后，松弛邻居 V1 得距离 5，堆里新增 (5, V1)；再弹出 V1 松弛 V2 得距离 8，堆里新增 (8, V2)。堆中始终存的是 (距离, 顶点) 对，按距离升序。

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。