图
作业6
一、单项选择题
1．采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（ ）。（南方名校经典试题）
A）先序遍历 B）中序遍历 C）后序遍历 D）层次遍历
2．一个n个顶点的连通无向图，其边的个数至少为（ ）。（南方名校经典试题）
A）n-1 B）n C）n+1 D）nlogn
3．下面（ ）可以判断出一个有向图中是否有环（回路）？（北方名校典试题）
A）求关键路径 B）拓扑排序
C）求最短路径 D）前面都不正确
二、综合题
1．设有带权无向图G如下图所示：（南方名校经典试题）
带权无向图G
试给出：
（1）从V1开始的深度优先遍历；
（2）从V1开始的广度优先遍历；
（3）从V1开始执行的普里姆（Prim）算法过程中所选边的序列。
2．对如下图所示的有向图G试给出各顶点的入/出度。（南方名校经典试题）
有向图G
3．给出如下图所示的所有拓扑有序序列。（南方名校经典试题）
有向图示意图
4．在有向图G中顶点只有编号的信号，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写算法完成下列功能：（北方名校经典试题）
（1）编写算法实现由邻接矩阵A建立有向图G的邻接表存储结构；
（2）编写算法判断有向图G是否有根，若有，则打印所有根结点的值。
注：此题较难，选作。
因篇幅问题不能全部显示，请点此查看更多更全内容