首页 › 题库 › GESP编程能力等级认证 › 3.1 图的概念

GESP-C++七级 题库

共 80 道题 ,第 3 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 3.1 图的概念 清除
41 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点,还需哪种结构存放结点以实现遍历?(   )

A

双向栈

B

队列

C

哈希表

D

堆

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
42 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

学生在读期间所上的某些课程中需要先上其他的课程,所有课程和课程间的先修关系构成一个有向图 G ,有向边 <U, V> 表示课程 U 是课程 V 的先修课,则要找到某门课程 C 的全部先修课下面哪种方法不可行?(   )

A

BFS搜索

B

DFS搜索

C

DFS+BFS

D

动态规划

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
43 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

用下面的邻接表结构保存一个有向图 G , InfoType 和 VertexType 是定义好的类。设 G 有 n 个顶点、e 条弧,则求图 G 中某个顶点 u (其顶点序号为 k )的度的算法复杂度是(   )。

A

O(n)

B

O(e)

C

O(n+e)

D

O(n+2*e)

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
44 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

给定一个简单有向图 G ,判断其中是否存在环路的下列说法哪个最准确?(   )

A

BFS更快

B

DFS更快

C

BFS和DFS一样快

D

不确定

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
45 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

从顶点 v1 开始遍历下图 G 得到顶点访问序列,在下面所给的 4 个序列中符合广度优先的序列有几个?(   )

{v1 v2 v3 v4 v5} , {v1 v2 v4 v3 v5} , {v1 v4 v2 v3 v5} , {v1 v2 v4 v5 v3}

A
4
B
3
C
2
D
1
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
46 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

求两个长度为 序列的最长公共子序列(LCS)长度时,可以使用滚动数组将空间复杂度从优化到。

A
对
B
错
答案与解析
正确答案:对
使用动态规划求解最长公共子序列时,状态转移依赖于前一行和当前行的值。通过滚动数组技术,仅保留当前行和上一行的状态,将二维DP表压缩为两个一维数组或单个一维数组循环更新,从而减少空间占用。每次遍历中,依据序列元素是否相等更新当前状态,覆盖旧行数据以实现空间复用。该方法将空间复杂度由O(mn)降至O(n),其中m和n分别为两序列长度。
题目详情
47 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

使用邻接矩阵存储一个有 个顶点、 条边的图,对该图进行一次完整的BFS遍历,时间复杂度为。

A
对
B
错
答案与解析
正确答案:错
确定图的顶点数n和边数m;获取邻接矩阵存储结构,其规模为n×n;BFS遍历从起始顶点开始,使用队列管理待访问顶点;每轮取出队首顶点,标记为已访问;遍历该顶点在邻接矩阵中的整行,查找所有邻接且未访问的顶点并加入队列;每一行的检查耗时O(n),最多处理n个顶点;总时间由访问所有顶点和检查所有矩阵元素决定;矩阵中每个元素被访问一次,共n²次操作;最终时间复杂度由顶点数n决定。
题目详情
48 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一个包含V个顶点的连通无向图,其任何一棵生成树都恰好包含 V-1条边。

A
对
B
错
答案与解析
正确答案:对
分析连通无向图的生成树定义,明确生成树是极小连通子图且包含图中所有顶点。根据图论基本性质,生成树中不存在环路,且任意两个顶点间有唯一路径。若生成树边数少于V-1,则无法连通所有顶点;若多于V-1,则必然形成环路。因此生成树的边数与顶点数之间存在确定关系。
题目详情
49 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

在无向图中,所有顶点的度数之和等于边数的两倍。2025.12-7

A
对
B
错
答案与解析
正确答案:错
分析无向图中每个边连接两个顶点,每条边对两个顶点的度数各贡献1。统计所有顶点的度数时,每条边被计算两次。将所有顶点的度数相加,总和来源于每条边的两次贡献。由此可得度数总和与边数之间存在固定倍数关系。通过枚举图中边与顶点的关联方式,可验证每条边在度数总和中对应两个单位增量。
题目详情
50 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

题 一棵有N个节点的完全二叉树,则树的深度为+1。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
51 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

对 n 个元素的数组进行快速排序,最差情况的时间复杂度为 O(n log n)。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
52 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

如果将城市视作顶点,公路视作边,将城际公路网络抽象为简单图,可以满足城市间的车道级导航需求。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
53 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

邻接表和邻接矩阵都是图的存储形式。为了操作时间复杂度考虑,同一个图可以同时维护两种存储形式。( )

A
对
B
错
答案与解析
正确答案:对

 两种维护方式并不冲突。(图结构的存储)

题目详情
54 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

在 n 个元素中进行二分查找,平均时间复杂度是 O(logn),但须要事先进行排序。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
55 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时,时间复杂度更低;邻接矩阵在判断两个顶点之间是否有边时,时间复杂度更低。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
56 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一个图中,每个顶点表达一个城市,连接两个顶点的边表达从一个城市到达另一个城市的一种交通方式。这个图可以用来表达交通网络,且是简单有向图。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
57 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

埃氏筛法和欧拉筛法都是使用筛法思想生成素数表的算法,欧拉筛法的时间复杂度更低。

A
对
B
错
答案与解析
正确答案:对

埃氏筛法的时间复杂度是O(n log logn),欧拉筛法是O(n)。

题目详情
58 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一个图,不管是否连通,都可以使用深度优先搜索算法进行遍历。

A
对
B
错
答案与解析
正确答案:对

与连通性无关。对于非连通图,遍历完一个连通分量后,可以在未访问的节点中选择新的起点,继续进行DFS,直到所有节点都被访问。

题目详情
59 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一个图中,每个结点表达一个人,连接两个结点的边表达两个结点对应的人相互认识,则这个图可以用来表达社交网络

A
对
B
错
答案与解析
正确答案:对

图属于网状结构可以表示社交网络。

题目详情
60 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

唯一分解定理(算术基本定理)指出,每个大于1的自然数都可以唯一地分解成若干个素数的乘积。因此,我们可以很容易的对给定的自然数 n 进行质因数分解,时间复杂度仅为O(log(n))。

A
对
B
错
答案与解析
正确答案:错

对n进行质因数分解的时间复杂度为O(sqrt(n)

题目详情