数据结构试题：第七章的练习.doc

数据结构复习题：图 单选题 1、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_____倍。 A,1/2 B,1 C,2 D,4 2、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_____。 A,n B, n+1 C,n-1 D,n+e 3、具有n个顶点的无向完全图，边的总数为_____条。 A,n-1 B,n C,n+1 D,n*(n-1)/2 4、在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于_____ 。 A,i+j B,i-j C,1 D,0 5、在n个结点的线索二叉树中,线索的数目为______. A,n-1 B,n C,n+1 D,2n 6、在二叉排序中,凡是新插入的结点,都是没有______的. A孩子 B关键字 C平衡因子 D赋值 7、深度为5的二叉树至多有_______个结点. A,16 B,32 C,31 D,10 8、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为_________。 A,s B,s-1 C,s+1 D,n 9、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为_________。 A,s B,s-1 C,s+1 D,2s 10、在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为_________。 A,n B,e C,n+e D,2e 11、在一个具有n个顶点的无向完全图中，所含的边数的_________。 A,n B,n(n-1) C,n(n-1)/2 D,n(n+1)/2 12、在一个具有n个顶点的有向完全图中，所含的边数为_________。 A,n B,n(n-1) C,n(n-1)/2 D,n(n+1)/2 13、在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为_________。 A,k B,k+1 C,k+2 D,2k 14、对于一个具有n个顶点的无向连通图，它留念的连通分量的个数为_________。 A,0 B,1 C,n D,n+1 15、若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用_________次深度优先于搜索遍历的算法。 A,k B,1 C,k-1 D,k+1 16、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为_________。 A,n B,n*e C,e D, 2*e 17、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为_________。 A,n B,n*e C,e D,2*e 18、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为_________ A,n B,2n C,e D,2e 19、在一个无权图的邻接表表示中，每个边结点至少包含_________域。 A,１ B,２ C,３ D,４ 20、对于一个有向图，若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为_________ A,k1 B,k2 C,k1-k2 D,k1+k2 21、对于一个有向图，若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为_________。 A,k1 B,k2 C,k1-k2 D,k1+k2 22、对于一个无向图，下面_________说法是正确的。 A,每个顶点的入度等于出度 B,每个顶点的度等于其入度出度之和 C,每个顶点的入度为０ D,每个顶点的出度为０ 23、在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的_________。 A,出边数 B入边数 C度数 D度数减１ 24、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行深度优先搜索，得到的顶点序