答案解析 — 星火征途（红色文化）

第 1 题单选题 2 分

在"红军密码本"问题中，需要尝试所有可能的3位数字密码（000-999）来破解一个加密情报。这种逐一尝试所有可能解的算法思想属于？

A. 贪心算法

B. 枚举算法

C. 递推算法

D. 分治算法

✅ 正确答案：B

💡 考点解析：枚举算法——穷举所有可能的候选解来寻找正确答案

第 2 题单选题 2 分

以下Python代码用于计算"红军长征中某段路的翻山方案数"，该函数使用了什么算法思想？

def climb(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb(n - 1) + climb(n - 2)
print(climb(5))

A. 贪心算法

B. 枚举算法

C. 递归算法

D. 广度优先搜索

✅ 正确答案：C

💡 考点解析：递归算法——函数调用自身来求解问题

第 3 题单选题 2 分

在"革命根据地地形图"中，使用二维列表存储海拔数据。terrain = [[100, 200, 150], [180, 220, 190], [160, 210, 170]]，以下哪个代码可以正确获取第2行第3列（220）的值？

A. terrain[2][3]

B. terrain[1][2]

C. terrain[2][1]

D. terrain[3][2]

✅ 正确答案：B

💡 考点解析：二维列表的索引——先行后列，索引从0开始，terrain[1][2] 表示第2行第3列

第 4 题单选题 2 分

在"军需物资最优分配"问题中，红军需要将有限的物资分配给多个前线部队。每次选择"当前单位物资收益最高"的部队进行分配，直到物资耗尽。这种策略属于？

A. 枚举算法

B. 递推算法

C. 贪心算法

D. 深度优先搜索

✅ 正确答案：C

💡 考点解析：贪心算法——每一步都选择当前看起来最优的局部方案，以期望获得全局最优解

第 5 题单选题 2 分

在"革命根据地联络网"中，需要判断从一个根据地出发能否到达另一个根据地。以下哪种算法最适合解决这类"连通性"问题？

A. 冒泡排序

B. 二分查找

C. 深度优先搜索（DFS）或广度优先搜索（BFS）

D. 选择排序

✅ 正确答案：C

💡 考点解析：搜索算法——DFS/BFS用于遍历图或网格，判断连通性和可达性

第 6 题多选题 4 分

关于算法时间复杂度的说法，以下哪些是正确的？

A. 一个算法执行的基本操作次数可以衡量其时间复杂度

B. 对于同一问题，不同算法的时间复杂度可能不同

C. 时间复杂度为O(n^2)的算法一定比O(n)的算法在任何输入下都慢

D. 枚举算法在数据规模很大时可能效率较低，因为它需要检查所有可能的解

✅ 正确答案：ABD

💡 考点解析：时间复杂度概念——C选项错误，因为在大O表示法中，当n很小时，常数因子的影响可能使O(n^2)反而更快

第 7 题多选题 4 分

关于递推与递归的说法，以下哪些是正确的？

A. 递推是从已知的初始条件出发，逐步推导出结果

B. 递归是函数直接或间接地调用自身

C. 斐波那契数列既可以用递推实现，也可以用递归实现

D. 递归必须有终止条件（基准情况），否则会无限递归导致栈溢出

✅ 正确答案：ABCD

💡 考点解析：递推（迭代）与递归的关系和特点

第 8 题多选题 4 分

在Python中，关于列表排序的说法，以下哪些是正确的？

A. list.sort() 会直接修改原列表，返回值为 None

B. sorted(list) 会返回一个新的排序后列表，原列表不变

C. list.sort(reverse=True) 可以实现降序排序

D. sorted(list, key=len) 可以按元素的长度进行排序

✅ 正确答案：ABCD

💡 考点解析：列表的 sort() 方法与内置 sorted() 函数的区别，reverse 和 key 参数的使用

第 9 题多选题 4 分

在"红色情报网"系统中，使用了嵌套数据结构。以下Python代码的描述，正确的有哪些？

spy_network = {
    "上海站": {"联络员": ["李明", "王芳"], "密码本": 3},
    "延安站": {"联络员": ["张强", "刘洋", "陈静"], "密码本": 5}
}

A. spy_network["上海站"]["联络员"] 是一个列表

B. spy_network["延安站"]["联络员"][1] 的值是 "刘洋"

C. spy_network["上海站"]["密码本"] 的值是 3

D. len(spy_network["延安站"]["联络员"]) 的结果是 3

✅ 正确答案：ABCD

💡 考点解析：字典与列表的嵌套访问——字典嵌套字典，再嵌套列表

第 10 题多选题 4 分

关于Python异常处理的说法，以下哪些是正确的？

A. try 代码块用于包裹可能发生异常的代码

B. 一个 try 后面可以跟多个 except 来捕获不同类型的异常

C. finally 代码块中的代码无论是否发生异常都会执行

D. except Exception 可以捕获所有类型的异常

✅ 正确答案：ABCD

💡 考点解析：异常处理——try-except-finally结构，多个except捕获不同异常类型

第 11 题编程操作题 15 分

题目描述：
红军长征途中，需要在一段直线上选择若干休整点。已知直线上有n个可选休整点，每个休整点有一个"安全指数"（正整数）。由于战略需要，任意两个被选中的休整点之间必须至少间隔一个休整点（即不能选择相邻的休整点）。请你编写程序，计算在满足条件的情况下，所选休整点的安全指数之和最大是多少。

输入格式：
第一行一个正整数 n（1 ≤ n ≤ 20），表示可选休整点数量。
第二行 n 个正整数，用空格分隔，表示每个休整点的安全指数。

输出格式：
一个整数，表示最大安全指数之和。
示例输入1：
5
10 5 20 15 30
示例输出1：
60
说明：选择第1、3、5个休整点：10 + 20 + 30 = 60；或第2、5个：5 + 30 = 35；第1、4个：10 + 15 = 25。最大值为60。
示例输入2：
3
10 20 10
示例输出2：
20

示例输入：

示例输出：

✅ 参考答案：

📖 参考代码

# 方法一：枚举所有可能的选择方案
n = int(input())
safety = list(map(int, input().split()))
max_sum = 0
# 枚举所有 2^n 种选择方案
for mask in range(1 << n):
    current_sum = 0
    valid = True
    prev_selected = False
    for i in range(n):
        if (mask >> i) & 1:  # 第 i 位为1，表示选中
            if prev_selected:  # 上一个也被选中，违反间隔规则
                valid = False
                break
            current_sum += safety[i]
            prev_selected = True
        else:
            prev_selected = False
    if valid and current_sum > max_sum:
        max_sum = current_sum
print(max_sum)

第 12 题编程操作题 15 分

题目描述：
红军情报员需要将一段密码从初始字符串S变为目标字符串T。每次操作可以选择以下之一：
1. 在任意位置插入一个字符
2. 删除任意一个字符
3. 将任意一个字符替换为另一个字符
请你编写程序，计算从S变为T所需的最少操作次数。
提示：本题考察递推/动态规划思想。设 dp[i][j] 表示将S的前i个字符变为T的前j个字符的最少操作数。可以从较小规模的子问题推导。

输入格式：
两行字符串，第一行为初始密码S，第二行为目标密码T。字符串长度均不超过100。

输出格式：
一个整数，表示最少操作次数。
示例输入1：
redstar
redarmy
示例输出1：
4
说明：redstar → redarmy：替换s→a(1次)，替换t→m(1次)，替换a→y(1次)，删除r(1次)，共4次。
示例输入2：
army
army
示例输出2：
0

示例输入：

示例输出：

✅ 参考答案：

📖 参考代码

# 编辑距离（Levenshtein distance）——递推/动态规划
S = input().strip()
T = input().strip()
len_s = len(S)
len_t = len(T)
# dp[i][j] 表示 S 的前 i 个字符变为 T 的前 j 个字符的最少操作数
dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
# 初始化：空字符串的情况
for i in range(len_s + 1):
    dp[i][0] = i  # 删除 i 个字符
for j in range(len_t + 1):
    dp[0][j] = j  # 插入 j 个字符
# 递推填表
for i in range(1, len_s + 1):
    for j in range(1, len_t + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]  # 字符相同，不需要操作
        else:
            # 取三种操作中的最小值
            insert_op = dp[i][j - 1] + 1      # 插入
            delete_op = dp[i - 1][j] + 1      # 删除
            replace_op = dp[i - 1][j - 1] + 1 # 替换
            dp[i][j] = min(insert_op, delete_op, replace_op)
print(dp[len_s][len_t])

第 13 题编程操作题 20 分

题目描述：
革命根据地分布在一个n行m列的矩形地图上。地图中每个格子用数字表示：1表示该格子属于根据地，0表示该格子是敌占区。一个"连通区域"是指若干个相邻的根据地格子组成的区域（相邻包括上下左右四个方向）。请你编写程序，找出地图中面积最大的连通区域，输出其面积（格子数量）。
提示：使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历二维网格。

输入格式：
第一行两个正整数 n 和 m（1 ≤ n, m ≤ 50），用空格分隔，表示地图的行数和列数。
接下来 n 行，每行 m 个整数（0或1），用空格分隔，表示地图。

输出格式：
一个整数，表示最大连通区域的面积。如果地图中没有根据地（全部为0），则输出0。
示例输入1：
4 5
1 1 0 0 1
1 0 0 1 1
0 0 1 1 0
1 1 0 0 1
示例输出1：
4
说明：左上角的3个1不连通（中间有0隔开）。中间有一个4个1的连通块（第2行第4-5列和第3行第3-4列），面积最大为4。
示例输入2：
3 3
1 1 1
0 1 0
1 1 1
示例输出2：
7
说明：除了中间(2,2)位置因周围被1包围？不，中间是1，所有1形成一个连通块，面积为7。

示例输入：

示例输出：

✅ 参考答案：

📖 参考代码

# 使用深度优先搜索（DFS）遍历二维网格
import sys
sys.setrecursionlimit(10000)
def dfs(x, y):
    """从(x,y)开始搜索连通区域，返回该区域的面积"""
    if x < 0 or x >= n or y < 0 or y >= m:
        return 0
    if grid[x][y] == 0 or visited[x][y]:
        return 0
    visited[x][y] = True
    area = 1  # 当前格子计入面积
    # 四个方向搜索
    area += dfs(x - 1, y)  # 上
    area += dfs(x + 1, y)  # 下
    area += dfs(x, y - 1)  # 左
    area += dfs(x, y + 1)  # 右
    return area
# 输入地图
line = input().split()
n = int(line[0])
m = int(line[1])
grid = []
for i in range(n):
    row = list(map(int, input().split()))
    grid.append(row)
# visited数组记录已访问的格子
visited = [[False] * m for _ in range(n)]
max_area = 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == 1 and not visited[i][j]:
            area = dfs(i, j)
            if area > max_area:
                max_area = area
print(max_area)

第 14 题编程操作题 20 分

题目描述：
红军指挥部收到一份战役地图，地图是一个n行m列的网格。地图中每个格子有一个数字，表示通过该格子需要消耗的"行军体力值"。红军部队需要从起点（左上角，第1行第1列）行军到终点（右下角，第n行第m列）。部队每次只能向右或向下移动一格。请你编写程序，计算从起点到终点所需的最小体力消耗总和。
提示：本题考察递推/动态规划思想。定义 dp[i][j] 为从起点到达位置 (i, j) 的最小体力消耗。则：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])（考虑从上方或左方过来）。

输入格式：
第一行两个正整数 n 和 m（1 ≤ n, m ≤ 100），用空格分隔。
接下来 n 行，每行 m 个非负整数，用空格分隔，表示每个格子的体力消耗值。

输出格式：
一个整数，表示从起点到终点的最小体力消耗总和。
示例输入1：
3 4
1 3 5 2
2 1 4 3
4 2 1 5
示例输出1：
12
说明：路径 (1,1)→(2,1)→(2,2)→(3,2)→(3,3)→(3,4)，消耗为 1+2+1+2+1+5 = 12。
示例输入2：
2 2
1 2
3 4
示例输出2：
7
说明：路径 (1,1)→(1,2)→(2,2)，消耗为 1+2+4 = 7；或 (1,1)→(2,1)→(2,2)，消耗为 1+3+4 = 8。最小值为7。

示例输入：

示例输出：

✅ 参考答案：

📖 参考代码

# 输入地图尺寸
line = input().split()
n = int(line[0])
m = int(line[1])
# 输入体力消耗地图
grid = []
for i in range(n):
    row = list(map(int, input().split()))
    grid.append(row)
# dp[i][j] 表示从起点到 (i, j) 的最小体力消耗
dp = [[0] * m for _ in range(n)]
# 初始化起点
dp[0][0] = grid[0][0]
# 初始化第一行（只能从左边过来）
for j in range(1, m):
    dp[0][j] = dp[0][j - 1] + grid[0][j]
# 初始化第一列（只能从上方过来）
for i in range(1, n):
    dp[i][0] = dp[i - 1][0] + grid[i][0]
# 递推填表
for i in range(1, n):
    for j in range(1, m):
        dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
# 输出终点结果
print(dp[n - 1][m - 1])

📖 答案解析 — 星火征途（红色文化） — 困难