图论算法基础测试试卷

姓名

学号

关于拓扑排序，下面说法正确的是( )。

广度优先搜索时，需要用到的数据结构是( )。

以(A0)作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是 ( )。

图的邻接关系：

A0连接：A1,A2,A3

A1连接：A0,A3

A2连接：A0,A3

A3连接：A0,A1,A2

把 M 个同样的球放到 N 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法？(用 K 表示)。

例如，M=7，N=3 时，K=8；在这里认为（袋子无区别）是同一种放置方法。

问：M=8，N=5时，K=__。

6 个顶点的连通图的最小生成树，其边数为( )。

以a为起点，对右边的无向图进行深度优先遍历，则 b、c、d、e四个点中有可能作为最后一个遍历到的点个数为（）。

图的边：

a-b，a-c，b-d，d-c，c-e