首页 › 题库 › GESP编程能力等级认证 › 2 复杂动态规划

GESP-Python七级 题库

共 10 道题 · 按题型筛选,点「查看答案」核对解析
章节 2 复杂动态规划 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

已知三个序列: s1 = {3, 1, 8, 2, 5, 6, 7, 4} , s2 = {1, 5, 1, 8, 6, 4, 7, 5, 6} , s3 ={1, 8, 3, 5, 7, 6, 2, 4} 。以下哪个序列是它们的最长公共子序列( )。

A

{1, 8, 5, 6}

B

{1, 5, 6, 7}

C

{1, 8, 6}

D

{1, 5, 7, 4}

答案与解析
正确答案:A
确定三个序列的最长公共子序列需逐元素比对,找出在所有序列中按相同顺序出现的最长元素序列。首先枚举可能的公共子序列,筛选出仅包含同时存在于s1、s2和s3中的元素且保持各自原有顺序的候选序列。对每个候选序列验证其是否能在三个序列中分别找到对应的递增下标序列,使得元素顺序一致。比较所有合法公共子序列的长度,选择长度最大者作为结果。若多个序列长度相同,则任取其一作为最长公共子序列。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

现有一个地址区间为0~10 的哈希表,当出现冲突情况,会往后找第一个空的地址存储(到 10 冲突了就从 0开始往后),现在要依次存储(1,3,5,7,9) ,哈希函数为h(x)=(x²+x)mod 11 。其中 9 存储在哈希表哪个地址中( )。

A

1

B

2

C

3

D

4

答案与解析
正确答案:D
计算每个元素通过哈希函数 h(x) = (x² + x) mod 11 得到的初始地址。按输入顺序依次处理元素,若该地址为空,则存储;若已被占用,则从该地址后一个位置开始线性探测,逐位检查下一个地址是否为空,直到找到第一个空地址进行存储。探测过程在到达地址 10 后若仍需继续,则回绕至地址 0 继续查找。重复此过程直至所有元素存储完毕。关注元素 9 在该机制下的最终存储位置。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

给定一个整数数组 nums,找到其中最长的严格上升子序列的长度。

子序列是指从原数组中删除一些元素(或不删除)后,剩余元素保持原有顺序的序列。

要求:

子序列必须是严格上升的(即每个元素都比前一个元素大)。

返回最长严格上升子序列的长度。

横线处应该填写的是()

def length_of_lis(nums):
	if not nums:
		return 0

	dp = [1] * len(nums)
	for i in range(1, len(nums)):
		for j in range(i):
			if nums[j] < nums[i]:
				________________
	return max(dp)
A
dp[i] = max(dp[i], dp[j])
B
dp[i] = max(dp[i], dp[j] + 1)
C
dp[i] = max(dp[i]+1, dp[j] + 1)
D
dp[i] = max(dp[i]+1, dp[j])
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

以下代码的功能是什么?

def max_subarray(nums):
	dp = [0] * len(nums)
	dp[0] = nums[0]
	for i in range(1, len(nums)):
		dp[i] = max(nums[i], dp[i - 1] + nums[i])
	return max(dp)
A
计算数组的最大值
B
计算数组的最大子数组和
C
计算数组的最小值
D
计算数组的最小子数组和
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

以下代码的功能是什么?

def coin_change(coins, amount):
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for coin in coins:
		for i in range(coin, amount + 1):
			dp[i] = min(dp[i], dp[i - coin] + 1)
	return dp[amount] if dp[amount] != float('inf') else -1
A
计算硬币的组合数
B
计算硬币的最小数量,使得总金额等于目标金额
C
计算硬币的最大数量,使得总金额等于目标金额
D
计算硬币的总金额
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

以下代码的功能是什么?

def fuction1(text1, text2):
	m, n = len(text1), len(text2)
	dp = [[0] * (n + 1) for _ in range(m + 1)]
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if text1[i - 1] == text2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[m][n]
A
计算两个字符串的最长公共子序列
B
计算两个字符串的最长公共子串
C
计算两个字符串的最长公共前缀
D
计算两个字符串的最长公共后缀
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

以下代码的功能是什么?

def knapsack(weights, values, capacity):
	n = len(weights)
	dp = [[0] * (capacity + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, capacity + 1):
			if weights[i - 1] <= j:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i
- 1])
			else:
				dp[i][j] = dp[i - 1][j]
	return dp[n][capacity]
A
计算背包问题的最小价值
B
计算背包问题的最大价值
C

计算背包问题的最小重量

D

计算背包问题的最大重量

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

以下代码的功能是什么?

def unique_paths(m, n):
	dp = [[1] * n for _ in range(m)]
	for i in range(1, m):
		for j in range(1, n):
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
	return dp[m - 1][n - 1]
A
计算从左上角到右下角的唯一路径数
B
计算从左上角到右下角的最短路径
C
计算从左上角到右下角的最长路径
D
计算从左上角到右下角的最小路径
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
9 判断题 偏易 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

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

A
对
B
错
答案与解析
正确答案:对
使用动态规划求解最长公共子序列时,状态转移依赖于前一行和当前行的值。通过滚动数组技术,仅保留当前行和前一行的状态,将二维状态表压缩为两个一维数组交替更新。每次遍历时根据索引奇偶性或模运算决定当前使用哪一行,从而实现空间复用。该方法使存储空间由O(n²)降至O(n),同时保持时间复杂度不变。
题目详情
10 判断题 偏易 GESP编程能力等级认证 ·GESP-Python七级 · 2 复杂动态规划

动态规划算法通常有递归实现和递推实现。但由于递归调用在运行时会由于层数过多导致程序崩溃,因此有些动态规划算法只能用递推实现。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情