B.在顺序栈的入栈操作过程中可能发生上溢现象
C.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的
D.无向图的邻接矩阵一定是对称的
B.在顺序栈的入栈操作过程中可能发生上溢现象
C.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的
D.无向图的邻接矩阵一定是对称的
A、O(n)
B、O(e)
C、O(n+e)
D、O(n2)
【Test-7-2】假设不带权有向图采用邻接表 G 存储,下面算法的功能是: (1)求出图中每个顶点的入度。 (2)求出图中出度为0的顶点数。 请在空白处填入正确的语句。 void InDs(ALGraph *G) //求出图 G 中每个顶点的入度 { ArcNode *p; int A[MAX_VERTEX_NUM], i; //A 存放各顶点的入度 for(i = 0; ______①_______; i++) //A 中元素置初值 0 ______②_______; for(i = 0; i < G->n; i++) { //扫描所有头结点 p = _________③___________; while(p != NULL) { //扫描边结点 _______④_________; //表示 i 到 p->adjvex 顶点有一条边 p = p->nextarc; } } printf("各顶点入度:\n"); //输出各顶点的入度 for(i = 0; i < G->n; i++) printf(" 顶点%d:%d\n", i, A[i]); } void ZeroOutDs(ALGraph *G) //求出图 G 中出度为 0 的顶点数 { int i, n; ArcNode *p; printf("出度为 0 的顶点:"); for(i = 0; i < G->n; i++) { //扫描所有头结点 p = ________⑤__________; n = 0; while(p != NULL) { //扫描边结点 n++; //累计出边的数 ________⑥__________; } if(n == 0) //输出出边数为 0 的顶点编号 printf("%2d", i); } }
B.矩阵中的非零元素的个数等于图中的边数的2倍。
C.第i行非零元数量和第i列非零元数量相等
D.矩阵是一个n*n的方阵
(a)A中任何两个顶点在G中都不是相互邻接的;(b)B中任何两个顶点在G中都不是相互邻接的。例如,图8-34就是二部图。对V(G)的一个划分可能是A=(0,3,4,6)和B=(1,2,5,7).
(1)试编写一个算法,判断图G是否是二部图。如果图G是二部图,则你的算法应当把项点划分成为具有上述性质的两个互不相交的子集A和B。证明:当用邻接表表示图G时,这个算法的复杂度可以做到O(n+e)。其中n是图G的顶点个数,e是边数。
(2)证明:任何-棵树都是二部图
(3)证明:当且仅当图G不包含奇数条边的回路时.它是二部图。
(1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上,则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥,将把图分割成两个连通分量。
(2)编写一个时间复杂度为O(n+e)的使用邻接表表示的算法,判断连通图G中是否有桥,若有。输出这样的桥。
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!