图 - Problem Detail - lizikid

ID: 20

Type: Objective

Difficulty: 8

Uploaded By:

Tags>

初赛选择题

Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人A 向他(她)的朋友B 分享了某张照片，那么B 就可以对该照片进行评论；如果B 评论了该照片，那么他(她)的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论(除非A 也向他(她)分享了该照片)。现在Lucia 已经上传了一张照片，但是她不想让Jacob 看见这张照片，那么她可以向以下朋友（）分享该照片。

{{ select(1) }}

Dana, Michael, Eve
Dana, Eve, Monica
Michael, Eve, Jacob
Micheal, Peter, Monica

有向图中每个顶点的度等于该顶点的（）。 {{ select(2) }}

入度
出度
入度与出度之和
入度与出度之差

在无向图中，所有顶点的度数之和是边数的（）倍。 {{ select(3) }}

0.5
1
2
4

设简单无向图G 有16 条边且每个顶点的度数都是2，则图G 有（）个顶点。 {{ select(4) }}

10
12
8
16

关于拓扑排序，下面说法正确的是（）。 {{ select(5) }}

所有连通的有向图都可以实现拓扑排序
对同一个图而言，拓扑排序的结果是唯一的
拓扑排序中入度为 0 的结点总会排在入度大于 0 的结点的前面
拓扑排序结果序列中的第一个结点一定是入度为 0 的点

设T是一棵有n个顶点的树，下列说法不正确的是（）。 {{ select(6) }}

T有 $n$ 条边
T是连通的
T是无环的
T有 $n-1$ 条边

设G 是有 $n$ 个结点、 $m$ 条边 $(n ≤ m)$ 的连通图，必须删去G 的（）条边，才能使得G 变成一棵树。 {{ select(7) }}

m – n + 1
m - n
m + n + 1
n – m + 1

6个顶点的连通图的最小生成树，其边数为（）。 {{ select(8) }}

6
5
7
4

设G是有6个结点的完全图，要得到一棵生成树，需要从G中删去（）条边。 {{ select(9) }}

6
9
10
15

已知 $n$ 个顶点的有向图，若该图是强连通的(从所有顶点都存在路径到达其他顶点)，则该图中最少有（）多少条有向边？ {{ select(10) }}

$n$
$n+1$
$n-1$
$n*(n-1)$

无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图G有7个顶点，则它共有（）条边。。 {{ select(11) }}

7
21
42
49

对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，右图就是一个强连通图。事实上，在删掉边（）后，它依然是强连通的。

{{ select(12) }}

a
b
c
d

在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。 {{ select(13) }}

1
2
3
4

在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有5个顶点、8条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。 {{ select(14) }}

2
3
4
5

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，12个顶点的二分图至多有（）条边。 {{ select(15) }}

18
24
36
66

对图G中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图G的一个正常着色。正常着色图G所必需的最少颜色数，称为G的色数。那么下图的色数是（）。 {{ select(16) }}

3
4
5
6

G 是一个非连通简单无向图，共有28 条边，则该图至少有（）个顶点。 {{ select(17) }}

10
9
8
7

由四个不同的点构成的简单无向连通图的个数是（）。 {{ select(18) }}

32
35
38
41

由四个没有区别的点构成的简单无向连通图的个数是（）。 {{ select(19) }}

6
7
8
9

以 $A_0$ 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（）。 {{ select(20) }}

$A_0, A_1, A_2, A_3$
$A_0, A_1, A_3, A_2$
$A_0, A_2, A_1, A_3$
$A_0, A_3, A_1, A_2$

具有 $n$ 个顶点， $e$ 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（）。 {{ select(21) }}

$Θ(n^2)$
$Θ(e^2)$
$Θ(ne)$
$Θ(n + e)$

对一个 $n$ 个顶点、 $m$ 条边的带权有向简单图用Dijkstra算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（）。 {{ select(22) }}

$O(mn + n^3)$
$O(n^2)$
$O((m + n) log^n)$
$O((m + n^2) log^n)$

左图给出了一个加权无向图，从顶点 $V_0$ 开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为（）：

{{ select(23) }}

$V_0, V_1, V_2, V_3, V_5, V_4$
$V_0, V_1, V_5, V_4, V_3, V_3$
$V_1, V_2, V_3, V_0, V_5, V_4$
$V_1, V_2, V_3, V_0, V_4, V_5$