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

NOIP2026全国青少年信息学奥林匹克联赛提高组初赛试题（含详细答案）考试时间：2026年10月18日14:30-16:30满分：100分注意事项：1.答卷前，考生务必将自己的姓名、准考证号填写在答题卡上。2.答案全部写在答题卡上，写在本试卷上无效。3.考试结束后，将试卷和答题卡一并交回。一、单项选择题（共15题，每题2分，共计30分。每题仅有一个正确选项）1.下列不属于线性数据结构的是（）A.队列B.栈C.二叉树D.链表2.十进制数2026转换为二进制数的位数为（）A.10位B.11位C.12位D.13位3.已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为BADCFE，则其后序遍历序列为（）A.BDFECAB.BDEFCAC.DBFEACD.BDFCEA4.时间复杂度为O(n²)的排序算法是（）A.归并排序B.快速排序（平均）C.冒泡排序D.堆排序5.哈希表解决冲突的方法中，开放寻址法不包含以下哪种方式（）A.线性探测B.二次探测C.链地址探测D.随机探测6.一台计算机的内存容量为8GB，等价于（）A.8×1024×1024KBB.8×1000×1000KBC.8×1024MBD.8×1000MB7.下列关于图的描述，错误的是（）A.无向完全图n个顶点的边数为n(n-1)/2B.有向图的邻接矩阵一定是对称矩阵C.拓扑排序仅适用于有向无环图D.最小生成树包含图中全部n个顶点，且无环8.C++语言中，以下变量定义合法的是（）A.int1a=10;B.inta_1=10;C.inta-b=10;D.intstatic=10;9.栈的应用场景不包括（）A.函数递归调用B.括号匹配校验C.广度优先搜索D.表达式求值10.已知IP地址00，其属于（）类IP地址A.A类B.B类C.C类D.D类11.二分查找算法的适用条件是（）A.无序数组B.有序顺序存储数组C.有序链式存储数组D.任意数组12.一棵深度为5的满二叉树的节点总数为（）A.16B.31C.32D.1513.下列操作系统中，属于开源系统的是（）A.Windows11B.macOSC.LinuxD.闭源Unix14.若入栈序列为1、2、3、4、5，则不可能的出栈序列是（）A.32154B.43521C.15432D.5413215.HTTP协议中，状态码200表示（）A.请求成功B.页面未找到C.服务器错误D.重定向二、不定项选择题（共5题，每题2分，共计10分。每题有一个或多个正确选项，多选、少选、错选均不得分）1.下列算法中，属于贪心算法应用的有（）A.哈夫曼编码B.最小生成树Kruskal算法C.01背包问题D.活动选择问题2.关于队列的描述，正确的有（）A.遵循先进先出规则B.可用于广度优先搜索C.循环队列可解决假溢出问题D.队列只能顺序存储3.以下属于稳定排序的算法有（）A.插入排序B.冒泡排序C.快速排序D.归并排序4.下列关于C++循环语句的说法正确的有（）A.for循环可以嵌套while循环B.break语句可跳出多层循环C.continue语句仅结束本次循环D.do-while循环至少执行一次5.下列数据结构中，能够快速实现插入和删除操作的有（）A.单向链表B.双向链表C.顺序数组D.栈三、问题求解（共2题，每题5分，共计10分）1.现有6个不同的小球，放入4个不同的盒子中，每个盒子至少放1个小球，共有多少种不同的放置方案？2.已知一个无向图有8个顶点、12条边，其连通图的最小生成树的边数为多少？若删除多少条边可使该图变为无环图？四、程序阅读题（共4题，每题8分，共计32分）程序1PlainText

#include<iostream>

usingnamespacestd;

intmain(){

inta=2026,b=12;

intres=0;

while(a%b!=0){

intt=a%b;

a=b;

b=t;

res++;

}

cout<<res+b<<endl;

return0;

}请问程序输出结果为？程序2PlainText

#include<iostream>

usingnamespacestd;

intf(intn){

if(n<=2)return1;

returnf(n-1)+f(n-2);

}

intmain(){

intans=0;

for(inti=3;i<=8;i++){

ans+=f(i);

}

cout<<ans<<endl;

return0;

}请问程序输出结果为？程序3PlainText

#include<iostream>

#include<algorithm>

usingnamespacestd;

intmain(){

intarr[]={5,2,9,1,5,6};

intn=6;

sort(arr,arr+n);

intsum=0;

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

sum+=arr[i];

}

cout<<sum<<endl;

return0;

}请问程序输出结果为？程序4PlainText

#include<iostream>

usingnamespacestd;

intmain(){

ints=0;

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

if(i%3==0)continue;

if(i%5==0)break;

s+=i;

}

cout<<s<<endl;

return0;

}请问程序输出结果为？五、程序完善题（共2题，每空2分，共计18分）程序1（最大公约数与最小公倍数）功能：输入两个正整数x、y，求解并输出二者的最大公约数（gcd）和最小公倍数（lcm）。最小公倍数公式：lcm(x,y)=x×y÷gcd(x,y)。PlainText

#include<iostream>

usingnamespacestd;

intgcd(inta,intb){

while(____1____){

intt=a%b;

a=b;

____2____;

}

return____3____;

}

intmain(){

intx,y;

cin>>x>>y;

intg=gcd(x,y);

intl=____4____/g;

cout<<g<<""<<l<<endl;

return0;

}补全四处空缺代码。程序2（斐波那契数列统计）功能：输入正整数n，统计1~n范围内所有斐波那契数的个数。斐波那契数列定义：F(1)=1，F(2)=1，F(k)=F(k-1)+F(k-2)。PlainText

#include<iostream>

usingnamespacestd;

intmain(){

intn;

cin>>n;

if(n<1){

cout<<0<<endl;

return0;

}

intcnt=1;

inta=1,b=1;

while(____5____){

intc=a+b;

if(c>n)____6____;

cnt++;

____7____;

b=c;

}

cout<<____8____<<endl;

return0;

}补全四处空缺代码。参考答案及详细解析一、单项选择题（每题2分，共30分）1.C解析：线性数据结构包含栈、队列、链表、数组，元素呈一维线性排列；二叉树为树形非线性数据结构。2.B解析：2103.A解析：由前序A为根，中序判定左子树B，右子树DCFE；递归推导后序遍历为BDFECA。4.C解析：归并、堆排序平均复杂度O(nlogn)；快速排序平均O(nlogn)，最坏O(n²)；冒泡排序稳定O(n²)。5.C解析：链地址法是独立的哈希冲突解决方式，不属于开放寻址法；开放寻址法包含线性、二次、随机探测。6.C解析：计算机存储标准1GB=1024MB，1MB=1024KB。7.B解析：无向图邻接矩阵对称，有向图邻接矩阵通常不对称。8.B解析：变量名不能以数字开头、不能含特殊符号、不能使用关键字，仅a_1合法。9.C解析：广度优先搜索基于队列实现，栈用于深度优先、递归、括号匹配、表达式求值。10.C解析：C类IP地址范围~55，题干地址属于C类。11.B解析：二分查找依赖随机访问，仅适用于有序的顺序存储数组，链式存储无法高效查找。12.B解析：深度k的满二叉树节点总数为2k−1，13.C解析：Linux为开源操作系统，Windows、macOS均为闭源系统。14.D解析：入栈序列12345，5第一个出栈则1、2、3、4必已入栈，后续出栈只能是4321，不可能出现4之后的1。15.A解析：200为请求成功，404为页面未找到，500为服务器错误，302为临时重定向。二、不定项选择题（每题2分，共10分）1.ABD解析：01背包无贪心最优解，需动态规划求解；哈夫曼编码、Kruskal算法、活动选择问题均为经典贪心应用。2.ABC解析：队列可顺序存储、链式存储，D错误；其余描述均正确。3.ABD解析：快速排序属于不稳定排序，插入、冒泡、归并排序均为稳定排序。4.ACD解析：break仅跳出当前单层循环，无法跳出多层循环，B错误；其余语句规则描述正确。5.ABD解析：顺序数组插入删除需移动元素，效率低；链表、栈均可快速完成首尾插入删除操作。三、问题求解（每题5分，共10分）1.答案：1560种解析：6个不同小球放入4个不同盒子，每盒至少1个，分组方式仅两种：(3,1,1,1)和(2,2,1,1)。①3,1,1,1分组：C②2,2,1,1分组：C总计：480+1080=1560种。2.答案：7条；5条解析：n个顶点的连通图最小生成树边数为n-1，8个顶点即7条边；无环图为森林，8个顶点无环最多7条边，现有12条边，需删除12-7=5条边。四、程序阅读题（每题8分，共32分）1.输出：2解析：程序为辗转相除法迭代统计次数。2026%12=10，res=1；12%10=2，res=2；10%2=0，循环结束。最终输出2+0=2。2.输出：52解析：递归函数为斐波那契数列，f(3)=2、f(4)=3、f(5)=5、f(6)=8、f(7)=13、f(8)=21。累加：2+3+5+8+13+21=52。3.输出：13解析：数组排序后为{1,2,5,6,9}，循环遍历i=1、2、3，累加2+5+6=13。4.输出：12解析：遍历1~10，跳过3、6、9，遇到5直接终止循环。累加1+2+4=12。五、程序完善题（每空2分，共18分）程序1答案1.b!=0（辗转相除循环条