🏆 全国青少年信息素养大赛

算法应用主题赛 — 丝路新程(丝路文化)
难度:困难 | 时长:120 分钟 | 满分:100分
题型:5单选(10分) + 5多选(20分) + 4编程(70分)

算法应用主题赛 — 丝路新程(丝路文化)(困难)
考生:— 第 1 / 14 题
--:--
第 1 题 单选题 2 分
在敦煌壁画的数字化修复中,研究人员用一个二维列表 pixels 存储图像数据。若图像有 m 行 n 列,要获取第 i 行第 j 列的像素值,正确的访问方式是?
第 2 题 单选题 2 分
驼队商人用递推算法预测下一站货物的需求量。定义递推公式:f(1) = 10,f(n) = f(n-1) + n * 3(n > 1)。则 f(4) 的值是?
第 3 题 单选题 2 分
在海上丝绸之路中,商船需要将货物装入集装箱,每箱最多装 capacity 件。以下使用贪心策略的代码要实现"用最少的箱子装完所有货物",应在横线处填入?
items = [5, 3, 8, 2, 6]
capacity = 10
boxes = 0
current = 0
for item in items:
    if current + item > capacity:
        boxes += 1
        current = _____
    current += item
第 4 题 单选题 2 分
研究丝路遗址的旅行路线时,需要遍历所有可能的城市访问顺序。以下代码中,count 的最终值是?
count = 0
for i in range(3):
    for j in range(3):
        if i != j:
            for k in range(3):
                if k != i and k != j:
                    count += 1
print(count)
第 5 题 单选题 2 分
驼队商人用递归函数计算不同路线的方案数。以下递归函数的返回值是什么?
def routes(n):
    if n <= 1:
        return 1
    return routes(n - 1) + routes(n - 2)
print(routes(5))
第 6 题 多选题 4 分
在丝绸之路的贸易路线规划中,可以使用多种算法思想。以下关于算法思想的描述,正确的有?(多选)
第 7 题 多选题 4 分
在敦煌文物的数字化存档中,使用二维列表存储文物的属性矩阵。关于以下代码,说法正确的有?(多选)
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
第 8 题 多选题 4 分
在海上丝绸之路的航线搜索中,使用广度优先搜索(BFS)寻找从起点港口到目标港口的最短航线。关于搜索算法,以下说法正确的有?(多选)
第 9 题 多选题 4 分
丝路商队需要将贵重货物按利润最大化原则分配运力。关于贪心算法,以下说法正确的有?(多选)
第 10 题 多选题 4 分
在丝路遗址的考古研究中,考古学家使用递归回溯算法来复原破碎的文物。关于递归回溯,以下说法正确的有?(多选)
第 11 题 编程操作题 0 分

题目描述:
丝绸之路上的商人需要在不同城市之间贩运商品。商品在每个城市的买入价和卖出价不同。商人从城市A出发,经过若干个城市到达终点,共经过 n 个城市。在每个城市,他可以选择买入商品,然后在之后经过的任何一个城市卖出。每笔交易只能买卖一次(必须先买后卖)。
已知每个城市的商品价格(整数,单位:文),请你编写程序,帮商人计算在整条路线中能获得的最大利润。如果无法获得利润(价格一直在下跌),则输出 0。

输入格式:
第一行:一个正整数 n,表示经过的城市数量。
第二行:n 个正整数,以空格分隔,依次表示每个城市的商品价格。

输出格式:
一行,输出一个整数,表示最大利润。
示例输入1:
6
7 1 5 3 6 4
示例输出1:
5
(解释:在第2个城市买入(价格为1),在第5个城市卖出(价格为6),利润为 6-1=5。)
示例输入2:
4
7 6 4 3
示例输出2:
0
(解释:价格一直下跌,无法获利。)

示例输入:

示例输出:

第 12 题 编程操作题 0 分

题目描述:
驼队从起点出发前往终点,总路程为 distance 里。沿途有 n 个驿站,每个驿站距离起点的里程已知(整数,单位:里)。驼队每天最多只能行进 max_per_day 里,且必须在驿站处停靠过夜(不能在驿站之外的地方露营)。
请你使用贪心算法编写程序,计算驼队最少需要多少天才能到达终点。如果驼队无法在限制条件下到达终点(即存在两个相邻停靠点之间的距离超过了每日最大行程),则输出 -1。

输入格式:
第一行:三个正整数 n、distance、max_per_day,以空格分隔。
第二行:n 个正整数,以空格分隔,依次表示每个驿站距离起点的里程(已按升序排列)。

输出格式:
一行,输出最少需要的天数;如果无法到达终点,输出 -1。
示例输入1:
4 100 30
10 30 60 80
示例输出1:
4
(解释:起点0→第1天到30(驿站2),走30里→第2天到60(驿站3),走30里→第3天到80(驿站4),走20里→第4天到100(终点),走20里。共4天。)
示例输入2:
2 100 20
15 50
示例输出2:
-1
(解释:从驿站1(15)到驿站2(50)距离为35里,超过每日最大行程20里,无法到达。)

示例输入:

示例输出:

第 13 题 编程操作题 0 分

题目描述:
考古学家在丝绸之路遗址中发现了一批破碎的竹简,每片竹简上刻有一个汉字。现在需要将这些竹简拼接起来复原原文。竹简已经被编上了从 1 到 n 的序号,考古学家知道每片竹简连接的下一个竹简的编号(如果没有下一片,则编号为 0)。
请你使用递推或递归方法,从第一片竹简(编号为1)开始,依次输出完整的原文。
输入保证:竹简从编号1开始,连接关系构成一条单向链表,不会形成环。

输入格式:
第一行:一个正整数 n,表示竹简的数量。
接下来 n 行,每行包含一个汉字和一个整数,以空格分隔,分别表示该竹简上的文字和下一片竹简的编号。

输出格式:
一行,输出拼接后的完整原文(汉字之间无空格)。

示例输入:

4
丝 2
绸 3
之 4
路 0

示例输出:

丝绸之路
(解释:竹简1"丝"→竹简2"绸"→竹简3"之"→竹简4"路"→连接结束(0),完整原文为"丝绸之路"。)
第 14 题 编程操作题 0 分

题目描述:
丝绸之路的商人规划了一条经过 n 个城市的贸易路线,城市编号为 1 到 n。商人从城市 1 出发,必须到达城市 n。城市之间的道路信息存储在一个二维列表(邻接矩阵)中:roads[i][j] 表示从城市 i 直接到城市 j 的贸易利润(正数表示盈利,0表示无直接道路)。每个城市只需访问一次,题目保证不会出现导致无限递归的环路。
请你使用深度优先搜索(DFS)编写程序,找出从城市1到城市n的所有可能路径中,总利润最大的那条路径的总利润值。题目保证城市n一定可达。

输入格式:
第一行:一个正整数 n(2 <= n <= 10),表示城市数量。
接下来 n 行,每行 n 个整数(以空格分隔),表示邻接矩阵。roads[i][j] 表示城市 i+1 到城市 j+1 的利润。

输出格式:
一行,一个整数,表示从城市1到城市n的最大总利润。

示例输入:

5
0 3 5 0 0
0 0 0 2 0
0 0 0 1 7
0 0 0 0 4
0 0 0 0 0

示例输出:

12
(解释:可能的路径有:1->2->4->5 利润=3+2+4=9;1->3->4->5 利润=5+1+4=10;1->3->5 利润=5+7=12。最大利润为12。)