首页 › 题库 › GESP编程能力等级认证 › 3 图的定义及遍历

GESP-Python七级 题库

共 20 道题 · 按题型筛选,点「查看答案」核对解析
章节 3 图的定义及遍历 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

一棵深度为 6(根节点深度为1)的完全二叉树,节点总数最少有( )。

A

31

B

32

C

63

D

64

答案与解析
正确答案:B
完全二叉树的深度由根节点开始计算,深度为k时,前k-1层是满二叉树结构。第k层至少存在一个节点。前k-1层的节点总数为2^(k-1)-1。将深度k=6代入,前5层节点总数为2^5 - 1 = 31。第6层至少有1个节点,因此总节点数为前5层节点数与第6层最小节点数之和。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

下面程序中,函数 query 的时间复杂度是( )。

def query(n, a, x): 
    left = 0 
    right = n 
    while left < right: 
        mid = left + (right - left) // 2 
        if a[mid] >= x: 
            right = mid 
        else: 
            left = mid + 1 
    if left == n: 
        return -1 
    return left 
if __name__ == "__main__": 
    n = 10 
    x = 3 
    num = [1, 2, 2, 3, 3, 4, 5, 5, 6, 7] 
    print(query(n, num, x))
A

O(1)

B

O(log n)

C

O(n)

D

O(n log n)

答案与解析
正确答案:B
函数 query 使用 while 循环控制 left 和 right 的范围,每次迭代将搜索区间缩小一半。循环条件依赖 left 和 right 的关系,且每次更新 mid 为 (left + right) // 2。当 mid 满足特定条件时,right 被赋值为 mid,否则 left 被更新为 mid + 1。循环持续直到 left 不小于 right。过程中仅进行常数时间的操作,无嵌套循环或递归。元素比较和指针移动均在固定时间内完成。整个执行路径由区间长度决定,每次将问题规模近似减半。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

有5个字符,它们出现的次数分别为2次、2次、3次、3次、5次。现在要用哈夫曼编码的方式来为这些字符进行编码,最小加权路径长度WPL(每个字符的出现次数 它的编码长度,再把每个字符结果加起来)的值为( )。

A

30

B

34

C

43

D

47

答案与解析
正确答案:B
将每个字符的出现次数作为叶子节点的权值,构建哈夫曼树。每次选择权值最小的两个节点合并为一个新节点,新节点的权值为两者之和,直至所有节点合并成一棵树。每个字符的编码长度等于其对应叶子节点在树中的深度。最小加权路径长度WPL为各叶子节点的权值与其深度乘积的总和。计算过程基于贪心策略,优先合并较小权值节点,以确保高频字符拥有较短编码路径。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

一个简单无向图 G 有36条边,且每个顶点的度数都为4,则图 G 的顶点个数为( )。

A

9

B

12

C

18

D

36

答案与解析
正确答案:C
利用图论中边数与顶点度数的关系,所有顶点的度数之和等于边数的两倍。设顶点个数为 n,每个顶点的度数为 4,则总度数为 4n。根据握手定理,总度数等于 2 倍边数,即 4n = 2 × 36。通过代数运算可得 n 的值。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

假设一个算法时间复杂度的递推式是(n为正整数),和T(0)=1,那么这个算法的时间复杂度是( )。

A

B

C

D

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

下面哪一个可能是下图的深度优先遍历序列( )。

A

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

B

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

C

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

D

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

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

下面这个有向图的强连通分量的个数是(  )。

A

3

B

4

C

5

D

6

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

下面程序的时间复杂度是()

def func(n):
	for i in range(n):
		for j in range(i, n):
			print(i, j)
A
n
B
n*log(n)
C
n的平方
D
n的立方
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

给定一个无向图,图的节点编号从 0 到 n-1,图的边以邻接表的形式给出。编写的一个python程序,使用深度优先搜索(DFS)遍历该图,并输出遍历的节点顺序。

下面程序中横线处应该填写的是()

def dfs(graph, start, visited=None):
	if visited is None:
		visited = set()
	visited.add(start)
	print(start, end=" ")

	for neighbor in graph[start]:
		if neighbor not in visited:
			________________

graph = {
	0: [1, 2],
	1: [0, 3, 4],
	2: [0, 5],
	3: [1],
	4: [1, 5],
	5: [2, 4]
}

print("DFS 遍历顺序:")
dfs(graph, 0)
A
dfs(graph, neighbor, visited)
B
dfs(graph+1, neighbor, visited)
C
dfs(graph, neighbor)
D
dfs(graph+1, visited)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

以下代码的时间复杂度是多少?

def fib(n):
	if n <= 1:
		return n
	return fib(n - 1) + fib(n - 2)
A
n
B
n的平方
C
2的n次幂
D
log(n)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

以下代码的时间复杂度是多少?

def fib(n, memo={}):
	if n <= 1:
		return n
	if n not in memo:
		memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
	return memo[n]
A
n
B
n的平方
C
2的n次幂
D
log(n)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

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

A
对
B
错
答案与解析
正确答案:对
分析无向图中每个边连接两个顶点,每条边对两个顶点的度数各贡献1。统计所有顶点的度数时,每条边被计算两次。将所有顶点的度数相加,总和来源于每条边的两次贡献。通过累加顶点度数的方式,可推导出总和与边数之间的数量关系。该关系由边与顶点连接方式的结构性决定。
题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

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

A
对
B
错
答案与解析
正确答案:错
BFS遍历从起始顶点开始,使用队列管理待访问顶点。邻接矩阵为V×V二维数组,每行对应一个顶点,元素表示顶点间是否存在边。算法首先初始化所有顶点为未访问状态。将起始顶点标记为已访问并入队。当队列非空时,出队一个顶点,遍历其在邻接矩阵中的对应行,查找所有与其相邻且未访问的顶点,将它们标记为已访问并入队。每个顶点被访问一次,每条边在矩阵中被检查一次。由于需扫描整个矩阵以检测邻接关系,总时间开销由顶点数V和边的检查次数决定。
题目详情
14 判断题 偏易 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

在图像处理或游戏开发中,泛洪(flood fill)算法既可以用BFS实现,也可以用DFS实现。

A
对
B
错
答案与解析
正确答案:对
泛洪算法通过访问连通区域内的所有可达节点实现填充操作。BFS使用队列结构逐层遍历相邻像素,按距离起始点的远近顺序处理节点。DFS使用栈结构(或递归调用)沿路径深入访问,直到无法继续后再回溯处理其他分支。两种遍历方式均可覆盖相同连通区域,只要访问条件和边界判断一致,就能达到相同的填充效果。实现时需记录已访问节点以避免重复处理。
题目详情
15 判断题 偏易 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

使用链地址法处理冲突的哈希表,当所有元素都映射到同一个槽位时,查找操作的最坏时间复杂度为O(n),其中 n 为元素个数。

A
对
B
错
答案与解析
正确答案:对
链地址法中,哈希表每个槽位对应一个链表存储映射到该位置的元素。当所有元素经哈希函数计算后均落入同一槽位时,该槽位的链表长度为n。查找操作需遍历该链表直至找到目标元素或遍历完毕。遍历长度为n的链表所需时间与n成正比。时间复杂度由链表遍历过程中的比较次数决定。
题目详情
16 判断题 偏易 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

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

A
对
B
错
答案与解析
正确答案:对
分析连通无向图的生成树定义,明确生成树是极小连通子图且包含所有顶点。根据图论基本性质,生成树中不存在环,且任意两个顶点间有唯一路径。考虑构建生成树的过程:从单个顶点开始,每加入一个新顶点需添加一条边以保持连通性,新增顶点数为V-1时,对应新增边数即为V-1。验证该边数与顶点数的关系是否在所有可能构造方式下均成立,不依赖具体算法或实例。考察是否存在其他边数配置仍满足生成树条件的可能性。
题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

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

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
18 简答题 偏难 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

学习小组

3.2.3 输出格式

输出一行,一个整数,表示所有划分方案中,学习小组综合讨论积极度之和的最大值。

3.2.4.1 输入样例 1

4
2 1 3 2
1 5 6 3

3.2.4.2 输出样例 1

12

3.2.4.3 输入样例 2

8
1 3 2 4 3 5 4 6
0 2 5 6 4 3 3 4

3.2.4.4 输出样例 2

21

答案与解析
参考答案
getint = lambda: map(int, input().split())
getints = lambda: list(getint())

# 同学数量
n = int(input())
# 按照讨论积极程度从小到大排序,方便后面计算转移方程
c = sorted(getints())
# 不同分组的基础讨论度
a = [0] + getints()
# 用来进行动态规划的数组
# f[j][k]表示在当前已经用掉k个学生,且包含了j个人数不为1的组的情况下的最大积极度
# 我们在这里使用了滚动数组优化,所以没有题解中的i维度
f = [[0] * (n + 1) for _ in range(n + 1)]

# 考虑人数最少的组不少于i个人的情况
for i in range(n, 0, -1):
    # j表示分成了多少个组
    # 一共就n个人,所以组的数量绝对不大于n//i+1
    for j in range(1, n // i + 1):
        # 如果最后一个小组刚刚好有i个人,因为之前的组都有至少i个人,所以新加入的组应该选择第j大和第j小的元素作为极大极小值
        diff = c[n - j] - c[j - 1] if i > 1 else 0
        if diff < 0:
            break
        # 假设我们考虑用掉了k个学生,只需要考虑k>=i的情况即可
        for k in range(i, n + 1):
            # 判断最后一个小组如果刚刚好有i个人能否比
            f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff)

print(max(f[i][n] for i in range(n + 1)))


题目详情
19 简答题 偏难 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

图上移动

题目描述

小 A 有一张包含n 个结点与 m条边的无向图,结点以1,2,...,n 标号。小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点 i(1≤i≤n ),小 A 想知道从结点i 出发恰好移动1,2,...,k步之后,小 A 可能位于哪些结点。由于满足条件的结点可能有很多,你只需要求出这些结点的数量。

输入格式

第一行,三个正整数 n,m,k,分别表示无向图的结点数与边数,最多移动的步数。

接下来m 行,每行两个正整数 ui,vi,表示图中的一条连接结点 ui与vi 的无向边。

输出格式

共n 行,第 i行(1≤i≤n  )包含 k个整数,第j 个整数(1≤j≤k  )表示从结点 i出发恰好移动j 步之后可能位于的结点数量。


输入样例

4 4 3
1 2
1 3
2 3
3 4

输出样例

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

数据范围

对于20 % 的测试点,保证k=1 。

对于另外20 % 的测试点,保证 1≤n≤50,1≤m≤50 。

对于所有测试点,保证 1≤n≤500,1≤m≤500 ,1≤k≤20 ,1≤ui,vi≤n。

答案与解析
参考答案
n, m, k = map(int, input().split())
to = [[] for i in range(n + 2)]
for i in range(m):
	x, y = map(int, input().split())
	to[x].append(y)
	to[y].append(x)

f = [[[False] * (n + 2) for _ in range(n + 2)] for __ in range(k + 2)]

for i in range(1, n + 1):
	f[0][i][i] = True

for t in range(1, k + 1):
	for x in range(1, n + 1):
		for y in range(1, n + 1):
			if f[t - 1][x][y]:
				for z in to[y]:
					f[t][x][z] = True

for i in range(1, n + 1):
	Ans = []
	for t in range(1, k + 1):
		ans = 0
		for j in range(1, n + 1):
			ans += (f[t][i][j] == True)
		Ans.append(str(ans))
	print(' '.join(Ans))
题目详情
20 简答题 偏难 GESP编程能力等级认证 ·GESP-Python七级 · 3 图的定义及遍历

等价消除

题目描述

小 A 有一个仅包含小写英文字母的字符串 S。

对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字符串是可以被等价消除的。

小 A 想知道 S有多少子串是可以被等价消除的。

一个字符串 S'是S 的子串,当且仅当删去 S的某个可以为空的前缀和某个可以为空的后缀之后,可以得到 S'。

输入格式

第一行,一个正整数|S| ,表示字符串S 的长度。

第二行,一个仅包含小写英文字母的字符串 S。

输出格式

一行,一个整数,表示答案。


输入样例 1

7
aaaaabb

输出样例 1

9

输入样例 2

9
babacabab

输出样例 2

2

数据范围

对于20 % 的测试点,保证S 中仅包含 a 和 b 两种字符。

对于另外20 % 的测试点,保证 1≤|S|≤2000。

对于所有测试点,保证 1≤|S|≤2*105 。

答案与解析
参考答案
n = int(input())
s = input()
state, cnt, ans = 0, {}, 0
cnt[0] = 1
for i in range(n):
	c = ord(s[i]) - ord('a')
	state ^= (1 << c)
	if state not in cnt:
		cnt[state] = 0
	ans += cnt[state]
	cnt[state] += 1
print(ans)
题目详情