图形结构题目及答案
一、单项选择题（每题2分，共10题）
1.在图形结构中，连接两个顶点的线称为（）
A.顶点B.边C.路径D.回路
2.具有n个顶点的无向完全图的边数为（）
A.n(n-1)B.n(n-1)/2C.n2D.n
3.以下哪种遍历方式是对图的广度优先遍历（）
A.DFSB.BFSC.拓扑排序D.关键路径法
4.一个有向图的邻接矩阵中，第i行的元素之和表示（）
A.顶点i的入度B.顶点i的出度C.顶点i的度D.边的总数
5.对于连通无向图，生成树的边数是（）
A.顶点数B.顶点数-1C.顶点数+1D.边数-1
6.以下哪种图一定没有回路（）
A.无向图B.有向图C.树D.完全图
7.在图的邻接表存储结构中，每个顶点的链表存储的是（）
A.该顶点的所有邻接顶点B.图的所有顶点C.该顶点的度D.所有边
8.最短路径算法中，用于求单源最短路径的是（）
A.Dijkstra算法B.Floyd算法C.Prim算法D.Kruskal算法
9.一个图的拓扑排序结果（）
A.唯一B.不唯一C.不存在D.只有一个
10.图的深度优先遍历类似于树的（）
A.层次遍历B.先序遍历C.中序遍历D.后序遍历
二、多项选择题（每题2分，共10题）
1.以下属于图的存储结构的有（）
A.邻接矩阵B.邻接表C.十字链表D.顺序存储结构
2.图的遍历方法有（）
A.深度优先遍历B.广度优先遍历C.先序遍历D.层次遍历
3.生成树的特点包括（）
A.连通B.无回路C.包含图的所有顶点D.边数等于顶点数-1
4.以下算法可用于图的最小生成树的有（）
A.Prim算法B.Kruskal算法C.Dijkstra算法D.Floyd算法
5.有向图中，可能存在的路径类型有（）
A.简单路径B.回路C.最短路径D.关键路径
6.图的邻接矩阵的性质有（）
A.对称矩阵（无向图）B.第i行元素和为顶点i的出度（有向图）
C.第i列元素和为顶点i的入度（有向图）D.元素值只能为0或1
7.拓扑排序可应用于（）
A.确定工程完成顺序B.检测有向图中是否存在回路
C.求最短路径D.求关键路径
8.图的连通分量是指（）
A.无向图中的极大连通子图B.有向图中的极大强连通子图
C.连通图的子图D.不连通图中各个连通部分
9.最短路径算法的应用场景包括（）
A.地图导航B.网络传输C.任务调度D.电路布线
10.关于图的度，以下说法正确的是（）
A.无向图顶点的度是其邻接顶点数B.有向图顶点的度等于入度+出度
C.度为0的顶点称为孤立顶点D.图中所有顶点度之和等于边数的2倍
三、判断题（每题2分，共10题）
1.图的邻接矩阵表示法比邻接表表示法占用空间更少。（）
2.深度优先遍历和广度优先遍历对连通图和非连通图都适用。（）
3.无向图的生成树是唯一的。（）
4.Prim算法和Kruskal算法生成的最小生成树一定相同。（）
5.有向图中存在环时，无法进行拓扑排序。（）
6.图的邻接表存储结构中，每个顶点链表的长度等于该顶点的度。（）
7.Dijkstra算法可以求出图中任意两个顶点之间的最短路径。（）
8.一个图的连通分量个数可能为0。（）
9.完全图一定是连通图。（）
10.关键路径是有向无环图中从源点到汇点的最长路径。（）
四、简答题（每题5分，共4题）
1.简述图的邻接矩阵和邻接表存储结构的优缺点。
答案：邻接矩阵优点是直观、方便判断顶点间是否有边，缺点是空间复杂度高；邻接表优点是节省空间，适合稀疏图，缺点是判断顶点间是否有边相对复杂。
2.简述Dijkstra算法的基本思想。
答案：从源点出发，维护一个距离集合，初始源点距离为0，其余为无穷。每次从未确定顶点中选距离最小的顶点，更新其邻接顶点距离，直到所有顶点距离确定。
3.简述拓扑排序的作用。
答案：拓扑排序可确定有向无环图中顶点的先后顺序，常用于工程任务调度等场景，还能检测有向图中是否存在回路，若