练习题 -- 数据结构与算法 >> 图
共 7 题
第 1/7 题
★
以下关于图的说法错误的是：
正确答案: D
【数据结构-图】
题目：关于图的说法错误的是：
✅ 正确答案：D.邻接矩阵一定对称
错误选项：
❌ A.连通图至少n-1条边
❌ B.有向图邻接矩阵不一定对称
❌ C.稀疏图适合邻接表
📖 解析：无向图邻接矩阵对称，有向图不一定。
题目：关于图的说法错误的是：
✅ 正确答案：D.邻接矩阵一定对称
错误选项：
❌ A.连通图至少n-1条边
❌ B.有向图邻接矩阵不一定对称
❌ C.稀疏图适合邻接表
📖 解析：无向图邻接矩阵对称，有向图不一定。
第 2/7 题
★
图的广度优先遍历BFS使用数据结构：
正确答案: B
【数据结构-图】
题目：图的BFS使用什么数据结构？
✅ 正确答案：B.队列
错误选项：
❌ A.栈
❌ C.堆
❌ D.树
📖 解析：BFS用队列，DFS用栈。
题目：图的BFS使用什么数据结构？
✅ 正确答案：B.队列
错误选项：
❌ A.栈
❌ C.堆
❌ D.树
📖 解析：BFS用队列，DFS用栈。
第 3/7 题
★★
用Prim算法求最小生成树，以下描述正确的是：
正确答案: C
【数据结构-图】
题目：Prim算法的描述正确的是：
✅ 正确答案：C.Prim每次选最小边连接已选和未选集
错误选项：
❌ A.Prim适合稀疏图
❌ B.Prim时间复杂度O(eloge)
❌ D.Prim用并查集判环
📖 解析：Prim从点出发，每次选连接已选和未选的最小边。O(n²)。
题目：Prim算法的描述正确的是：
✅ 正确答案：C.Prim每次选最小边连接已选和未选集
错误选项：
❌ A.Prim适合稀疏图
❌ B.Prim时间复杂度O(eloge)
❌ D.Prim用并查集判环
📖 解析：Prim从点出发，每次选连接已选和未选的最小边。O(n²)。
第 4/7 题
★★
以下关于拓扑排序的说法，正确的是：
正确答案: C
【数据结构-图】
题目：拓扑排序说法正确的是：
✅ 正确答案：C.每次输出入度0的顶点
错误选项：
❌ A.有环图也可以
❌ B.结果唯一
❌ D.用于无向图
📖 解析：拓扑=每次输出入度0顶点并删除出边。要求DAG，结果可能不唯一。
题目：拓扑排序说法正确的是：
✅ 正确答案：C.每次输出入度0的顶点
错误选项：
❌ A.有环图也可以
❌ B.结果唯一
❌ D.用于无向图
📖 解析：拓扑=每次输出入度0顶点并删除出边。要求DAG，结果可能不唯一。
第 5/7 题
★
Kruskal算法在选择边时，判断是否会形成环使用：
正确答案: B
【数据结构-图】
题目：Kruskal判环使用：
✅ 正确答案：B.并查集
错误选项：
❌ A.DFS
❌ C.邻接矩阵
❌ D.哈希表
📖 解析：并查集维护连通分量。两端点在同一集合→加入会成环→跳过。
题目：Kruskal判环使用：
✅ 正确答案：B.并查集
错误选项：
❌ A.DFS
❌ C.邻接矩阵
❌ D.哈希表
📖 解析：并查集维护连通分量。两端点在同一集合→加入会成环→跳过。
第 6/7 题
★
具有n个顶点的连通图至少有多少条边？
正确答案: B
【数据结构-图】
题目：n个顶点的连通图最少边数：
✅ 正确答案：B.n-1
错误选项：
❌ A.n
❌ C.n(n-1)/2
❌ D.n+1
📖 解析：连通图最少=n-1（树形结构）。完全图最多=n(n-1)/2。
题目：n个顶点的连通图最少边数：
✅ 正确答案：B.n-1
错误选项：
❌ A.n
❌ C.n(n-1)/2
❌ D.n+1
📖 解析：连通图最少=n-1（树形结构）。完全图最多=n(n-1)/2。
第 7/7 题
★
n个顶点的有向完全图边数为：
正确答案: B
【数据结构-图】
题目：n个顶点的有向完全图边数：
✅ 正确答案：B.n(n-1)
错误选项：
❌ A.n(n-1)/2
❌ C.n²
❌ D.n-1
📖 解析：有向完全图每对顶点两条弧→n(n-1)。
题目：n个顶点的有向完全图边数：
✅ 正确答案：B.n(n-1)
错误选项：
❌ A.n(n-1)/2
❌ C.n²
❌ D.n-1
📖 解析：有向完全图每对顶点两条弧→n(n-1)。