中国人民大学 BK138A网络、群体与市场 综合练习题库答案（不含图片）.doc

★网络、群体与市场(BK138A)

模块一图论与社会网络

1、【231347】（单项选择题）关于图论中图的概念，以下叙述（）正确。

A.图中的有向边表示研究对象，结点表示衔接关系

B.图中的点表示研究对象，边表示点与点之间的关系

C.图中任意两点之间必有边

D.图的边数必定等于点数减1

【答案】B

2、【231349】（单项选择题）有15个顶的无向简单图的边数最多是（）。

A.105

B.210

C.21

D.45

【答案】A

3、【231351】（单项选择题）100个顶点的无向星图的最大顶点度是（）。

A.98

B.100

C.99

D.101

【答案】C

4、【231357】（单项选择题）设G是由5个顶点构成的完全图，则从G中删去（）边可以得到树。

A.6

B.5

C.8

D.4

【答案】A

5、【231358】（单项选择题）无向简单图G是棵树，当且仅当（）。

A.G连通且边数比顶点数少1

B.G连通且顶点数比边数少1

C.G的边数比顶点数少1

D.G中没有圈

【答案】A

6、【231359】（单项选择题）下面哪几种图不一定是树（）。

A.无回路的连通图

B.有n个结点，n－1条边的连通图

C.对每对结点间都有通路的图

D.连通但删去任意一条边则不连通的图

【答案】A

7、【231360】（单项选择题）5个节点的无向完全图的边数为（）。

A.5

B.10

C.15

D.20

【答案】B

8、【231361】（单项选择题）设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k＋1，则G中度数为k的节点数是（）。

A.n/2

B.n（n＋1）

C.nk－2m

D.n（k＋1）－2m

【答案】D

9、【231362】（单项选择题）设G=V，E为有向图，V={a，b，c，d，e，f}，E={a，b，b，c，a，d，d，e，f，e}是（）。

A.强连通图

B.单向连通图

C.弱连通图

D.不连通图

【答案】B

10、【231367】（单项选择题）在有n个结点的连通图中，其边数（）。

A.最多有n－1条

B.至少有n－1条

C.最多有n条

D.至少有n条

【答案】B

11、【231373】267839（单项选择题）设无向简单图的顶点个数为n，则该图最多有（）条边。

A.n－1

B.n（n－1）/2

C.n（n＋1）/2

D.2n

【答案】C

12、【231375】（单项选择题）要连通具有n个顶点的有向图，至少需要（）条边。

A.n－1

B.n

C.n＋1

D.2n

【答案】A

13、【231378】（单项选择题）n个结点的完全有向图含有边的数目（）。

A.n*n

B.n（n＋1）

C.n/2

D.n*（n－1）

【答案】B

14、【231381】（单项选择题）在一个无向图中，所有顶点的度数之和等于所有边数（）倍。

A.1/2

B.2

C.1

D.4

【答案】B

15、【231529】（单项选择题）在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。

A.1/2

B.2

C.1

D.4

【答案】C

16、【231533】（单项选择题）连通图G是一棵树，当且仅当G中（）。

A.有些边不是割边

B.所有边都是割边

C.无割边集

D.每条边都不是割边

【答案】B

17、【231542】（单项选择题）考虑下图所示社会网络。回答以下问题。

请问节点A的聚集系数是多少？（聚集系数，clusteringcoefficient，定义为一个节点的邻居互为朋友的概率）（）

A.2/5

B.1/2

C.2/3

D.7/10

【答案】D

18、【231550】（单项选择题）考虑下图所示社会网络。回答以下问题。

若增加一条E-C边，会引起哪些节点聚集系数的变化？（）

A.E，B，C

B.B

C.A，B，W

D.G，A，B，U

【答案】A

19、【231558】（单项选择题）假设你和一些人类学家一起，去一个热带雨林进行调研，在那里30个农民生活在沿着30公里长的河段的一个人烟稀少的地区。每个农民住在占用河岸的1公里长的一块土地，所以他们正好划分完30公里河岸。

（1）假设所有距离不到5公里的农民之间是强关系，对于距离在5-12公里之间的农民，他们之间是弱关系，若两个农民之间距离大于12公里，则他们之间不存在任何关系。按照这样的假设，不难想到可用一个30个节点的网络，表达这些农民之间的关系。每个节点代表一个农民，有些节点之间有边，有些则没有，有些边用s标注，有些则用w标注。问，在上述定义下，是否所有在这个网络中的节点满足强三元闭包性