CMS专题
填空题在公式V（G）=E–N+2中：E为程序图G中边的总数；N为程序图中结点的总数。V（G）又称为图G的环形（）。
题目
参考答案和解析
相似问题和答案
第1题：
有向图G=(V，E)，其中V={a，b，c，d}，E={a，ba，d，b，c，c，d}，则图G为强连通图。()
第2题：
● McCabe度量法是通过定义环路复杂度，建立程序复杂性的度量，它基于一个程序模块的程序图中环路的个数。计算有向图 G 的环路复杂性的公式为：V(G)=m-n+2，其中 V(G)是有向图 G 中的环路个数，m是 G 中的有向弧数，n 是 G 中的节点数。下图所示程序图的程序复杂度是 （32） 。
（32）
A. 2
B. 3
C. 4
D. 5
第3题：
McCabe度量法计算公式为：V(G=m-n+p，其中V（G是强连通有向图G中的环数;m是G中的弧数;n是G中的节点数;p是G中分离部分的数目）。
此题为判断题(对，错)。
第4题：
设，|V|=n(n＞1)，当且仅当(59)，G=＜V，E＞是强连通图。
A．G中至少有一条路
B．G中至少有一条回路
C．G中有通过每个结点至少一次的路
D．G中有通过每个结点至少一次的回路
解析：本题考查的是图论中的基本知识点。在简单有向图G中，任何一对结点问两者之间是相互可达的，则称这个图是强连通的。如图：A→B只有A到达B，有一次路，但是该图不是强连通的。所以，C错。
第5题：
Mcc：abe度量法是通过定义环路复杂度，建立程序复杂性的度量，它基于一个程序模块的程序图中环路的个数。计算有向图G的环路复杂性的公式为：V(G)=m—n+2，其中V(G)是有向图G中的环路个数，m是G中的有向弧数，n是G中的节点数。下图所示程序图的程序复杂度是( )。
A．2
B．3
C．4
D．5
解析：要采用McCabe度量法度量程序复杂度，需要先画出程序流图，识别有向图中节点数n=8，有向弧数m=7，然后利用环路复杂性计算公式V(G)=m-n+2进行计算，得出程序图的程序复杂度是3。
第6题：
A、G1是G2的子图
B、G1是G2的连通分量
第7题：
设|V|=n(n＞1)，当且仅当______，G=＜V，E＞是强连通图。
A．G中至少有一条路
B．G中至少有一条回路
C．G中有通过每个节点至少一次的路
D．G中有通过每个节点至少一次的回路
A．
B．
C．
D．
解析：在简单有向图G中，任何一对节点间两者之间是相互可达的，则称这个图是强连通的。设|V|=n(n＞1)，当且仅当G中有通过每个节点至少一次的回路，G=V，E＞是强连通图。
对于选项C，例如图“A→B”，即只有A到达B，有一次路，但是该图不是强连通的。因此选项C的说法不能成为强连通图的充要条件。
第8题：
在程序控制流图中，有8条边，6个节点，则控制流程图的环路复杂性V(G)等于(55)。
A．2
B．4
C．6
D．8
解析：本题考查白盒测试中控制流程图的环路复杂性V(G)的计算方法。
其计算方法包括3种：
.V(G)=区域数
.V(G)=判断结点数+1
.V(G)=边-节点+2
第9题：
设有一个无向图G=(V，E)和G′=(V′,E′)，如果G′为G的生成树，则下面不正确的说法是(40)。
A．G′为G的子图
B．G′为G的极小连通子图且V′=V
C．G′为G的一个无环子图
D．G′为G的边通分量
解析：本题考查无向图与其生成树的关系。对于无向图而言，如果无向图G是一个连通图，在对其进行遍历时，一次可以遍历所有顶点，得到的极小连通子图是一棵生成树，树中包含了图的所有顶点，但不一定包含所有的边；如果无向图G是一个非连通图，在对其进行遍历时，得到的是森林，这个森林是由图的连通分量的生成树组成的，森林中也不一定包含图中所有的边。因此，G'不一定为G的边通分量。
第10题：
B.G′是G的一个无环子图
C.G′为G的子图
D.G′为G的连通分量