数据结构练习5

1、数据结构练习(图)一、选择题1 .在一个具有n个顶点的有向完全图中，所含的边数为_C_。A.nB.n(n-l) C.n(n-1)/2D.n(n+1)/2在一个有向图中，所有顶点的度之和与图的边数之比为B。A. 1： 1B. 2： 1C. 1： 2D.不确定一个具有n个顶点的无向图，要确保是一个连通图，至少需要A条边。A. n-1B. nC. n+1D. n/2在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的C倍oA. 4B. 2C. 1D. 1/2对于一个有向图，若一个顶点的度为k1，出度为k2,则对应邻接表中该顶点在表结点 中出现的结点数为 A。A.k1B.k2C.k1-k2D.k

2、1 + k2在无向图G的邻接矩阵A中，若Ai,j等于1，则Aj,i等于 旦A.无穷大B. 1 C. 0 D.无法确定在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的 大小至少为e_。A. nB. 2nC. eD. 2eG是一个非连通无向图，共有28条边，则该图至少有个顶点。A.16B. 9C. 8D. 7在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的_日_。A.出边数日.入边数C.度数D.度数减1对某个无向图的邻接矩阵来说，下列叙述错误的是 D 。第i行与第i列上的非零元素的总数等于顶点vi的度数矩阵中的非零元素个数等于图中的边数的2倍第i行上的非零

3、元素个数和第i列上的非零元素个数一定相等矩阵是一个nxn的方阵(n为图的顶点数)对于B ，从它的某个顶点出发进行一次深度或广度优先搜索就可以访问到该图的每 一个顶点。A.无向图 B.有向图C.无向连通图D.任何一个图在有向图的邻接表存储结构中，顶点v在表结点中出现的次数等于B。A.顶点v的度B.顶点v的出度C.顶点的入度D.依附于顶点v的弧数二、填空题已知某无向图的二元组表示为DS=(K, R), K= a,b,c,d,e,f ，R=r， r=(a,b),(a,c),(a,d),(b,e),(d,e),(c,d),(c,e),(c,f)，则顶点 c 的度为 4,它的所有邻 接点为a,d,e,f

4、。一 个有向图的顶点集为a,b,c,d,e,f,边集为va,c,va,e,vc,f,vd,c,ve,b, ,则出度为o的顶点个数为_2，入度为1的顶点个数为5。一个有n个顶点的无向完全图有n(n-1)/2条边。在一个具有n个顶点的无向图中，要 连通全部顶点至少需要山1条边。n个顶点的有向强连通图至少有n-1条边，最多有 n(n-1) 条弧。若一个无向图 有10条边，若要使该无向图是一个非连通图，至少需要 12 个顶点:若要使该无向图是一个连通图，至多可以有_个顶点。在有向图的邻接矩阵中，第i行中1的个数是第i个顶点的出度，第i列中1的个数 是第i个顶点的入度。在无向图的邻接矩阵中，第i行(列)

5、中、1的个数是第i个顶点的度。 图结构的数据元素之间存在多对多的关系。对稠密图来说，应选用邻接矩阵存储结 构较合适。若一个有向图采用逆邻接表存储结构，则求该图顶点的入度、入边邻接点最方便，以上 的叙述是正确(正确/错误)。图的广度优先遍历算法使用了数据结构队列操作。三、应用题1.设有向图 G = (V,E)，V=V0,V1,V2,V3,V4,V5，E=, , , , , , 请给出图G的邻接矩阵存储结构示意图。请写出顶点V3的入度与出度。入度2；出度1请按照上述邻接矩阵存储结构，写出从顶点V0出发分别进行深度优先和广度优先搜索 所得到的顶点访问序列；深度：V0V2V3V1V5V4广度：V0V1

6、V2V4V5V32.已知一个有向图的邻接链表存储结构如下：根据有向图的深度优先遍历算法，写出从顶点v1出发所得到的顶点序列。V1V4V5V3V6V2根据有向图的广度优先遍历算法，写出从顶点v1出发所得到的顶点序列。V1V2V4V5V3V6三、算法填空题 1.下列算法是对具有n个顶点的邻接表表示的有向图G,求序号为num的顶点的度。阅读 该算法，在空白处填入适当的语句，使该算法完整。设邻接表结构定义如下：typedef struct nodeint adjvex;struct node *next; edgenode;typedef edgenode *adjlistMaxVertexNum;算法为：int Degree( adjlist G, int n, int num) /求n个顶点的有向图G中顶点号为num的顶点的度，并返回该值。int sum1=0, sum2=0;edgenode *p;p= Gnum.next;while (p! =