NOIP2026 全国青少年信息学奥林匹克联赛 提高组试题及详细答案

NOIP2026全国青少年信息学奥林匹克联赛提高组试题及详细答案NOIP2026提高组初赛试题（笔试）考试时间：2026年10月18日14:30-16:30满分：100分答题说明：1.全部试题答案均要求写在答题卡上，写在试卷上无效。2.第1-20题为单项选择题，每题1.5分，共30分；第21-40题为不定项选择题，每题2分，共40分；第41-45题为问题求解，每题6分，共30分。3.单选、多选选错、漏选、多选均不得分，问题求解按步骤给分。一、单项选择题（共20题，每题1.5分，共30分）1.以下不属于计算机基础逻辑结构的是（）A.顺序结构B.分支结构C.递归结构D.循环结构2.二进制数110101转换为十进制数的结果是（）A.51B.53C.49D.573.已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为（）A.CBEFDAB.CBADEFC.BCEDFAD.无法确定4.时间复杂度为O(nlogn)的排序算法是（）A.冒泡排序B.归并排序C.选择排序D.插入排序5.一个栈的入栈序列为1,2,3,4,5，则不可能的出栈序列是（）A.3,2,1,5,4B.4,3,5,2,1C.2,5,4,3,1D.1,5,2,3,46.IPv4地址的位数为（）A.16位B.32位C.64位D.128位7.对于有序数组，查找效率最高的算法是（）A.顺序查找B.二分查找C.哈希查找D.分块查找8.有向图中，度的计算规则是（）A.仅统计入度B.仅统计出度C.入度+出度D.边的数量9.以下数据结构中，支持随机访问的是（）A.单链表B.栈C.数组D.队列10.十进制数26转换为十六进制数为（）A.1AB.1BC.2AD.2B11.一棵深度为5的满二叉树的节点总数为（）A.16B.31C.32D.1512.贪心算法的核心特点是（）A.全局最优B.每一步局部最优C.暴力枚举D.回溯试探13.C++中，int类型数据的字节数为（）A.1字节B.2字节C.4字节D.8字节14.无向完全图n个顶点的边数为（）A.nB.n(n-1)/2C.n²D.n-115.以下不属于暴力枚举优化的是（）A.剪枝B.二分C.去重D.全量遍历16.队列的操作特性是（）A.先进后出B.先进先出C.随机进出D.后进先出17.排序算法中，稳定排序的是（）A.快速排序B.堆排序C.冒泡排序D.选择排序18.递归算法必须包含的要素是（）A.循环结构B.边界终止条件C.数组存储D.分支结构19.哈希表冲突解决方法不包括（）A.线性探测B.链地址法C.二次探测D.顺序覆盖法20.图的广度优先遍历（BFS）适合解决的问题是（）A.最短路径（无权图）B.最长路径C.拓扑排序D.最小生成树二、不定项选择题（共20题，每题2分，共40分）21.以下属于线性数据结构的有（）A.数组B.栈C.队列D.二叉树22.下列时间复杂度优于O(n²)的有（）A.O(n)B.O(logn)C.O(nlogn)D.O(2ⁿ)23.关于二叉搜索树，说法正确的有（）A.左子树所有节点值小于根节点B.右子树所有节点值大于根节点C.中序遍历为有序序列D.一定是平衡二叉树24.最小生成树算法包括（）A.DijkstraB.PrimC.KruskalD.Floyd25.以下算法中，属于动态规划思想的有（）A.背包问题B.最长公共子序列C.冒泡排序D.最短路DP26.关于栈和队列，说法正确的有（）A.栈可实现括号匹配校验B.队列可实现广度优先遍历C.栈和队列都可以用数组实现D.栈是先进先出结构27.下列进制转换正确的有（）A.(1010)₂=10₁₀B.(FF)₁₆=255₁₀C.(12)₈=10₁₀D.(111)₂=6₁₀28.不稳定的排序算法有（）A.快速排序B.堆排序C.归并排序D.希尔排序29.图的遍历方式包括（）A.DFSB.BFSC.二分遍历D.顺序遍历30.动态规划问题的核心要素包括（）A.最优子结构B.重叠子问题C.无后效性D.贪心选择31.以下可以用于优化最短路算法的有（）A.堆优化B.链式前向星存图C.暴力枚举D.松弛操作32.关于链表和数组对比，说法正确的有（）A.数组随机访问快B.链表插入删除快C.数组内存连续D.链表内存连续33.属于搜索剪枝技巧的有（）A.可行性剪枝B.最优性剪枝C.记忆化搜索D.暴力遍历34.下列关于递归的说法正确的有（）A.递归深度过大会导致栈溢出B.递归可以转化为迭代实现C.递归无需终止条件D.递归适合处理分治问题35.分治算法的应用场景有（）A.归并排序B.快速排序C.二分查找D.冒泡排序36.关于拓扑排序，说法正确的有（）A.仅适用于有向无环图B.可以判断图中是否存在环C.排序结果唯一D.基于入度实现37.C++中循环语句包括（）A.ifB.forC.whileD.do-while38.能够处理负权边的最短路算法有（）A.DijkstraB.SPFAC.FloydD.Prim39.以下属于模拟算法应用的有（）A.进制转换B.字符串处理C.简单队列模拟D.背包求解40.平衡二叉树的优势有（）A.避免二叉树退化成链表B.保证查询效率稳定C.节点数量更少D.遍历速度更快三、问题求解（共5题，每题6分，共30分）41.已知有一个长度为n的有序数组，使用二分查找查找目标元素，最坏情况下的比较次数为多少？请写出通项公式。42.一个无向图有6个顶点、8条边，该图的最大连通分量顶点数为6，最小连通分量顶点数为1，请问该图最多有几个连通分量？43.求1~100中，所有能被3整除或能被5整除的整数的个数。44.一棵二叉树有20个叶子节点，请问该二叉树中度为2的节点个数为多少？写出推导过程。45.现有10个物品，每个物品重量为1，价值分别为1,2,3,...,10，背包最大容量为6，求01背包的最大价值。NOIP2026提高组复赛试题（上机）考试时间：2026年11月7日8:30-12:00满分：400分答题说明：共四道题目，每题100分，包含基础分、部分分、满分数据，支持暴力、优化、正解多种写法。T1区间统计（100分）题目描述给定n个整数组成的序列a[1~n]，以及一个整数k。定义合法区间为：区间内所有数的最大值与最小值的差值≤k。请你求出序列中合法区间的总数量。输入格式第一行两个整数n,k。第二行n个整数，表示序列a。输出格式输出一个整数，表示合法区间总数。数据范围对于30%的数据：n≤100对于60%的数据：n≤1000对于100%的数据：1≤n≤1e5，0≤k≤1e9，1≤a[i]≤1e9T2数字拆分（100分）题目描述给定一个正整数n，你需要将n拆分为若干个互不相同的正整数之和，使得拆分后的所有数的乘积最大。请求出这个最大乘积。答案对998244353取模。输入格式一行一个整数n。输出格式输出一个整数，表示最大乘积模998244353的结果。数据范围对于40%的数据：n≤20对于70%的数据：n≤1000对于100%的数据：1≤n≤1e6T3树上查询（100分）题目描述给定一棵n个节点的无根树，节点编号1~n，每个节点有一个权值w[i]。现有m次查询，每次查询给出两个节点u,v，求u到v路径上所有节点权值的异或和。输入格式第一行一个整数n。第二行n个整数w[1]~w[n]。接下来n-1行，每行两个整数x,y，表示x,y之间有一条边。接下来一行一个整数m。接下来m行，每行两个整数u,v。输出格式对于每次查询，输出一行一个整数，表示路径异或和。数据范围对于30%的数据：n,m≤100对于60%的数据：n,m≤1000对于100%的数据：1≤n,m≤1e5，0≤w[i]≤1e9T4城市联通（100分）题目描述有n座城市，初始时所有城市相互不连通。现有m条修路操作，每条操作给出u,v,w，表示在u,v之间修建一条权值为w的双向道路。每次修路完成后，你需要输出当前整张图的最小生成树总权值；若当前图不连通，输出-1。输入格式第一行两个整数n,m。接下来m行，每行三个整数u,v,w。输出格式共m行，每行一个整数，为每次操作后的答案。数据范围对于40%的数据：n≤100，m≤1000对于70%的数据：n≤1000，m≤1e4对于100%的数据：1≤n≤1e5，1≤m≤2e5，1≤w≤1e6NOIP2026提高组详细答案与解析一、初赛选择题答案与解析单项选择题答案1.C2.B3.A4.B5.D6.B7.B8.C9.C10.A11.B12.B13.C14.B15.D16.B17.C18.B19.D20.A核心题目解析3.前序ABCDEF（根左右），中序CBAEDF（左根右）。根为A，左子树CB，右子树EDF；递归推导后序为CBEFDA。5.栈先进后出，1先出栈的情况下，2、3、4必然全部在栈中，不可能出现5之后2、3、4依次出栈的情况，D错误。11.深度k的满二叉树节点总数为2^k-1，2^5-1=31。20.BFS按层遍历，天然求解无权图单源最短路径。不定项选择题答案21.ABC22.ABC23.ABC24.BC25.ABD26.ABC27.ABC28.ABD29.AB30.ABC31.ABD32.ABC33.ABC34.ABD35.ABC36.ABD37.BCD38.BC39.ABC40.AB核心题目解析23.二叉搜索树不一定平衡，极端情况会退化成链表，D错误。28.归并排序是稳定排序，快速、堆、希尔排序均为不稳定排序。38.Dijkstra无法处理负权，SPFA、Floyd可处理负权边。二、问题求解答案与解析41.答案：⌊解析：二分查找每次将区间缩小一半，最坏情况下需要遍历完全部二分层数，向下取整后加1，为标准最坏比较次数公式。42.答案：3解析：要最大化连通分量，需拆分出最多孤立点。已知最大连通分量6个点，占用全部顶点，无法拆分孤立点；修正题意：最大连通分量可为部分点，8条边最少需要4个点构成连通图（完全图6边，加2边共8边），剩余2个孤立点，总连通分量=1（4点连通）+2（孤立点）=3。43.答案：47解析：容斥原理。能被3整除：33个，能被5整除：20个，能被15整除：6个。总数=33+20-6=47。44.答案：19解析：二叉树性质：叶子节点数n0=n2+1。n0=20，故n2=19。45.答案：21解析：容量6，选1+2+3=6，价值1+2+3=6；最优选择：2+4=6（6）、1+5=6（6）、6（6），最优为3+2+1无优化，正确最优：6解题思路满分代码#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

constintN=1e5+10;

intn,k,a[N];

deque<int>qmax,qmin;

intmain(){

scanf("%d%d",&n,&k);

for(inti=1;i<=n;i++)scanf("%d",&a[i]);

llans=0;

intl=1;

for(intr=1;r<=n;r++){

while(!qmax.empty()&&a[r]>a[qmax.back()])qmax.pop_back();

qmax.push_back(r);

while(!qmin.empty()&&a[r]<a[qmin.back()])qmin.pop_back();

qmin.push_back(r);

while(a[qmax.front()]-a[qmin.front()]>k){

if(qmax.front()==l)qmax.pop_front();

if(qmin.front()==l)qmin.pop_front();

l++;

}

ans+=r-l+1;

}

printf("%lld\n",ans);

return0;

}解题思路满分代码#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

constintmod=998244353;

intmain(){

intn;scanf("%d",&n);

if(n==1){printf("1\n");return0;}

llres=1;

intsum=0,last=2;

vector<int>v;

while(sum+last<=n){

v.push_back(last);

sum+=last;

last++;

}

intrem=n-sum;

if(rem){

for(inti=v.size()-1;i>=0&&rem;i--){

v[i]++;rem--;

}

if(rem)v.push_back(rem);

}

for(autox:v)res=res*x%mod;

printf("%lld\n",res);

return0;

}解题思路满分代码#include<bits/stdc++.h>

usingnamespacestd;

constintN=1e5+10;

vector<int>g[N];

intw[N],xor_dis[N],dep[N],f[N][20];

intn,m;

voiddfs(intu,intfa){

f[u][0]=fa;

dep[u]=dep[fa]+1;

xor_dis[u]=xor_dis[fa]^w[u];

for(inti=1;i<20;i++)f[u][i]=f[f[u][i-1]][i-1];

for(autov:g[u])if(v!=fa)dfs(v,u);

}

intlca(intu,intv){

if(dep[u]<dep[v])swap(u,v);

for(inti=19;i>=0;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i];

if(u==v)returnu;

for(inti=19;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];

returnf[u][0];

}

intmain(){

scanf("%d",&n);

for(inti=1;i<=n;i++)scanf("%d",&w[i]);

for(inti=1;i<n;i++){

intx,y;scanf("%d%d",&x,&y);

g[x].push_back(y);g[y].push_back(x);

}

dfs(1,0);

scanf("%d",&m);

while(m--){

intu,v;scanf("%d%d",&u,&v);

intp=lca(u,v);

printf("%d\n",xor_dis[u]^xor_dis[v]^w[p]);

}

return0;

}解题思路满分代码#include<bits/stdc++.h>

usingnamesp