数据结构练习(答案) 8.doc

一、单项选择题在一个具有n个顶点的有向图中,若所有顶点的出度数之和为s,则所有顶点的入度数之和为(A)。 -1 +1 ,若具有e条边,则所有顶点的度数之和为(D)。 +e ,所含的边数为(C)。 (n-1) (n-1)/2 (n+1)/2在一个具有n个顶点的有向完全图中,所含的边数为(B)。 (n-1) (n-1)/(n+1)/2在一个无向图中,若两顶点之间的路径长度为k,则该路径上的顶点数为(B)。 +1 +2 ,它包含的连通分量的个数为(B)。 +1若一个图中包含有k个连通分量,若要按照深度优先搜索的方法访问所有顶点,则必须调用(A)次深度优先搜索遍历的算法。 -1 +1若要把n个顶点连接为一个连通图,则至少需要(C)条边。 +1 -1 ,表示边存在的元素(又称为有效元素)的个数为(D)。 ´e ´e在一个具有n个顶点和e条边的有向图的邻接矩阵中,表示边存在的元素个数为(C)。 ´e ´e在一个具有n个顶点和e条边的无向图的邻接表中,边结点的个数为(D)。 ´e ´e在一个具有n个顶点和e条边的有向图的邻接表中,保存顶点单链表的表头指针向量的大小至少为(A)。 ,每个边结点至少包含(B)域。 ,若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为(B)。 -k2 +k2对于一个有向图,若一个顶点的度为k1,出度为k2,则对应逆邻接表中该顶点单链表中的边结点数为(C)。 -k2 +k2对于一个无向图,下面(A)说法是正确的。 ,每个顶点单链表中结点的个数等于该顶点的(A)。 {(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行深度优先搜索,得到的顶点序列可能为(B)。,B,C,F,D,E ,C,F,D,E,,B,D,C,F,E ,B,D,F,E,C若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行广度优先搜索,得到的顶点序列可能为(D)。,B,C,D,E,F ,B,C,F,D,,B,D,C,E,F ,C,B,F,D,E若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索,得到的顶点序列可能为(A)。,2,5,4,