2014xdf计算机7月9日重新汇总数据结构第

【答案解析】当所有n个顶点都在某一个有向环（有向回时，形成一个强连通图，条数少于n则不能构成环，不再是强连通图。【答案解析】对于有向图，顶点v的度分为入度和出度，入度是以顶点v为终点的边的数目；出度是以顶点v为起点的边的数目，顶点v的度等于起入度和出度之和。因此，此有k1-k2。对于有向图的邻接表表示，边表的结点数就等于图中边数，每个单把与ki相邻接的顶点放在一个链表中，即边表中存放的是入度边而不是出度边。边结点数为k1-k2的第i行第j列的元素是否为零即可。栈图问的顶点的邻接点优先于后被的顶点的邻接点”的特征，所以需使用队列已被的路径长度为1，2，…，n的顶点。[B]拓扑排序[C] n个顶点和n-1条边的极小连通子图。[A]G的一棵最小代价生成树的代价未必小于图G的其他任何一棵生成树的代价边时，即使该边的权值最小也不会出现在任何解中，因此B不正确；因为图中每边的权值n-1C正确；一的，因此D不正确。【答案解析】本题主要考查Kruskal[A]v1，v2，v5，v7[B]v1，v8)4，(v5，v6)4，(v5，v7)2，(v6，v10)4，(v7，v9)5，(v8，v9)2，(v9，v10)2}【答案解析】求出该AOE其邻接点未完;已且其邻接点已完。下面用0，1，2表示这三种状态。前面已对应程序中v的状态为1，而u是正的顶点，若找出u的下一邻接点的状态为1，前面已提到，若DFS（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正的顶点，若 找出u的下一邻接点的状态【解答】用Cif(i==start)printf(“\n”);elsePrint(i,start);break;}}voidDFS(int{visited[v]=1;for(j=1;j<=n;j++)ifg[v][j]!=0存在边ifif(!visited[j])DFS(j);else{}}for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(!visited[i])}可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的算法思想及描述。注：圈就是回路。nn-1条边，最小生成树是边上通，继续向下删；直到剩n-1条边为止。nn-1条边，最小生成仍连通，继续向下删；直到剩n-1条边为止。typedefstructintj；nodevoidSpnTree(AdjListg用“破圈法”求解带权连通无向图的一棵最小代价生成树scanf("%d%d",&e,&n);//输入边数和顶点数while(edge[j].w<edge[0].w)edge[j+1]=edge[j--];}ifconnect(k)kedge[k].w=0测试下一条边edge[k]，权值置0表示该边被删除}}}connect()DFS或BFS就可遍历完全部结点，否则，因为删除该