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

NOIP2026全国青少年信息学奥林匹克联赛提高组试题及详细答案一、试题正文NOIP2026提高组初赛试题考试时长：90分钟满分：100分题型：单选、判断、程序阅读、程序完善（一）单项选择题（共15题，每题2分，共30分）1.以下不属于线性数据结构的是（）A.队列B.栈C.二叉树D.链表2.对于规模为n的无序数组，简单选择排序的最坏时间复杂度为（）A.O(n)B.O(nlogn)C.O(n²)D.O(1)3.一个高度为h的完全二叉树，最多包含的结点个数为（）A.2ʰ-1B.2ʰ⁻¹C.h²D.2ʰ4.计算机网络中，IP协议的主要作用是（）A.可靠传输数据B.路由寻址与数据包转发C.端口监听D.数据加密5.十进制数2026转换为二进制数的位数为（）A.10位B.11位C.12位D.13位6.下列排序算法中，稳定排序的是（）A.快速排序B.堆排序C.冒泡排序D.简单选择排序7.栈的入栈序列为1、2、3、4、5，不可能得到的出栈序列是（）A.32154B.45321C.54123D.234518.图的广度优先遍历（BFS）最适合求解的问题是（）A.有向图拓扑排序B.无权图最短路C.图的最长路径D.最小生成树9.C++中，int类型变量的取值范围主要由什么决定（）A.编译器版本B.操作系统位数C.代码书写格式D.变量命名规则10.哈希表中，线性探测法解决冲突的主要缺陷是（）A.空间复杂度极高B.容易产生哈希堆积C.无法删除元素D.查找速度极慢11.下列关于递归的说法正确的是（）A.递归无需终止条件B.递归一定比迭代效率高C.递归可能产生栈溢出D.递归不占用内存空间12.一棵有1023个结点的满二叉树，叶子结点数量为（）A.512B.511C.256D.102313.时间复杂度O(nlogn)的排序算法是（）A.插入排序B.归并排序C.冒泡排序D.计数排序14.下列不属于图的存储结构的是（）A.邻接矩阵B.邻接表C.十字链表D.顺序栈15.二进制数11010110对应的十进制数为（）A.214B.213C.212D.211（二）判断题（共10题，每题2分，共20分，正确选√，错误选×）1.二叉树的前序遍历序列中，根结点一定是序列第一个元素。（）2.所有的递归算法都可以改写为迭代算法。（）3.堆排序是稳定排序，时间复杂度稳定为O(nlogn)。（）4.无向图的邻接矩阵一定是对称矩阵。（）5.队列遵循先进后出的运算规则。（）6.完全二叉树的结点可以连续存储在数组中，无需浪费空间。（）7.快速排序在数据有序时效率最高。（）8.哈希表的查找时间复杂度最坏可达O(n)。（）9.有向无环图一定存在拓扑序列。（）10.栈和队列都可以通过数组和链表实现。（）（三）程序阅读题（共2题，每题10分，共20分）阅读程序1cpp

#include<iostream>

usingnamespacestd;

intfunc(intn){

if(n==0)return0;

returnfunc(n/2)+n%2;

}

intmain(){

intx=2026;

cout<<func(x);

return0;

}请写出程序运行输出结果。阅读程序2cpp

#include<iostream>

usingnamespacestd;

inta[10]={2,5,1,8,3,9,4,7,6,0};

intmain(){

intans=0;

for(inti=0;i<10;i++){

for(intj=i+1;j<10;j++){

if(a[i]>a[j])ans++;

}

}

cout<<ans;

return0;

}请写出程序运行输出结果。（四）程序完善题（共2题，每题15分，共30分）完善程序1：统计区间素数个数题目描述：给定两个整数L、R（1≤L≤R≤100000），统计区间[L,R]内素数的个数。以下代码采用埃氏筛法预处理素数，补全空缺代码。cpp

#include<iostream>

#include<cstring>

usingnamespacestd;

constintMAXN=100005;

boolisp[MAXN];

voidinit(){

memset(isp,true,sizeof(isp));

isp[0]=isp[1]=____①____;

for(inti=2;i*i<MAXN;i++){

if(____②____){

for(intj=i*i;j<MAXN;j+=i){

isp[j]=____③____;

}

}

}

}

intmain(){

init();

intL,R,cnt=0;

cin>>L>>R;

for(inti=L;i<=R;i++){

if(____④____)cnt++;

}

cout<<cnt<<endl;

return0;

}补全①②③④四处空缺代码。完善程序2：二分查找题目描述：给定严格递增的整数数组，查询目标数x是否存在，存在输出下标，不存在输出-1，补全二分查找代码。cpp

#include<iostream>

usingnamespacestd;

inta[1005],n,x;

intbinary(){

intl=1,r=n;

while(____①____){

intmid=(l+r)/2;

if(a[mid]==x)returnmid;

elseif(a[mid]<x){

l=____②____;

}else{

r=____③____;

}

}

return-1;

}

intmain(){

cin>>n;

for(inti=1;i<=n;i++)cin>>a[i];

cin>>x;

cout<<binary()<<endl;

return0;

}补全①②③三处空缺代码。NOIP2026提高组复赛试题考试时长：3小时满分：400分题型：四道编程题，每题100分T1数字求和（100分）题目描述给定正整数n，定义f(x)为x的每一位数字之和。求1~n中所有满足f(x)为偶数的数字的总和。输入格式一行一个整数n（1≤n≤10⁶）。输出格式一行一个整数，表示符合条件的数字总和。样例输入110样例输出130样例解释符合条件的数：2、4、6、8、10，总和2+4+6+8+10=30。T2区间最大子段和（100分）题目描述给定长度为n的整数序列（包含负数），求出序列中最大的子段和（子段为连续区间，不能为空）。输入格式第一行一个整数n（1≤n≤10⁵）。第二行n个整数，为序列元素，绝对值不超过1000。输出格式一行一个整数，表示最大子段和。样例输入15-23-12-1样例输出14T3二叉树遍历（100分）题目描述给定一棵二叉树的前序遍历和中序遍历序列，求该二叉树的后序遍历序列。保证结点权值互不相同，结点数n≤1000。输入格式第一行一个整数n，表示结点个数。第二行n个整数，前序遍历序列。第三行n个整数，中序遍历序列。输出格式一行n个整数，为后序遍历序列，元素空格分隔。样例输入151245342513样例输出145231T4最短路径计数（100分）题目描述给定一个n个点m条边的无向无权连通图，求从1号点到n号点的最短路径的总条数。答案对1000000007取模。输入格式第一行两个整数n、m（2≤n≤1000，1≤m≤5000）。接下来m行，每行两个整数u、v，表示u、v之间有一条无向边。输出格式一行一个整数，最短路径数量对1e9+7取模的结果。样例输例输出12二、详细答案与解析（一）初赛答案与解析单选题答案（1-15）1.C2.C3.A4.B5.B6.C7.C8.B9.B10.B11.C12.A13.B14.D15.A单选题核心解析1.线性结构包括栈、队列、链表、顺序表，二叉树属于树形非线性结构。2.简单选择排序无论数据有序与否，都需要遍历比较，最坏、平均时间复杂度均为O(n²)。3.高度为h的满二叉树结点总数为2ʰ-1，完全二叉树最多结点数等同于同高度满二叉树。5.2¹⁰=1024，2¹¹=2048，2026介于两者之间，二进制共11位。7.栈先进后出，5第一个出栈说明1、2、3、4已入栈，后续出栈只能是4321，无法出现123序列。12.满二叉树结点数2ʰ-1=1023，得h=10，叶子结点数为2ʰ⁻¹=512。15.11010110按权展开：128+64+16+4+2=214。判断题答案（1-10）1.√2.√3.×4.√5.×6.√7.×8.√9.√10.√判断题核心解析3.堆排序是不稳定排序，相等元素相对位置可能改变。5.队列规则为先进先出，栈为先进后出。7.快速排序在数据完全有序时，退化为O(n²)复杂度，效率最低。程序阅读题答案与解析阅读程序1答案：7解析：函数功能为统计数字二进制中1的个数。2026二进制为11111101010，共计7个1，输出结果为7。阅读程序2答案：27解析：程序统计数组逆序对数量。数组{2,5,1,8,3,9,4,7,6,0}遍历统计，总逆序对数量为27。程序完善题答案完善程序1①false②isp[i]③false④isp[i]解析：埃氏筛核心逻辑：0、1非素数；若i是素数，标记其所有倍数为非素数，最后遍历统计区间素数。完善程序2①l<=r②mid+1③mid-1解析：二分查找循环条件为左右指针合法；中间值小于目标，右区间查找，左指针右移；中间值大于目标，左区间查找，右指针左移。（二）复赛试题详细题解+标程T1数字求和题解解题思路：暴力枚举1~n所有数字，逐位拆分计算数位和，判断是否为偶数，累加符合条件的数字即可。数据范围1e6，暴力遍历完全满足时间限制。C++标程cpp

#include<iostream>

usingnamespacestd;

typedeflonglongll;

intcheck(intx){

intres=0;

while(x){

res+=x%10;

x/=10;

}

returnres;

}

intmain(){

intn;

cin>>n;

llans=0;

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

if(check(i)%2==0){

ans+=i;

}

}

cout<<ans<<endl;

return0;

}T2区间最大子段和题解解题思路：经典最大子段和问题，采用Kadane算法（动态规划）。定义dp[i]为以第i个元素结尾的最大子段和，状态转移：dp[i]=max(a[i],dp[i-1]+a[i])，全程维护最大值。时间复杂度O(n)，适配1e5数据范围。C++标程cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintMAXN=1e5+10;

inta[MAXN];

intmain(){

intn;

cin>>n;

for(inti=1;i<=n;i++)cin>>a[i];

intnow=a[1],maxn=a[1];

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

now=max(a[i],now+a[i]);

maxn=max(maxn,now);

}

cout<<maxn<<endl;

return0;

}T3二叉树遍历题解解题思路：前序遍历首元素为根结点，在中序序列中找到根结点位置，左侧为左子树，右侧为右子树。递归拆分左右子树，最后输出根结点，实现后序遍历。用哈希数组存储中序结点下标，优化查找效率。C++标程cpp

#include<iostream>

usingnamespacestd;

constintMAXN=1005;

intpre[MAXN],in[MAXN],pos[MAXN];

voiddfs(intpl,intpr,intil,intir){

if(pl>pr)return;

introot=pre[pl];

intp=pos[root];

//递归左子树

dfs(pl+1,pl+p-il,il,p-1);

//递归右子树

dfs(pl+p-il+1,pr,p+1,ir);

//后序输出根

cout<<root<<"";

}

intmain(){

intn;

cin>>n;

for(inti=1;i<=n;i++)cin>>pre[i];

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

cin>>in[i];

pos[in[i]]=i;

}

dfs(1,n,1,n);

return0;

}T4最短路径计数题解解题思路：无权图最短路采用BFS求解，同时记录路径数量。定义dis数组存储起点到各点最短路长度，cnt数组存储路径数。初始dis[1]=0，cnt[1]=1；遍历过程中，若找到更短路径，更新距离并重置计数；若找到等长最短路径，累加计数，结果对1e9+7取模。C++标程cpp

#include<iostream>

#include<vector>

#include<queue>

#include<cstring>

usingnamespacestd;

constintMOD=1e9+7;

constintMAXN=1005;

vector<int>g[MAXN];

intdis[MAXN],cnt[MAXN];

intmain(){

intn,m;

cin>>n>>m;

for(int