GESP-Python六级 题库

共 132 道题 ,第 7 / 7 页 · 按题型筛选,点「查看答案」核对解析
121 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

二叉搜索树可以是空树(没有任何节点)或者单节点树(只有一个节点),或者多节点。如果是多节点,则左节点的值小于父节点的值,右节点的值大于父节点的值,由此推理,右节点树的值都大于根节点的值,左节点树的值都小于根节点的值。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
122 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 综合练习

5G网络中,5G中的G表示Gigabytes/s,其中 1 GB = 1024 MB。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
123 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.2 哈夫曼树

哈夫曼编码是一种有损压缩算法。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
124 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 综合练习

Python本身并不支持指针和引用语法,因此有关链表等算法或数据结构在Python中不能实现。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
125 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

如果节点数为 ,广度搜索算法的最差时间复杂度为O(N)。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
126 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

二叉搜索树的左右子树也是二叉搜索树。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
127 简答题 偏难 GESP编程能力等级认证 ·GESP-Python六级 · 综合练习

选数


答案与解析
参考答案
# 接受输入
# n
n = int(input())
# 接受a和b的输入
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
# 准备动态规划的数组f
# f[i]的含义如题解所述
f = [0] * (n + 5)
# ans表示目前找到的最大的答案
ans = 0
for i in range(1, n + 1):
    # 比较一下,如果将i加入到下标序列中,那么可能得到的最大序列和为f[i]+a[i],比较这个值和最大的已发现的答案
    ans = max(ans, f[i] + a[i])
    # f[i+b[i]]表示最后一个被选中的下标<=i的情况下能够找到的最大序列和。如果加入a[i]能够让这个值更大,则更新
    if i + b[i] <= n:
        f[i + b[i]] = max(f[i + b[i]], f[i] + a[i])
    # 因为f[i]表示的是i及i以后的下标都能被选中情况下的最大序列和,所以利用f[i]来更新f[i+1]
    f[i + 1] = max(f[i + 1], f[i])
print(ans)
题目详情
128 简答题 偏难 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

完全二叉树

答案与解析
参考答案
n = int(input())
# l[i]:i的左孩子;r[i]:i的右孩子,0为空
l = [0] * (n + 1)
r = [0] * (n + 1)
# mn[u]:u子树中,叶子节点的最小深度
mn = [0] * (n + 1)
# mx[u]:u子树中,叶子节点的最大深度
mx = [0] * (n + 1)
# chk[u]:布尔标记,1代表以u为根的子树是完全二叉树,0不是
chk = [0] * (n + 1)
ans = 0

for i in range(1, n + 1):
    li, ri = map(int, input().split())
    l[i] = li
    r[i] = ri

def dfs(u):
    global ans
    chk[u] = 1
    if u == 0:
        return
    # 后序:先递归左右子树
    dfs(l[u])
    dfs(r[u])

    # 条件1:左右子树本身都必须是完全二叉树
    chk[u] &= chk[l[u]] & chk[r[u]]

    # mn[u]:当前子树叶子最小深度
    mn[u] = 1 + min(mn[l[u]], mn[r[u]])
    # mx[u]:当前子树叶子最大深度
    mx[u] = 1 + max(mx[l[u]], mx[r[u]])

    # 条件2:左子树叶子最小深度 >= 右子树叶子最大深度
    chk[u] &= mn[l[u]] >= mx[r[u]]
    # 条件3:整棵子树叶子最小深度 >= 最大深度 - 1
    chk[u] &= mn[u] >= mx[u] - 1

    # 如果u是完全二叉树,答案+1
    ans += chk[u]

dfs(1)
print(ans)
题目详情
129 简答题 偏难 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

路径覆盖

时间限制:3.0 s

内存限制:512.0 MB

题目描述

给定一棵有 n 个结点的有根树 T ,结点依次以 1 , 2, . , n 编号 ,根结点编号为 1 。方便起见 ,编号为 i 的结点称为结点 i。

初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结

点。将结点 i 染为黑色需要代价 c,你需要在满足以上条件的情况下,最小化染色代价之和。

叶子是指 T 中没有子结点的结点。

 输入格式

第一行,一个正整数 n,表示结点数量。

输出格式

一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。

输入样例 1

4
1 2 3
5 6 2 3

输出样例 1

2

 输入样例 2

7
1 1 2 2 3 3
64 16 15 4 3 2 1

输出样例 2

10

数据范围

答案与解析
参考答案
getint = lambda: map(int, input().split())
getints = lambda: list(getint())
# 获取节点数
n = int(input())
# 各个节点的根节点
f = [0, 0] + getints()
# 各个节点涂黑的成本
c = [0] + getints()
# cnt[i]表示节点i有多少子节点
cnt = [0] * (n + 1)
# ans[i]表示以节点i为根节点的子树,需要多少成本才能让所有叶子结点到根节点都有涂黑的节点
ans = [0] * (n + 1)
# 统计一个节点有多少子节点
for i in range(2, n + 1):
	cnt[f[i]] += 1
# 遍历每一个节点,因为一个节点的父节点编号肯定这个节点,所以大编号的一定更深
for i in range(n, 0, -1):
	# 如果一个节点没有子节点,那么显然ans[i]=c[i]就是把自己涂黑
	if cnt[i] == 0:
		ans[i] = c[i]
	# 一个节点当前已经找到的答案等于
	ans[i] = min(ans[i], c[i])
	ans[f[i]] += ans[i]
print(ans[1])
题目详情
130 简答题 偏难 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

树上漫步

题目描述

小 A 有一棵 n个结点的树,这些结点依次以 1,2,...,n标号。

小 A 想在这棵树上漫步。具体来说,小 A 会从树上的某个结点出发,每一步可以移动到与当前结点相邻的结点,并且小 A 只会在偶数步(可以是零步)后结束漫步。

现在小 A 想知道,对于树上的每个结点,从这个结点出发开始漫步,经过偶数步能结束漫步的结点有多少个(可以经过重复的节点)。

输入格式

第一行,一个正整数n 。

接下来n-1 行,每行两个整数ui,vi ,表示树上有一条连接结点ui 和结点vi 的边。

输出格式

一行, n个整数,第 i个整数表示从结点i 出发开始漫步,能结束漫步的结点数量。


输入样例 1

3
1 3
2 3

输出样例 1

2 2 1

输入样例 2

4
1 3
3 2
4 3

输出样例 2

3 3 1 3

数据范围

对于40 % 的测试点,保证1≤n≤103 。

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

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

cnt = [0, 0]
color = [0 for i in range(n + 2)]
def dfs(x, c, f):
	color[x] = c
	cnt[c] += 1
	for y in to[x]:
		if y != f:
			dfs(y, c ^ 1, x)

dfs(1, 0, 0)
ans = []
for i in range(1, n + 1):
	ans.append(str(cnt[color[i]]))

print(' '.join(ans))
题目详情
131 简答题 偏难 GESP编程能力等级认证 ·GESP-Python六级 · 1.1 树的基本概念

树上游走

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含无穷节点的二叉树(即每个节点都有左儿子节点和右儿子节点;除根节点外,每个节点都有父节点),其中根节点的编号为 1 ,对于节点 i ,其左儿子的编号为 2×i,右儿子的编号为 2×i+1。

小杨会从节点 s 开始在二叉树上移动,每次移动为以下三种移动方式的任意一种:

第1种移动方式: 如果当前节点存在父亲节点,向上移动到当前节点的父亲节点,否则不移动;

第2种移动方式: 移动到当前节点的左儿子;

第3种移动方式: 移动到当前节点的右儿子。

小杨想知道移动 n 次后自己所处的节点编号。数据保证最后的所处的节点编号不超过1012。

输入格式

第一行包含一个正整数 n,s,代表移动次数和初始节点编号。

第二行包含一个长度为 n 且仅包含大写字母 U,L,R 的字符串,代表每次移动的方式,其中U 代表第1种移动方式,L 代表第2种移动方式,R 代表第3种移动方式。

输出格式

输出一个正整数,代表最后所处的节点编号。


输入样例

3 2
URR

输出样例

7

样例解释

小杨的移动路线为 2-1-3-7。

对于全部数据,保证有1≤n≤106,1≤s≤1012。

答案与解析
参考答案
INF = 1e12
n, s = map(int, input().split())
c = input()
st = []

for i in range(n):
	if c[i] == 'U':
		if s == 1:
			continue
		if st:
			st.pop()
			continue
		s >>= 1
	elif c[i] == 'L':
		if (s << 1) > INF:
			st.append('L')
			continue
		s = s << 1
	else:
		if (s << 1 | 1) > INF:
			st.append('R')
			continue
		s = s << 1 | 1
print(int(s))
题目详情
132 简答题 偏难 GESP编程能力等级认证 ·GESP-Python六级 · 综合练习

小杨的握手问题

时间限制:1.0 s

内存限制:128.0 MB

问题描述

小杨的班级里共有N名同学,学号从0至N-1。

某节课上,老师安排全班同学进行一次握手游戏,具体规则如下:老师安排了一个顺序,让全班N名同学依次进入教室。每位同学进入教室时,需要和已经在教室内且学号小于自己的同学握手。

现在,小杨想知道,整个班级总共会进行多少次握手。

提示:可以考虑使用归并排序进行降序排序,并在此过程中求解。

输入描述

输入包含2行。第一行一个整数N,表示同学的个数;第二行N个用单个空格隔开的整数,依次描述同学们进入教室的顺序,每个整数在0~N-1之间,表示该同学的学号。

保证每位同学会且只会进入教室一次。

输出描述

输出一行一个整数,表示全班握手的总次数。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。

样例输入 1

4

2 1 3 0

样例输出 1

2

样例解释 1

2号同学进入教室,此时教室里没有其他同学。

1号同学进入教室,此时教室里有2号同学。1号同学的学号小于2号同学,因此他们之间不需要握手。

3号同学进入教室,此时教室里有1,2号同学。3号同学的学号比他们都大,因此3号同学需要分别和另外两位同学握手。

0号同学进入教室,此时教室里有1,2,3号同学。0号同学的学号比他们都小,因此0号同学不需要与其他同学握手。

综上所述全班一共握手0+0+2+0=2次。


样例输入 2

6

0 1 2 3 4 5

样例输出 2

15

样例解释 2

全班所有同学之间都会进行握手,因为每位同学来到教室时,都会发现他的学号是当前教室里最大的,所以他需要和教室里的每位其他同学进行握手。


数据规模

对于30%的测试点,保证N≤100。

对于所有测试点,保证2≤N≤3×105。

答案与解析
参考答案
def merge(arr, l, r):
	if l + 1 == r:
		return 0
	mid = (l + r) >> 1
	ans = merge(arr, l, mid) + merge(arr, mid, r)

	_arr = []
	i, j = l, mid
	for _ in range(l, r):
		if j == r or (i < mid and arr[i] > arr[j]):
			_arr.append(arr[i])
			i += 1
		else:
			_arr.append(arr[j])
			j += 1
			ans += mid - i
	for idx, item in enumerate(_arr):
		arr[l+idx] = item
	#print(arr)
	return ans

n = int(input())
arr = list(map(int, input().split(' ')))
ans = merge(arr, 0, n)
print(ans)


题目详情