选择题（10分/题）
1对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（）
A.4
B.3
C.2
D.1
2关于下图所示的邻接矩阵，如果节点A的出度为2，则描述错误的是（）
A节点A到节点C的最短路径长度为4
B节点A的度为3
C节点A到C只有两条路径
D节点E的度为2
3无向图G=（V，E），其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历，得到的顶点序列正确的是（）
Aa,b,e,c,d,f
Ba,c,f,e,b,d
Ca,e,b,c,f,d
Da,e,d,f,c,b
4如果G是一个共有n个顶点的有向完全图，则该图中共有（）条弧
A（n2-1）/2
Bn（n-1）/2
Cn（n-1）
Dn2-1
5图中有关路径的定义是（）
A.由顶点和相邻顶点序偶构成的边所形成的序列
B.由不同的顶点形成的序列
C.由不同边所形成的序列
D.上述定义都不是
应用题（50分/题）
使用Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）请回答下列问题∶
（1）对下图G，从顶点A开始求G的MST，依次给出按算法选出的边。
（2）图G的MST是唯一的吗?
（3）对任意的带权连通图，满足什么条件时，其MST是唯一的?
大师兄有话说：
图这一章主要重要的重点在于对于图的算法的手动模拟。
例如DFS、BFS、Prim算法，Kruskal算法求最小生成树、Djakarta求最短路径、拓扑排序、关键路径等等都是常考题型，需要熟练掌握！
自主命题的学校通常以为风向标，甚至在考题中直接选用真题，所以适量的练习真题，对于自主命题的考生也是很有必要的。
每日测一测，你满分了吗？研究生er
答疑群交流群2：
预览时标签不可点收录于话题#个上一篇下一篇