新疆生产建设兵团第二中学2025-2026学年高一下学期7月期末考试 信息技术试题

**基本信息** 兵团二中信息技术加试卷含4道编程大题，覆盖动态规划、图论、最短路径及物理建模，通过服务器网络、骑行川藏等真实情境考查计算思维与问题解决能力。 **题型特征** |题型|题量/分值|知识覆盖|命题特色| |----|-----------|----------|----------| |编程题|4题/400分|加分二叉树（动态规划、树遍历）、善意的投票（图论最小割）、服务器储存（最短路径、集合运算）、骑行川藏（物理建模、优化算法）|以服务器网络、川藏骑行等真实场景为载体，梯度设计从基础算法到复杂建模，突出计算思维与数字化创新应用|

绝密★启用前 兵团二中2025-2026学年优培·顶尖·超尖计划(加试) 信息技术 参考答案 AC/代码评审/测评系统：兵团二中信息技术教研组 评分说明: 1. 由于本信息技术试题的特殊性，无法给出参考答案。考生最终成绩参考测评系统的最终得分。 2. 测评系统一共10个测评点，每通过一个测评点加10分。未通过既不加分也不扣分。 3. 为供考生评估个人水平及查漏补缺相关知识点，本参考答案将给出每道题目涉及的相关知识点。 4. 四道题目均为按照难度系数降序排列。 一．加分二叉树 （1）动态规划 DP （2）递归 （3）区间 DP （4）树形 DP 二．善意的投票/冠军调查 （1）网络流 （2）最小割 三．服务器储存信息问题 （1）图论 （2）最短路 四．骑行川藏 （1）数学 （2）向量 （2）构造 （2）拉格朗日乘数法 信息技术试题参考答案 第 1 页（共1页） 学科网（北京）股份有限公司 $新疆生产建设兵团第二中学 Xinjiang Bingtuan No.2 Middle School 绝密★启用前 兵团二中2025-2026学年优培.顶尖·超尖计划（加试） 信息技术 命题/审题/校验：兵团二中信息技术教研组 注意事项： 1.考生代码编写完成后务必将自己的.cpp程序文件存储于NOI Linux桌面且分别 命名为“姓名-题号-准考证号”，如“白厄-1-20280101.cpp”,命名不符要求视作0分。 2.考生可使用任意IDE作答，程序设计语言仅允许使用C+,使用其他程序设计 语言记为0分。 3.作答时请全程打开OBS录屏软件且请勿关闭，全程保持运行NOI Linux系统环 境的VMware.虚拟机窗口置顶，一经发现录屏中断或VMware窗口中断即视为作弊处理。 4.考生作答过程中不得使用任意AI工具，如Ollma等，一经发现亦视作弊处理。 5.考试结束后，考生请勿关闭电脑或虚拟机，否则本场考试记为0分。 一、加分二叉树：本题共100分。 1.题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3，，n),其中数字1,2 3,,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数 为d,ree及它的每个子树都有一个加分，任一棵子树subtree(也包含tree本身) 的加分计算方法如下： subtree的左子树的加分×subtree的右子树的加分+subtree的根的分数 若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考 虑它的空子树。 试求一棵符合中序遍历为(1,2,3，，n)且加分最高的二叉树tree。要求输出： 1.tree的最高加分。 2.tree的前序遍历。 2.输入格式 第1行1个整数n,为节点个数。 第2行n个用空格隔开的整数，为每个节点的分数。 信息技术试题第1页（共6页） 新疆生产建设兵团第二中学 Xinjiang Bingtuan No.2 Middle School 3.输出格式 第1行1个整数，为最高加分(Ans≤4,000,000,000)。 第2行n个用空格隔开的整数，为该树的前序遍历。 4.输入输出样例 题目输入 5 571210 输出 145 31245 5.说明/提示 数据规模与约定 对于全部的测试点，保证1≤n<30,节点的分数是小于100的正整数， 答案不超过4×10°。 二、善意的投票/冠军调查：本题共100分。 1.题目描述 幼儿园里有个小朋友打算通过投票来决定睡不睡午觉。 对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。 虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以 投和自己本来意愿相反的票。 我们定义一次投票的冲突数为下面两者相加： ·实际投票不同的好朋友对数。 ·自己实际投票和自己本来意愿不同的人数。 我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？ 2.输入格式 第一行两个整数n,m。其中n代表总人数，m代表好朋友的对数。 第二行n个整数，第i个整数代表第i个小朋友的意愿：当它为1时表示 同意睡觉，当它为0时表示反对睡觉。 接下来m行，每行有两个整数i,j,表示i,j是一对好朋友，我们保证任 何两对i,j不会重复。 信息技术试题第2页（共6页） 新疆生产建设兵团第二中学 Xinjiang Bingtuan No.2 Middle School 3.输出格式 一行一个整数，即可能的最小冲突数。 4.输入输出样例 题目输入 33 100 12 13 32 输出 1 5.说明/提示 对于100%的数据，2≤n≤300,1≤m≤n-型。 2 三、服务器储存信息问题：本题共100分。 1.题目描述 Byteland王国准备在各服务器间建立大型网络并提供多种服务。 网络由台服务器组成，用双向的线连接。两台服务器之间最多只能有一条 线直接连接，同时，每台服务器最多只能和10台服务器直接连接，但是任意两台 服务器间必然存在一条路径将它们连接在一起。 每条传输线都有一个固定传输的速度。6()，w)表示服务器v和w之间的最 短路径长度，且对任意的v有6(v,v)=0。 有些服务器比别的服务器提供更多的服务，它们的重要程度要高一些。我们用 r()表示服务器v的重要程度rank。rank越高的服务器越重要。 每台服务器都会存储它附近的服务器的信息。当然，不是所有服务器的信息都 存，只有感兴趣的服务器信息才会被存储。服务器)对服务器W感兴趣是指， 不存在服务器u满足，r(u>r(w)且6(，u)≤6(，w)。 举个例子来说，所有具有最高rQnk的服务器都会被别的服务器感兴趣。如果 v是一台具有最高rank的服务器，由于6(v,)=0,所以v只对具有最高 rank的服务器感兴趣。 我们定义B(~)为)感兴趣的服务器的集合。我们希望计算所有服务器储存 信息技术试题第3页（共6页） 新疆生产建设兵团第二中学 Xinjiang Bingtuan No.2 Middle School 的信息量，即所有服务器的|B(v)引之和。Byteland王国并不希望存储大量的数据， 所以所有服务器存储的数据量(IB(v)川之和)不会超过30m。 你的任务是写一个程序，读入Byteland王国的网络分布，计算所有服务器存 储的数据量。 2.输入格式 第第一行两个整数n和m。n表示服务器的数量，m表示传输线的数量。 接下来n行，每行一个整数，第i行的整数为r(),表示第i台服务器的 rank. 接下来m行，每行表示各条传输线的信息，包含三个整数a,b,t。a和b是 传输线所连接的两台服务器的编号，t是传输线的长度。 3.输出格式 一个整数，表示所有服务器存储的数据总量，即B()川之和。 4.输入输出样例 题目输入 43 2 3 1 1 1430 2320 3420 输出 5.说明/提示 (1)输出解释 B(1)=1,2,B(2)=2,B3)=2,3,B(4=1,2,3,4。 (1)数据规模 1≤n≤30000,1≤m≤5n。 1≤r(i)≤10。 1≤t≤1000,1≤a,b≤n,a≠b。 信息技术试题第4页（共6页） 新疆生产建设兵团第二中学 Xinjiang Bingtuan No.2 Middle School 四、骑行川藏：本题共100分。 1.题目描述 蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉 萨。 川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路 况变化多端，而蛋蛋的体力十分有限，因此在每天的骑行前设定好目的地，同时合 理分配好自己的体力是一件非常重要的事情。 由于蛋蛋装备了一辆非常好的自行车，因此在骑行过程中可以认为他仅在克服 风阻做功（不受自行车本身摩擦力以及自行车与地面的摩擦力影响）。 某一天他打算骑段路，每一段内的路况可视为相同：对于第i段路，我们 给出有关这段路况的3个参数S,k,v',其中S1表示这段路的长度，k表示这 段路的风阻系数，'表示这段路上的风速(；>0表示在这段路上他遇到了顺风， 反之则意味着他将受逆风影响)。 若某一时刻在这段路上骑车速度为v,则他受到的风阻大小为F= k(v-)(这样若在长度为s的路程内保持骑行速度v不变，则他消耗能量（做 功)E=k(v-v)s)。 设蛋蛋在这天开始时的体能值是E,请帮助他设计一种行车方案，使他在有 限的体力内用最短的时间到达目的地。请告诉他最短的时间T是多少。 2.输入格式 第一行包含一个正整数n和一个实数E,分别表示路段的数量以及蛋蛋的体能 值。 接下来n行分别描述n个路段，每行有3个实数S,k,v',分别表示第i段 路的长度，风阻系数以及风速。 3.输出格式 输出一个实数T,表示蛋蛋到达目的地消耗的最短时间，要求至少保留到小数 点后6位。 信息技术试题第5页（共6页） 新疆生产建设兵团第二中学 Xinjiang Bingtuan No.2 Middle School 4.输入输出样例 题目输入 310000 18000105 20000158 5000056 输出 12531.34496464 5. 说明/提示 （1)样例说明 种可能的方案是：蛋蛋在三段路上都采用匀速骑行的方式，其速度依次 为5.12939919,8.03515481,6.17837967。 (2)评分方法 本题没有部分分，你程序的输出只有和标准答案的差距不超过106时， 才能获得该测试点的满分，否则不得分。 (3)数据规模与约定 对于10%的数据，n=1。 对于40%的数据，n≤2。 对于60%的数据，n≤100。 对于80%的数据，n≤1000。 对于100%的数据，n≤104，Eu≤108，S1∈[0,101，k1∈(0,15]，∈ (-100,100)。 数据保证最终的答案不会超过105。 (4)提示 必然存在一种最优的体力方案满足：蛋蛋在每段路上都采用匀速骑行的方 式。 信息技术试题第6页（共6页）新疆生产建设兵团第二中学 Xinjiang Bingtuan No.2 Middle School 绝密★启用前 兵团二中2025-2026学年优培.顶尖·超尖计划（加试） 信息技术参考答案 AC/代码评审/测评系统：兵团二中信息技术教研组 评分说明： 1.由于本信息技术试题的特殊性，无法给出参考答案。考生最终成绩参考测评系统 的最终得分。 2.测评系统一共10个测评点，每通过一个测评点加10分。未通过既不加分也不扣 分。 3.为供考生评估个人水平及查漏补缺相关知识点，本参考答案将给出每道题目涉及 的相关知识，点。 4.四道题目均为按照难度系数降序排列。 一.加分二叉树 (1)动态规划DP (2)递归 (3)区间DP (4)树形DP 二.善意的投票/冠军调查 (1)网络流 (2)最小割 三.服务器储存信息问题 (1)图论 (2)最短路 四.骑行川藏 (1)数学 (2)向量 (2)构造 (2)拉格朗日乘数法 信息技术试题参考答案第1页（共1页） 绝密★启用前 兵团二中2025-2026学年优培·顶尖·超尖计划(加试) 信 息 技 术 命题/审题/校验：兵团二中信息技术教研组 注意事项： 1．考生代码编写完成后务必将自己的.cpp程序文件存储于NOI Linux桌面且分别命名为“姓名-题号-准考证号”，如“白厄-1-20280101.cpp”，命名不符要求视作0分。 2．考生可使用任意IDE作答，程序设计语言仅允许使用C++，使用其他程序设计语言记为0分。 3．作答时请全程打开OBS录屏软件且请勿关闭，全程保持运行NOI Linux系统环境的VMware虚拟机窗口置顶，一经发现录屏中断或VMware窗口中断即视为作弊处理。 4．考生作答过程中不得使用任意AI工具，如Ollma等，一经发现亦视作弊处理。 5．考试结束后，考生请勿关闭电脑或虚拟机，否则本场考试记为0分。 一、加分二叉树：本题共100分。 1．题目描述 设一个 个节点的二叉树 tree 的中序遍历为 ，其中数字 , , , …, 为节点编号。每个节点都有一个分数（均为正整数），记第 个节点的分数为 ，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下： 若某个子树为空，规定其加分为 ，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为 且加分最高的二叉树 tree。要求输出： 1. tree 的最高加分。 2. tree 的前序遍历。 2．输入格式 第 1 行 个整数 ，为节点个数。 第 2 行 个用空格隔开的整数，为每个节点的分数。 3．输出格式 第 1 行 个整数，为最高加分（）。 第 2 行 个用空格隔开的整数，为该树的前序遍历。 4．输入输出样例 题目输入 5 5 7 1 2 10 输出 145 3 1 2 4 5 5．说明/提示 数据规模与约定 对于全部的测试点，保证 ，节点的分数是小于 100 的正整数，答案不超过 。 二、善意的投票/冠军调查：本题共100分。 1．题目描述 幼儿园里有 个小朋友打算通过投票来决定睡不睡午觉。 对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。 虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。 我们定义一次投票的冲突数为下面两者相加： • 实际投票不同的好朋友对数。 • 自己实际投票和自己本来意愿不同的人数。 我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？ 2．输入格式 第一行两个整数 , 。其中 代表总人数， 代表好朋友的对数。 第二行 个整数，第 个整数代表第 个小朋友的意愿：当它为 时表示同意睡觉，当它为 时表示反对睡觉。 接下来 行，每行有两个整数 , ，表示 , 是一对好朋友，我们保证任何两对 , 不会重复。 3．输出格式 一行一个整数，即可能的最小冲突数。 4．输入输出样例 题目输入 3 3 1 0 0 1 2 1 3 3 2 输出 1 5．说明/提示 对于 100% 的数据，，。 三、服务器储存信息问题：本题共100分。 1．题目描述 Byteland 王国准备在各服务器间建立大型网络并提供多种服务。 网络由 台服务器组成，用双向的线连接。两台服务器之间最多只能有一条线直接连接，同时，每台服务器最多只能和 10 台服务器直接连接，但是任意两台服务器间必然存在一条路径将它们连接在一起。 每条传输线都有一个固定传输的速度。 表示服务器 和 之间的最短路径长度，且对任意的 有 。 有些服务器比别的服务器提供更多的服务，它们的重要程度要高一些。我们用 表示服务器 的重要程度 。 越高的服务器越重要。 每台服务器都会存储它附近的服务器的信息。当然，不是所有服务器的信息都存，只有感兴趣的服务器信息才会被存储。服务器 对服务器 感兴趣是指，不存在服务器 满足， 且 。 举个例子来说，所有具有最高 的服务器都会被别的服务器感兴趣。如果 是一台具有最高 的服务器，由于 ，所以 只对具有最高 的服务器感兴趣。 我们定义 为 感兴趣的服务器的集合。我们希望计算所有服务器储存的信息量，即所有服务器的 之和。Byteland 王国并不希望存储大量的数据，所以所有服务器存储的数据量（ 之和）不会超过 。 你的任务是写一个程序，读入 Byteland 王国的网络分布，计算所有服务器存储的数据量。 2．输入格式 第第一行两个整数 和 。 表示服务器的数量， 表示传输线的数量。 接下来 行，每行一个整数，第 行的整数为 ，表示第 台服务器的 。 接下来 行，每行表示各条传输线的信息，包含三个整数 , , 。 和 是传输线所连接的两台服务器的编号， 是传输线的长度。 3．输出格式 一个整数，表示所有服务器存储的数据总量，即 之和。 4．输入输出样例 题目输入 4 3 2 3 1 1 1 4 30 2 3 20 3 4 20 输出 9 5．说明/提示 （1）输出解释 , , , 。 （1）数据规模 。 。 。 四、骑行川藏：本题共100分。 1．题目描述 蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。 川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有限，因此在每天的骑行前设定好目的地，同时合理分配好自己的体力是一件非常重要的事情。 由于蛋蛋装备了一辆非常好的自行车，因此在骑行过程中可以认为他仅在克服风阻做功（不受自行车本身摩擦力以及自行车与地面的摩擦力影响）。 某一天他打算骑 段路，每一段内的路况可视为相同：对于第 段路，我们给出有关这段路况的 个参数 , , ，其中 表示这段路的长度， 表示这段路的风阻系数， 表示这段路上的风速（ 表示在这段路上他遇到了顺风，反之则意味着他将受逆风影响）。 若某一时刻在这段路上骑车速度为 ，则他受到的风阻大小为 （这样若在长度为 的路程内保持骑行速度 不变，则他消耗能量（做功））。 设蛋蛋在这天开始时的体能值是 ，请帮助他设计一种行车方案，使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间 是多少。 2．输入格式 第一行包含一个正整数 和一个实数 ，分别表示路段的数量以及蛋蛋的体能值。 接下来 行分别描述 个路段，每行有 3 个实数 , , ，分别表示第 段路的长度，风阻系数以及风速。 3．输出格式 输出一个实数 ，表示蛋蛋到达目的地消耗的最短时间，要求至少保留到小数点后 6 位。 4．输入输出样例 题目输入 3 10000 10000 10 5 20000 15 8 50000 5 6 输出 12531.34496464 5．说明/提示 （1）样例说明 一种可能的方案是：蛋蛋在三段路上都采用匀速骑行的方式，其速度依次为 5.12939919, 8.03515481, 6.17837967。 （2）评分方法 本题没有部分分，你程序的输出只有和标准答案的差距不超过 时，才能获得该测试点的满分，否则不得分。 （3）数据规模与约定 对于 10% 的数据，。 对于 40% 的数据，。 对于 60% 的数据，。 对于 80% 的数据，。 对于 100% 的数据，⁴，，，，。 数据保证最终的答案不会超过 。 （4）提示 必然存在一种最优的体力方案满足：蛋蛋在每段路上都采用匀速骑行的方式。 信息技术试题 第 2 页（共6页） 学科网（北京）股份有限公司 $