数据结构4: 图

ID: 9829

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

bitworld

标签>

CSP

初赛

1.单选题 [NOIP提高组2014/CSP-S2019] 以下哪些结构可以用来存储图 {{ select(1) }}

邻接矩阵
栈
邻接表
二叉树

2.单选题 [GESP202312【8级】] 使用邻接矩阵表达 n 个顶点的有向图，则该矩阵的大小为 {{ select(2) }}

n*(n+1)
n*n
n*(n-1)
n*(n-1)/2

3.单选题 [GESP202403【8级】] 使用邻接表表达一个无向简单图，图中包含 v 个顶点、 e 条边，则该表中边节点的个数为 {{ select(3) }}

v*(v-1)
v*v
2*e
e

4.单选题 [CSP-J2022] 考虑由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在多少个非零元素 {{ select(4) }}

N−1
N
N+1
N^2

5.单选题 [GESP202312【8级】] 下面的程序使用出边的邻接表表达有向图，则下列选项中哪个是它表达的图

6.单选题 [GESP202406【7级】] 如下图所示的邻接矩阵（inf表示无穷大），表示的是下列哪个选项中的图

7.单选题 [NOIP普及组2014] 有向图中每个顶点的度等于该顶点的 {{ select(7) }}

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

8.单选题 [NOIP提高组2014] 在无向图中，所有顶点的度数之和是边数的多少倍 {{ select(8) }}

9.单选题 [NOIP普及组2016] 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有多少个顶点 {{ select(9) }}

10.单选题 [GESP样题【7级】] 4个结点的简单有向图，最多可以有多少条边 {{ select(10) }}

11.单选题 [GESP202312【8级】] N个顶点的有向完全图（不带自环）有N*(N-1)/2条边 {{ select(11) }}

正确
错误

12.单选题 [GESP202403【8级】] N个顶点的无向完全图有N*(N-1)条边 {{ select(12) }}

正确
错误

13.单选题 [GESP202403【7级】] 一个简单有向图有10个结点、30条边。再增加多少条边可以成为完全图 {{ select(13) }}

14.单选题 [GESP样题【7级】] 一个简单有向图有20个结点，假设图中已经存在300条边，请问增加多少条边可以成为完全图 {{ select(14) }}

15.单选题 [NOIP普及组2011] 无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它共有多少条边 {{ select(15) }}

16.填空题 [NOIP提高组2011] 平面图是可以画在平面上、且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至多有6条边，如右图所示。那么，5个顶点的平面图至多有________条边

17.单选题 [GESP202312【6级】] 深度优先搜索（DFS，Depth First Search的简写）属于图算法，其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次 {{ select(17) }}

正确
错误

18.单选题 [GESP样题【7级】] 简单有向图的深搜结果和广搜结果一样 {{ select(18) }}

正确
错误

19.单选题 [GESP202406【7级】] 非连通图不能使用广度优先搜索算法进行遍历 {{ select(19) }}

正确
错误

20.单选题 [GESP202312【7级】] 图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历 {{ select(20) }}

双向栈
队列
哈希表
堆

21.单选题 [CSP-J2022] 以下对数据结构的表述不恰当的一项为 {{ select(21) }}

图的深度优先遍历算法常使用的数据结构为栈
栈的访问原则后进先出，队列的访问原则是先进先出
队列常常被用于广度优先搜索算法
栈与队列存在本质不同，无法用栈实现队列

22.单选题 [GESP202312【7级】] 学生在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成一个有向图 G，有向边 <U, V> 表示课程 U 是课程 V 的先修课，则要找到某门课程 C 的全部先修课下面哪种方法不可行 {{ select(22) }}

BFS搜索
DFS搜索
DFS+BFS
动态规划

23.单选题 [GESP202406【7级】] 图的存储和遍历算法，下面说法错误的是 {{ select(23) }}

图的深度优先搜索和广度优先搜索对有向图和无向图都适用
图的深度优先搜索和二叉树的先序遍历道理是不一样的
图的深度优先搜索需要借助栈来完成
邻接表中，顶点v对应的链表中的边结点数目正好是顶点v的度

24.单选题 [GESP202312【7级】] 小杨在开发画笔刷小程序（applet），操作之一是选中黄颜色，然后在下面的左图的中间区域双击后，就变成了右图。这个操作可以用图的泛洪算法来实现

正确
错误

25.单选题 [GESP202309【6级】] 如果节点数为N，广度搜索算法的最差时间复杂度为O(N) {{ select(25) }}

正确
错误

26.单选题 [NOIP提高组2015/CSP-S2020/GESP202406【8级】] 具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为 {{ select(26) }}

O(n2)
O(e2)
O(ne)
O(n+e)

27.单选题 [NOIP普及组2013] 以 A 0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能的是

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

28.单选题 [NOIP提高组2013] 以 A0 作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是

29.单选题 [CSP-J2021] 以a为起点，对下边的无向图进行深度优先遍历，则b,c,d,e 四个点中有可能作为最后一个遍历到的点的个数为

30.单选题 [GESP202406【7级】] 下列选项中，哪个可能是下图的深度优先遍历序列

1, 3, 7, 5, 4, 2, 6, 8, 9
9, 4, 2, 1, 3, 5, 7, 6, 8
1, 3, 4, 2, 7, 6, 8, 9, 5
9, 7, 6, 8, 4, 2, 1, 5, 3

31.单选题 [GESP202403【7级】] 下列选项中，哪个可能是下图的深度优先遍历序列

8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9
7, 8, 6, 4, 2, 1, 5, 3, 12, 9, 11, 10
8, 10, 12, 9, 11, 4, 5, 3, 2, 1, 6, 7
7, 8, 10, 9, 11, 12, 4, 5, 1, 2, 3, 6

32.单选题 [GESP202406【7级】] 如下图所示的邻接表结构，表示的是下列哪个选项中的图

33.单选题 [GESP样题【7级】] 阅读以下代码，visited起到的作用是

实现遍历过程
以广度优先的方式记录图中的顶点
存储深搜时节点的访问顺序
能够记录最短路径

34.单选题 [GESP样题【8级】] 下面是图的深度遍历的代码，则横线处可以填入：if(vis[x]) return

正确
错误

35.填空题 [NOIP普及组2018] 输入：10 7 1 4 3 2 5 9 8 0 6 输出：

36.单选题 [GESP202312【7级】] 从顶点 v1 开始遍历下图 G 得到顶点访问序列，在下面所给的 4 个序列中符合广度优先的序列有几个

37.单选题 [GESP样题【7级】] 下面有向图中的数字表示顶点序号，则从1号顶点出发的BFS遍历的输出顶点序列可能是

1 4 3 2
1 4 2 3
1 3 2 4
1 2 4 3

38.单选题 [NOIP提高组2012] 从顶点A0出发，对有向图进行广度优先搜索（BFS）时，一种可能的遍历顺序是A0，A1,A2，A3，A4

图A
图B
图C
图D

39.单选题 [NOIP普及组2004] 在下图中，从顶点出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次

A 点
B 点
C 点
D 点
E 点

40.单选题 [GESP样题【7级】] 判断图是否连通可以用深搜实现 {{ select(40) }}

正确
错误

41.单选题 [GESP202403【8级】] 可以使用深度优先搜索算法判断图的连通性 {{ select(41) }}

正确
错误

42.单选题 [GESP202312【7级】] 广度优先搜索（BFS）能够判断图是否连通 {{ select(42) }}

正确
错误

43.单选题 [GESP202312【8级】] 判断图是否连通只能用广度优先搜索算法实现 {{ select(43) }}

正确
错误

44.单选题 [GESP202406【8级】] 要判断无向图的连通性，在深度优先搜索和广度优先搜索中选择，深度优先的平均时间复杂度更低 {{ select(44) }}

正确
错误

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

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

46.单选题 [CSP-S2021] G是一个非连通简单无向图（没有自环和重边），共有36条边，则该图至少有多少个点 {{ select(46) }}

47.单选题 [GESP202403【7级】] 一个连通的简单无向图，共有28条边，则该图至少有多少个顶点 {{ select(47) }}

48.单选题 [CSP-S2019] G 是一个非连通无向图（没有重边和自环），共有 28 条边，则该图至少有多少个顶点 {{ select(48) }}

49.单选题 [NOIP提高组2016/GESP202312【7级】] G 是一个非连通简单无向图，共有 28 条边，则该图至少有多少个顶点 {{ select(49) }}

50.单选题 [NOIP普及组2013] 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图，至少要删去其中的多少条边

51.单选题 [NOIP提高组2013] 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有5个顶点、8条边的连通图。若要使它不再是连通图，至少要删去其中的多少条边

52.单选题 [CSP-J2020] 有10个顶点的无向图至少应该有多少条边才能确保是一个连通图 {{ select(52) }}

53.单选题 [NOIP提高组2017] 由四个不同的点构成的简单无向连通图的个数是 {{ select(53) }}

54.单选题 [NOIP普及组2018] 由四个没有区别的点构成的简单无向连通图的个数是 {{ select(54) }}

55.单选题 [NOIP提高组2017] 如下图所示，A到 B是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让 A,B不连通，最小代价是（________）（2分），最小代价的不同方案数是（_______）（3分）。（只要有一条删除的边不同，就是不同的方案）

56.单选题 [GESP202406【7级】] 下面关于图的说法正确的是 {{ select(56) }}

在无向图中，环是指至少包含三个不同顶点，并且第一个顶点和最后一个顶点是相同的路径
在有向图中，环是指一个顶点经过至少另⼀个顶点到自身的路径
在有向图中，如果任意两个顶点之间都存在一条边，则这个图一定是强连通图
在有向图中，所有顶点的入度和出度的总和就是图的边数的两倍

57.单选题 [NOIP普及组2009] 已知 n 个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点)，则该图中最少有多少条有向边 {{ select(57) }}

n
n+1
n-1
n*(n-1）

58.单选题 [NOIP提高组2009] 若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}，{1，0，1}，{0，1，0}}，假定在具体存储中顶点依次为: v1，v2，v3。关于该图，下面的说法哪些是正确的 {{ select(58) }}

该图是有向图
该图是强连通的
该图所有顶点的入度之和减所有顶点的出度之和等于1
从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的

59.单选题 [CSP-S2022] 强连通图的性质不包括 {{ select(59) }}

每个顶点的度数至少为1
任意两个顶点之间都有边相连
任意两个顶点之间都有路径相连
每个顶点至少都连有一条边

60.单选题 [NOIP普及组2011] 对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，右图就是一个强连通图。事实上，在删掉边后，它依然是强连通的

61.单选题 [GESP样题【7级】] 在下面的有向图中，强连通分量有多少个

62.单选题 [NOIP普及组2010/NOIP提高组2010] 关于拓扑排序，下面说法正确的是 {{ select(62) }}

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

63.单选题 [CSP-J2023] 考虑一个有向无环图，该图包含4条有向边：(1,2),(1,3),(2,4)和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序 {{ select(63) }}

4,2,3,1
1,2,3,4
1,2,4,3
2,1,3,4

64.单选题 [NOIP提高组2004/NOIP普及组2004] 某大学计算机专业的必修课及其先修课程如下表所示：请你判断下列课程安排方案哪个是合理的

C0, C1, C2, C3, C4, C5, C6, C7
C0, C1, C2, C3, C4, C6, C7, C5
C0, C1, C6, C7, C2, C3, C4, C5
C0, C1, C6, C7, C5, C2, C3, C4
C0, C1, C2, C3, C6, C7, C5, C4

65.填空题 [NOIP提高组2009] 拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G.，则u在线性序列中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为

66.单选题 [CSP-S2023] 如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边

67.单选题 [GESP202403【8级】] 关于生成树的说法，错误的是 {{ select(67) }}

一个无向连通图可以有多个生成树
一个无向图，只要连通，就一定有生成树
n个顶点的无向完全图，有nn-2棵生成树
n个顶点的无向图，生成树包含n-1条边

68.单选题 [GESP样题【8级】] 连通图G有n个顶点m条边，须删除m-n+1条边后才能变成一棵生成树 {{ select(68) }}

正确
错误

69.单选题 [NOIP提高组2014] 设 G 是有6个结点的完全图，要得到一颗生成树，需要从G中删去多少条边 {{ select(69) }}

70.单选题 [NOIP普及组2017/NOIP提高组2017/CSP-J2021] 设 G 是有n个结点、m条边(n ≤m)的连通图，必须删去G的多少条边，才能使得G变成一棵树 {{ select(70) }}

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

71.单选题 [GESP样题【8级】] 最小生成树的权值是指生成树所有边的权值之和最小 {{ select(71) }}

正确
错误

72.单选题 [NOIP普及组2005] 平面上有五个点A(5,3), B(3,5), C(2,1), D(3,3), E(5,1)。以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。以下哪条边不是图G的最小生成树中的边 {{ select(72) }}

73.单选题 [NOIP提高组2005] 平面上有五个点A(5,3), B(3,5), C(2,1), D(3,3), E(5,1)。以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。图G的最小生成树中的所有边的权值综合为 {{ select(73) }}

8
7+√5
9
6+√5
4+2√2 +√5

74.单选题 [GESP202312【8级】] 一个无向图包含n个顶点，则其最小生成树包含多少条边 {{ select(74) }}

n-1
n
n+1
最小生成树可能不存在

75.单选题 [NOIP普及组2015/NOIP提高组2015] 6个顶点的连通图的最小生成树，其边数为 {{ select(75) }}

76.填空题 [NOIP普及组2008/NOIP提高组2008] 有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_____________ {{ input(76) }}

77.填空题 [NOIP普及组2014] 如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是______ {{ input(77) }}

78.填空题 [NOIP提高组2014] 如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是_____ {{ input(78) }}

79.单选题 [CSP-S2021] 有如下的有向图，节点为A,B,⋯,J，其中每条边的长度都标在图中。则节点A到节点J的最短路径长度为 {{ select(79) }}

80.单选题 [GESP202403【8级】] 下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为

81.单选题 [GESP202403【7级】] 下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为 {{ select(81) }}

#CSPJKG74. 数据结构4: 图

还没有账户？

登录